Number Theory Home

## Euler's $$\phi$$ Function

Euler introduced the following number-theoretic function called Euler's $$\phi$$ function or Euler's totient function.

Definition. For any positive integer $$n$$, $$\phi(n)$$ is the number of all positive integers less than or equal to $$n$$ that are relatively prime to $$n$$.

Example. $$\phi(1)=1$$, $$\phi(2)=1$$, $$\phi(3)=2$$, $$\phi(4)=2$$, $$\phi(5)=4$$.

Observation. Let $$n>1$$ be a positive integer. Then $$n$$ is prime if and only if $$\phi(n)=n-1$$.

Proposition. Let $$p$$ be a prime and $$a$$ be a positive integer. Then $\phi(p^a)=p^a-p^{a-1}=p^a\left(1-\frac{1}{p}\right).$

Proof. The positive integers less than or equal to $$p^a$$ that are not relatively prime to $$p^a$$ are $$p^{a-1}$$ divisors of $$p^a$$: $$p,2p,3p,\ldots,p^{a-1}p$$. Thus $$\phi(p^a)=p^a-p^{a-1}=p^a\left(1-\frac{1}{p}\right)$$. ◼

To derive a formula for $$\phi$$ we need the multiplicativity of $$\phi$$.

Theorem. $$\phi$$ is a multiplicative function.

Theorem. Let $$n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$$ be the prime-power factorization of $$n>1$$. Then $\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right).$

Proof. Using the multiplicativity of $$\phi$$ repeatedly we get $\begin{array}{rl} \phi(n)&=\phi(p_1^{a_1}\cdot (p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}))\\ &=\phi(p_1^{a_1}) \phi(p_2^{a_2}(p_3^{a_3}\cdots p_k^{a_k}))\\ &=\phi(p_1^{a_1}) \phi(p_2^{a_2})\phi(p_3^{a_3}\cdots p_k^{a_k})\\ &\vdots\\ &=\phi(p_1^{a_1}) \phi(p_2^{a_2})\cdots \phi(p_k^{a_k}). \end{array}$ By the last proposition we have $\begin{array}{rl} \phi(n)=\phi(p_1^{a_1}) \phi(p_2^{a_2})\cdots \phi(p_k^{a_k}) &=p_1^{k_1}\left(1-\frac{1}{p_1}\right) p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_k^{a_k}\left(1-\frac{1}{p_k}\right)\\ &=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)\\ &=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right). ◼ \end{array}$

Example. For $$1176=2^3\cdot 3^1\cdot 7^2$$, $$\phi(1176)=1176\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) \left(1-\frac{1}{7}\right)=1176\frac{1}{2}\frac{2}{3}\frac{6}{7}=336$$.

Proof.(sketch) Let $$\gcd(m,n)=1$$. We show that $$\phi(mn)=\phi(m)\phi(n)$$. For each $$i=1,2,\ldots,m$$, define $S_i:=\{i,i+m,i+2m,\ldots,i+(n-1)m\}.$ Note that $$S_1,S_2,\ldots,S_m$$ partition $$\{1,2,\ldots,mn\}$$ and each $$S_i$$ contains exactly $$\phi(n)$$ integers that are relatively prime to $$n$$ (why?). Since $$\gcd(i+dm,m)=\gcd(i,m)$$, if $$i$$ is relatively prime to $$m$$, all integers in $$S_i$$ are relatively prime to $$m$$. Thus exactly $$\phi(m)$$ of $$S_1,S_2,\ldots,S_m$$ contain all the positive integers relatively prime to $$m$$. Since each $$S_i$$ contains exactly $$\phi(n)$$ integers that are relatively prime to $$n$$, there are exactly $$\phi(m)\phi(n)$$ integers in $$S_1\cup S_2\cup\cdots\cup S_m=\{1,2,\ldots,mn\}$$ that are relatively prime to both $$m$$ and $$n$$. The result follows as a positive integer is relatively prime to $$mn$$ if and only if it is relatively prime to both $$m$$ and $$n$$. ◼

Gauss noticed the following property of $$\phi$$.

Theorem. Let $$n$$ be a positive integer. Then $n=\sum_{d\vert n} \phi(d).$

Proof. For each positive divisor $$d$$ of $$n$$, we define a subset $$S_d$$ of $$\{1,2,\ldots,n\}$$ as follows: $S_d=\{x\;|\; 1\leq x\leq n,\; \gcd(x,n)=d \}.$ Suppose the positive divisors of $$n$$ are $$d_1,d_2,\ldots,d_k$$. Notice that $$S_{d_1},S_{d_2},\ldots,S_{d_k}$$ partition $$\{1,2,\ldots,n\}$$. Then $$n=\sum_{i=1}^k |S_{d_i}|=\sum_{d\vert n} |S_d|.$$ Now note that $$x\in S_d$$ if and only if $$\gcd(x,n)=d$$ if and only if $$\gcd(\frac{x}{d},\frac{n}{d})=1$$. Then $$|S_d|$$ is the number positive integers less than or equal to $$\frac{n}{d}$$ that are relatively prime to $$\frac{n}{d}$$. Thus $$|S_d|=\phi(\frac{n}{d})$$ and $n=\sum_{d\vert n} |S_d|=\sum_{d\vert n} \phi\left(\frac{n}{d}\right).$ As $$d$$ runs over all the positive divisors of $$n$$, so does $$\frac{n}{d}$$ and consequently $n=\sum_{d\vert n} \phi\left(\frac{n}{d}\right)=\sum_{d\vert n} \phi(d). ◼$

Example. The positive divisors of $$n=12$$ are $$1,2,3,4,6,12$$. So $\sum_{d\vert 12} \phi(d)=\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12)=1+1+2+2+2+4=12.$ Note that $$S_1=\{1,5,7,11 \}$$, $$S_2=\{2,10 \}$$, $$S_3=\{3,9 \}$$, $$S_4=\{4,8 \}$$, $$S_6=\{6 \}$$, $$S_{12}=\{12 \}$$.

Last edited