2.5: Euler's ϕ Function

Euler made the following definition, and it was good.

Definition: Euler's \(ϕ\) Function

Given \(n\in \mathbb{N}\), \[\phi(n)=\#\left(\{m\in\mathbb{Z}\mid 0\le m<n\text{ and }\gcd(m,n)=1\}\right)\ .\] In other words, \(\phi(n)\) counts the number of non-negative integers less than \(n\) which are relatively prime to \(n\).

This is called Euler’s \(\phi\) function, or Euler’s totient function (“totient” rhymes with “quotient”; this name was give to it by the English mathematician Sylvester).

Here’s one thing it is good for:

Theorem \(\PageIndex{1}\)

Given \(n\in \mathbb{N}\), \(\phi(n)\) is the number of elements of \(\mathbb{Z} / n \mathbb{Z}\) which are (multiplicatively) invertible.

Proof

This is just Theorem 2.4.4 part (5)

One quite surprising fact about Euler’s totient function is that it is multiplicative, at least for relatively prime numbers:

Theorem \(\PageIndex{2}\)

Given \(n, m ∈ \mathbb{Z}\), if \(\gcd(n,m)=1\) then \(\phi(nm)=\phi(n)\phi(m)\).

Proof

This is actually a nice application of the Chinese Remainder Theorem, as we shall see.

Fix \(n,m\in\mathbb{N}\) which are relatively prime. For \(k\in\mathbb{N}\), let \[(\mathbb{Z}/k\mathbb{Z})^*=\{x\in\mathbb{Z} / k \mathbb{Z} \mid x\text{ is invertible}\}\] so \(\phi(k)=\#((\mathbb{Z}/k\mathbb{Z})^*)\). (This notation means the number of things in the set \((\mathbb{Z}/k\mathbb{Z})^*\).)

Now define the set of pairs \[(\mathbb{Z} /n \mathbb{Z})^*\times(\mathbb{Z} /m \mathbb{Z})^*=\{(a,b)\mid a\in(\mathbb{Z} /n \mathbb{Z})^*\text{ and }b\in(\mathbb{Z} /n \mathbb{Z})^*\}\ .\] Notice that \(\#((\mathbb{Z} /n \mathbb{Z})^*\times(\mathbb{Z} / m \mathbb{Z})^*)=\#((\mathbb{Z}/n\mathbb{Z})^*)\cdot\#((\mathbb{Z} / m \mathbb{Z})^*)=\phi(n)\phi(m)\), since each part of the pair is free to be whichever element it wants of the respective set, so the total number of pairs is the size of the first set times the size of the second. Therefore, if we can prove that \((\mathbb{Z}/n\mathbb{Z})^*\times(\mathbb{Z}/m\mathbb{Z})^*\) can be put into bijective correspondence with \((\mathbb{Z}/(nm)\mathbb{Z})^*\), then we will have \[\phi(n)\phi(m)=\#\left((\mathbb{Z}/n\mathbb{Z})^*\times(\mathbb{Z}/m\mathbb{Z})^*\right)=\#((\mathbb{Z}/(nm)\mathbb{Z})^*)=\phi(nm)\] as desired, since bijective sets have the same number of elements.

The correspondence is given by the function \[\mathcal{F}:(\mathbb{Z}/(nm)\mathbb{Z})^*\to(\mathbb{Z}/n\mathbb{Z})^*\times(\mathbb{Z}/m\mathbb{Z})^*:[x]_{nm}\mapsto([x]_n,[x]_m)\ .\]

We must show \(\mathcal{F}\) is well-defined, 1-1, and onto. Well-defined means that for some \([x]_{nm}\), if \(y\in\mathbb{Z}\) is another representative of the congruence class \([x]_{nm}\), then \(([x]_n,[x]_m)=([y]_n,[y]_m)\) so that \(\mathcal{F}\) is defined only by the class \([x]_{nm}\), not by its choice of representative \(x\). But this is easy, since \(y\in[x]_{nm}\) means \(y\cong_{nm}x\) so \(\exists k\in\mathbb{Z}\) such that \(y-x=k(nm)=(km)n=(kn)m\). These last two versions mean that \(y\cong_nx\) and \(y\cong_mx\), so \([x]_n=[y]_n\) and \([x]_m=[y]_m\), which means \(\mathcal{F}\) is well-defined.

Now let us assume that \(x,y\in\mathbb{Z}\) have \(\mathcal{F}([x]_{nm})=\mathcal{F}([y]_{nm})\), i.e., \([x]_n=[y]_n\) and \([x]_m=[y]_m\). That is, \(z=x-y\in\mathbb{Z}\) solves the system \[\begin{aligned} z&\equiv 0\pmod{n}\\ z&\equiv 0\pmod{m}\ .\end{aligned}\] But \(z=0\) also solves this system, and the Chinese Remainder Theorem tells us that solutions of this system (which is an appropriate system for the CRT since \(\gcd(n,m)=1\)) are unique modulo \(nm\). Therefore, \(x-y\equiv0\pmod{nm}\), so \(x\equiv y\pmod{nm}\). Hence \([x]_{nm}=[y]_{nm}\), and thus \(\mathcal{F}\) is \(1-1\).

Now, given any pair \(([x]_n,[y]_m)\in(\mathbb{Z}/n\mathbb{Z})^*\times(\mathbb{Z}/m\mathbb{Z})^*\), consider the system of congruences \[\begin{aligned} z&\equiv x\pmod{n}\\ z&\equiv y\pmod{m}\ ,\end{aligned}\] which system is again CRT-ready since \(\gcd(n,m)=1\). Therefore there exists a solution to this system, call it \(z\in\mathbb{Z}\), and \(\mathcal{F}([z]_{nm})=([x]_n,[y]_m)\). Thus \(\mathcal{F}\) is onto as well.

Exercise \(\PageIndex{1}\)

1. Compute \(\phi(n)\) for \(n=2,3,5,7,11,13,17\). Make a general conjecture. Can you prove it?
2. Compute \(\phi(n)\) for \(n=2,4,8, 16, 32, 64\). Make a conjecture about \(\phi(2^k)\) for \(k\in\mathbb{N}\). Prove it!