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

m |
ComplexZeta (talk | contribs) m (→Formulas: Removed abuse of notation) |
||

Line 5: | Line 5: | ||

The formal definition is <math>\phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} </math>. | The formal definition is <math>\phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} </math>. | ||

− | Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p} | + | Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}</math>, one can compute <math>\phi(n)</math> using the formula <math> \phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_m}\right) </math>. |

=== Identities === | === Identities === |

## Revision as of 23:11, 24 June 2006

**Euler's totient function**, , is defined as the number of positive integers less than or equal to a given positive integer that are relatively prime to that integer.

### Formulas

The formal definition is .

Given the general prime factorization of , one can compute using the formula .

### Identities

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

For relatively prime , .

In fact, we also have for any that .

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