Difference between revisions of "Euler's totient function"
| Line 1: | Line 1: | ||
| − | '''Euler's totient function''', <math>\phi(n)</math>, | + | '''Euler's totient function''', <math>\phi(n)</math>, is defined as the number of positive integers less than or equal to a given positive integer that are [[relatively prime]] to that integer. |
=== Formulas === | === Formulas === | ||
| − | Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then | + | The formal definition is <math>\displaystyle \phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} </math>. |
| + | |||
| + | Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then another 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>. | ||
=== Identities === | === Identities === | ||
Revision as of 04:08, 20 June 2006
Euler's totient function, 
, is defined as the number of positive integers less than or equal to a given positive integer that are relatively prime to that integer.
Formulas
The formal definition is 
.
Given the prime factorization of 
, then another formula for is 
.
Identities
For prime p, 
, because all numbers less than 
are relatively prime to it.
For relatively prime 
, 
.
In fact, we also have for any that 
.
For any 
, we have 
where the sum is taken over all divisors d of .
