Difference between revisions of "Euler's phi function"

(Formulas: \left(and\right))
(See also)
Line 5: Line 5:
 
Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then one formula for <math>\phi(n)</math> is <math> \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) </math>.
 
Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then one formula for <math>\phi(n)</math> is <math> \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) </math>.
  
=== See also ===
 
  
* [[Number theory]]
 
* [[Prime]]
 
* [[Euler's Totient Theorem]]
 
  
 
=== Identities ===
 
=== Identities ===

Revision as of 15:34, 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^{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)$.


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