In 1763, Euler studied the function $\varphi(n)$ (the symbol $\varphi$ came later, with Gauss): the number of numbers from 1 to $n$ that have no common factor with $n$. For example, $\varphi(10) = 4$, because from 1 to 10 only 1, 3, 7 and 9 are suitable. He proved that if $a$ did not has a common factor with $n$, so

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

See the idea with $n = 10$ and $a = 3$. Multiply the numbers 1, 3, 7 and 9 by 3:

$$3 \cdot 1 = 3, \quad 3 \cdot 3 = 9, \quad 3 \cdot 7 = 21 \equiv 1, \quad 3 \cdot 9 = 27 \equiv 7 \pmod{10}.$$
On the 10 hour clock, multiplying by 3, 7 or 9 only shuffles the numbers 1, 3, 7 and 9.

The remainders are 3, 9, 1 and 7: the same four numbers, just shuffled. So their product is same:

$$(3 \cdot 1)(3 \cdot 3)(3 \cdot 7)(3 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}$$ $$3^4 \cdot (1 \cdot 3 \cdot 7 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}.$$

As $1 \cdot 3 \cdot 7 \cdot 9$ has no common factor with 10, it can be canceled on both sides: $3^4 \equiv 1 \pmod{10}$. Check: $3^4 = 81$, which leaves a remainder 1 when divided by 10. The same argument works for any $n$ and any $a$ with no common factor with $n$.

When $n$ is prime, $\varphi(n) = n - 1$ and the theorem becomes Fermat’s little theorem. More than 200 years later, in 1977, Euler’s theorem became the basis of RSA, the encryption system that protects internet purchases and cell phone messages.

All topics by Leonhard Euler · ← Fermat’s number that was not prime · Other contributions and legacy →

Credits and sources of images.