Euler's totient function: Difference between revisions

Revision as of 15:17, 25 July 2008

This is an AoPSWiki Word of the Week for July 18-July 24

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

Formulas

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

First, let's count the complement of what we want (i.e. all the numbers less than $n$ that share a common factor with it). There are $p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m}$ numbers less than $n$ that are divisible by $p_1$ . If we do the same for each $p_k$ and add these up, we get

$p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} + p_1^{e_1}p_2^{e_2-1}\cdots p_m^{e_m} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m - 1}.$

We can factor out, though:

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1+p_2+\cdots + p_m).$

But we are obviously overcounting. We then subtract out those divisible by two of the $p_k$ . We continue with this PIE argument to figure out that the number of elements in the complement of what we want is

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}[(p_1+p_2+\cdots+p_m)-(p_1p_2+p_1p_3+\cdots+p_{m-1}p_m)+\cdots+(-1)^{m+1}(p_1p_2\cdots p_m)]$

which we can factor further as

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1-1)(p_2-1)\cdots(p_m-1).$

Making one small adjustment, we write this as

$\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).$

Given the general prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}$ , 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_m}\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$ .

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

Notation

Sometimes, instead of $\phi$ , $\varphi$ is used. This variation of the Greek letter phi is common in textbooks, and is standard usage on the English Wikipedia

@@ Line 37: / Line 37: @@
 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==

Page

Toolbox

Search

Euler's totient function: Difference between revisions

Revision as of 15:17, 25 July 2008

Contents

Formulas

Identities

Notation

See Also