Definition
Given an integer \(n\). Euler's totient function is a function that counts the positive integers up to \(n\) that are relatively prime to \(n\). It is denoted with \(\phi(n)\).

Alternatively, it is the the number of integers \(k\) in the range \(1 \leq k \leq n\) for which \(\gcd(n,k)=1\).

Example

Take \(n = 9\). The numbers \(1,2,4,5,7\) and \(8\) are relatively prime to \(9\) while \(3,6\) and \(9\) are not. Therefore \(\phi(9) = 6\).

\(\phi(p)\) when \(p\) is prime

Observe that when when \(p\) is prime, then \(1\) and \(p\) are the only divisors of \(p\). Therefore \(\phi(p) = 2\) for any prime \(p\). What about prime powers? Suppose \(p\) is prime. What is \(\phi(p^k)\)? We know that any multiple of \(p\) is not coprime to \(p^k\). The multiples of \(p\) are

$$ \begin{align*} &1, p, 2p, 3p, 4p, \ldots, (p^{k-1})p. \\ \end{align*} $$

We have exactly \(p^{k-1}\) numbers that are not coprime to \(p^k\). Hence

$$ \begin{align*} \phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1). \end{align*} $$

\(\phi(p)\) is Multiplicative

Theorem
Given integers \(m\) and \(n\). If \(\gcd(m,n) = 1\), then $$ \begin{align*} \phi(mn) = \phi(m)\phi(n) \end{align*} $$

Proof

Let

$$ \begin{align*} \mathbb{Z}_n &= \{0,1,2,\ldots,n-1\} \\ \mathbb{Z}_n^* &= \{k \in \mathbb{Z}_n \mid \gcd(k,n) = 1\} \\ \end{align*} $$

Observe that by definition of the group of units above, \(|\mathbb{Z}_{n}^*| = \phi(n)\). Now, the goal of this proof is to find a bijection such that

$$ \begin{align*} f: \mathbb{Z}_{nm}^* &\rightarrow \mathbb{Z}_m^* \times \mathbb{Z}_n^* \\ f(k) &= (k \bmod{m}, k \bmod{n}) \end{align*} $$

If we show that \(f\) is a bijection, then this implies that

$$ \begin{align*} |\mathbb{Z}_{nm}^*| &= |\mathbb{Z}_{m}^* \times \mathbb{Z}_{n}^*| \\ |\mathbb{Z}_{nm}^*| &= |\mathbb{Z}_{m}^*| \times |\mathbb{Z}_{n}^*| \\ \phi(nm) &= \phi(m)\phi(n). \end{align*} $$

which is what we want to show. Then, first we need to show that \(f\) is well-defined. This mean no matter what we choose as a representative of a residue class \([k]_{mn}\) or \([l]_{mn}\), then \(f\) will give us back the same element in the co-domain of \(f\). So suppose that we have

$$ \begin{align*} k \equiv l \pmod{mn} \end{align*} $$

Then we want to show that

$$ \begin{align*} f(k) = f(l) \quad \text{ and } \quad f(k) \in \mathbb{Z}_m^* \times \mathbb{Z}_n^* \end{align*} $$

But if \(k \equiv l \pmod{mn}\), then \(mn \mid k - l\). This implies that \(m \mid k - l\) and \(n \mid k - l\). That is

$$ \begin{align*} k &\equiv l \pmod{n} \\ k &\equiv l \pmod{m} \end{align*} $$

Thus, \(k \equiv l \pmod{m}\) and \(k \equiv l \pmod{n}\) which means that

$$ \begin{align*} (k \bmod{m}, k \bmod{n}) &= (l \bmod{m}, l \bmod{n}) \\ f(k) &= f(l) \end{align*} $$

Next, we need that \(f(k)\) is inside the co-domain. Since \(k \in \mathbb{Z}_{nm}^*\), then we know that \(\gcd(k,mn) = 1\). But this also implies that \(\gcd(k,m)=\gcd(k,n)=1\). Why? Suppose not, then let \(\gcd(k,m)=s\). But this means that \(s\) is common factor of \(k\) and \(m\) so \(\gcd(k,mn)\) is at least \(s\) and that’s not possible. Therefore, \(k \in \mathbb{Z}_{m}^*\) and \(k \in \mathbb{Z}_{n}^*\).

Next, we want to show that \(f\) is \(1-1\). So let \(a, b \in \mathbb{Z}_{nm}^*\). Then, we know that \(\gcd(a,mn) = 1\) and \(\gcd(b, mn) = 1\). Now, suppose \(f(a) = f(b)\). We will show that \(a = b\). Since \(f(a) = f(b)\), then

$$ \begin{align*} (a \bmod{m}, a \bmod{n}) &= (b \bmod{m}, b \bmod{n}) \end{align*} $$

But this just means that

$$ \begin{align*} a &\equiv b \pmod{m} \\ a &\equiv b \pmod{n} \end{align*} $$

Since by assumption \(\gcd(m,n) = 1\), then the Chinese Remainder Theorem guarantees that the pair of congruences above has a unique solution modulo \(mn\). That is

$$ \begin{align*} a &\equiv b \pmod{mn} \end{align*} $$

Hence, \(a\) and \(b\) are in the same residue class modulo \(\mathbb{Z}_{mn}^*\) so \(f\) is injective.

Next we want to show that \(f\) is surjective. So let \((a,b) \in \mathbb{Z}_{m}^* \times \mathbb{Z}_{n}^*\). We want to show that there is a \(k \in \mathbb{Z}_{mn}^*\) such that \(f(k) = (a,b)\). That is

$$ \begin{align*} (k \bmod{m}, k \bmod{n}) &= (a \bmod{m}, b \bmod{n}) \\ \end{align*} $$

or

$$ \begin{align*} k &\equiv a \pmod{m} \\ k &\equiv b \pmod{n} \end{align*} $$

But this has a solution modulo \(mn\) by CRT since \(\gcd(m,n)=1\). Then we know that \(k \in \mathbb{Z}_{mn}\). But we still need to show that \(k \in \mathbb{Z}_{mn}^*\). That is, \(\gcd(k, mn) = 1\). Observe that since \(\gcd(a, m) = 1\) and since \(k \equiv a \bmod{m}\), then we must also have that \(\gcd(k,m) = 1\). Similarly, since \(\gcd(b,n) = 1\) and since \(k \equiv b \pmod{n}\), then \(\gcd(k,n)=1\). Finally, since \(\gcd(k,m) = 1\) and since \(\gcd(k,n) = 1\), then we must have that \(\gcd(k,mn) = 1\). Therefore, \(f\) is surjective.

References

  • Wikipedia
  • Number Theory by George E. Andrews
  • Math310 Class Notes by Matthias Beck