Difference between revisions of "Euler's totient function"

(Added new identity)
m
Line 11: Line 11:
 
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>.
 
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>.
  
For non-relatively prime <math>{a}, {b}</math>, we have <math>\phi{(a)}\phi{(b)}gcd(a,b)=\phi{(ab)}\phi{gcd(a,b)}</math>.
+
In fact, we also have <math>{a}, {b}</math>, we have <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</math>.
  
 
For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>.
 
For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>.

Revision as of 22:03, 18 June 2006

Euler's totient function, $\phi(n)$, 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)}$.

In fact, we also have ${a}, {b}$, we have $\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})$.

For any $n$, we have $\sum_{d|n}\phi(d)=n$ where the sum is taken over all divisors d of $n$.

See also

Invalid username
Login to AoPS