# Difference between revisions of "Euler's totient function"

(Added new identity) |
|||

Line 10: | Line 10: | ||

For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. | For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>. | ||

+ | |||

+ | For non-relatively prime <math>{a}, {b}</math>, we have <math>\phi{(a)}\phi{(b)}gcd(a,b)=\phi{(ab)}\phi{gcd(a,b)}</math>. | ||

For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. | For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. |

## Revision as of 21:44, 18 June 2006

**Euler's totient function**, , determines the number of integers less than a given positive integer that are relatively prime to that integer.

### Formulas

Given the prime factorization of , then one formula for is .

### Identities

For prime p, , because all numbers less than are relatively prime to it.

For relatively prime , .

For non-relatively prime , we have .

For any , we have where the sum is taken over all divisors d of .