Difference between revisions of "Euler's phi function"

(Removed content that was parsing badly; hopefully it can be restored eventually)
(Fixed LaTeX on old version; restores old info)
Line 8: Line 8:
 
=== Identities ===
 
=== Identities ===
  
For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than p are relatively prime to it.
+
For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it.
 +
 
 +
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>.
  
 
=== Other Names ===
 
=== Other Names ===

Revision as of 13:46, 18 June 2006

Euler's phi 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 $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})$

Identities

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)}$.

Other Names

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