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