Euler's phi function

Revision as of 12:34, 18 June 2006 by Dschafer (talk | contribs) (Removed content that was parsing badly; hopefully it can be restored eventually)

Euler's phi function 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^{a_1}p_2^{a_2} \cdots p_n^{a_n}$, then one formula for $\phi(n)$ is: $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_n})$


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

Other Names

  • Totient Function
  • Euler's Totient Function
Invalid username
Login to AoPS