View source

'''Euler's totient function''' <math>\phi(n)</math> applied to a [[positive integer]] <math>n</math> is defined to be the number of positive integers less than or equal to <math>n</math> that are [[relatively prime]] to <math>n</math>.  <math>\phi(n)</math> is read "phi of n."

== Formulas ==
To derive the formula, let us first define the [[prime factorization]] of <math> n </math> as <math> n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} </math> where the <math>p_i </math> are distinct [[prime number]]s.  Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to  <math> n </math> that are relatively prime to it.

First, let's count the complement of what we want (i.e. all the numbers less than <math> n </math> that share a common factor with it).  There are <math> \frac{n}{p_1} </math> numbers less than <math> n </math> that are divisible by <math> p_1 </math>.  If we do the same for each <math> p_i </math> and add these up, we get

<center><cmath> \frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.</cmath></center>

But we are obviously overcounting.  We then subtract out those divisible by two of the <math> p_i </math>.  There are <math>\sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}</math> such numbers. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is

<center><cmath> \sum_{1 \le i \le m}\frac{n}{p_i}
- \sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}
+ \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}. </cmath></center>

This sum represents the number of numbers less than <math>n</math> sharing a common factor with <math>n</math>, so

<math>\phi(n) = n - \left(\sum_{1 \le i \le m}\frac{n}{p_i}</math> <math>- \sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}
+ \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}\right)</math>

<math>\phi(n)= n\left(1 - \sum_{1 \le i \le m}\frac{1}{p_i}
+ \sum_{1 \le i_1 < i_2 \le m}\frac{1}{p_{i_1}p_{i_2}} - \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m}\right)</math>

<math>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</math>

Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}</math>, one can compute <math>\phi(n)</math> using the formula <cmath>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</cmath>

== Identities ==

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>.

In fact, we also have for any <math>{a}, {b}</math> that <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>.

Proof. Split the set <math>\{1,2,\ldots,n\}</math> into disjoint sets <math>A_d</math> where for all <math>d\mid n</math> we have
<cmath>A_d=\{x:1\leq x\leq n\quad\text{and}\quad \operatorname{syt}(x,n)=d \}.</cmath>
Now <math>\operatorname{gcd}(dx,n)=d</math> if and only if <math>\operatorname{gcd}(x,n/d)=1</math>. Furthermore, <math>1\leq dx\leq n</math> if and only if <math>1\leq x\leq n/d</math>. Now one can see that the number of elements of <math>A_d</math> equals the number of elements of
<cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath>
Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that
<cmath>n=\sum_{d \mid n}\varphi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).</cmath>

==Notation==
Sometimes, instead of  <math>\phi</math>, <math>\varphi</math> is used. This variation of the Greek letter ''phi'' is common in textbooks, and is standard usage on the English [[Wikipedia]]

== See Also ==

* [[Number theory]]
* [[Prime]]
* [[Euler's Totient Theorem]]

[[Category:Functions]]
[[Category:Number theory]]