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

(Added new identity) |
m |
||

Line 11: | Line 11: | ||

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>. | ||

− | + | In fact, we also have <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 22:03, 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 , .

In fact, we also have , we have .

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