Difference between revisions of "Euler's totient function"

m
Line 5: Line 5:
 
The formal definition is <math>\phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} </math>.
 
The formal definition is <math>\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>.
+
Given the [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, one can compute <math>\phi(n)</math> using the formula <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 12:55, 20 June 2006

Euler's totient function, $\phi(n)$, 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 $\phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\}$.

Given the prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}$, one can compute $\phi(n)$ using the formula $\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 for any ${a}, {b}$ that $\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