Euler's totient function

Revision as of 14:35, 18 June 2006 by Chess64 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Euler's totient function, $\phi(n)$, determines the number of integers less than a given positive integer that are relatively prime to that integer.


Given the prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}$, then one formula for $\phi(n)$ is $\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right)$.


For prime p, $\phi(p)=p-1$, because all numbers less than ${p}$ are relatively prime to it.

For relatively prime ${a}, {b}$, $\phi{(a)}\phi{(b)} = \phi{(ab)}$.

See also

Invalid username
Login to AoPS