Euler's Totient Theorem

Recall from the Euler's Totient Function page that if $n \in \mathbb{N}$ then $\phi (n)$ denotes the number of positive numbers less than or equal to $n$ that are relatively prime to $n$, and this function $\phi$ is called Euler's totient function.

We made note of some important properties of this function including:

• If $p$ is a prime number then $\phi (p) = p - 1$.

• If $p$ is a prime number then $\phi (p^2) = p^2 - p$.

• If $p$ is a prime number and $k \in \mathbb{N}$ then $\phi (p^k) = p^k - p^{k-1} = (p - 1)p^{k-1}$.

• If $p$ and $q$ are distinct prime numbers then $\phi (pq) = \phi (p) \phi (q)$.

We are about to look at a very nice theorem known as Euler's totient theorem but we will first need to prove a lemma.

Lemma 1: Let $a, m \in \mathbb{N}$. If $(a, m) = 1$ and if $r_1, r_2, ..., r_{\phi(m)}$ are the $\phi(m)$ many positive integers less than or equal to $m$ and relatively prime to $m$, then the least residues of $ar_1, ar_2, ..., ar_{\phi(m)}$ modulo $m$ are a permutation of $r_1, r_2, ..., r_{\phi(m)}$.

• Proof: Let $r_1, r_2, ..., r_{\phi(m)}$ be as described above and suppose that $ar_i \equiv ar_j \pmod m$ for some $i, j \in \{ 1, 2, ..., \phi(m) \}$. Since $(a, m) = 1$ we have that then $r_i \equiv r_j \pmod m$. But $r_i, r_j \in \{ 1, 2, ..., m - 1 \}$ and so $r_i = r_j$. So $ar_i = ar_j$.

• So each of $ar_1, ar_2, ..., ar_{\phi(m)}$ is distinct modulo $m$ and there are $\phi(m)$ of such numbers, each of which must be congruence to some $r_1, r_2, ..., r_{\phi(m)}$ modulo $m$ since $(a, m) = 1$ to which there are also $\phi (m)$ such values. So the least residues of $ar_1, ar_2, ..., ar_{\phi(m)}$ modulo $m$ are a permutation of $r_1, r_2, ..., r_{\phi(m)}$. $\blacksquare$

• Proof:

Theorem 2 (Euler's Totient Theorem): Let $a, m \in \mathbb{N}$. If $(a, m) = 1$ then $a^{\phi(m)} \equiv 1 \pmod m$.

• Proof: Since $(a, m) = 1$ we have by Lemma 1 that:

(1)

\begin{align} \quad (ar_1)(ar_2)...(ar_{\phi(m)}) & \equiv r_1r_2...r_{\phi(m)} \pmod m \\ \quad a^{\phi(m)}(r_1r_2...r_{\phi(m)}) & \equiv r_1r_2...r_{\phi(m)} \pmod m \end{align}

• Since $(r_i, m) = 1$ by definition for each $i \in \{ 1, 2, ..., \phi(m) \}$ we have that $(r_1r_2...r_{\phi(m)}, m) = 1$, and so:

(2)

\begin{align} \quad a^{\phi(m)} \equiv 1 \pmod m \quad \blacksquare \end{align}

Notice that Euler's Theorem is a generalization of Fermat's Little Theorem. We prove this as a corollary.

Corollary 3 (Fermat's Little Theorem): Let $a, p \in \mathbb{N}$, $p$ be a prime, and $(a, p) = 1$. Then $a^{p-1} \equiv 1 \pmod m$.

• Proof: Since $(a, p) = 1$ we can apply Theorem 2 to get:

(3)

\begin{align} \quad a^{\phi(p)} & \equiv 1 \pmod p \\ \quad a^{p-1} & \equiv 1 \pmod p \quad \blacksquare \end{align}