A long long time ago, in a galaxy far away, I wrote up an account of the Euler-Fermat theorem for school students.
The Euler-Fermat theorem is the wonderful result of elementary number theory, which says that in modular arithmetic, you can often multiply a number by itself a certain number of times to get back to 1.
For instance, consider the integers modulo 14, i.e. remainders upon division by 14. Starting from the number 3, if we repeatedly multiply it by itself, i.e. we consider powers of 3, we obtain
\[
3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243, 3^6 = 729, …
\]
which reduce modulo 14 to (i.e. their remainders upon division by 14 are)
\[
3, 9, 13, 11, 5, 1, …
\]
Since, as we have just calculated, \( 3^6 \equiv 1 \) mod 14, this means that subsequent powers of 3 will reduce mod 14 to precisely the same numbers; they will continue to cycle around. For instance,
\[
3^7 = 3^6 \times 3 \equiv 1 \times 3 \equiv 3 \text{ mod } 14, \\
3^8 = 3^6 \times 3^2 \equiv 1 \times 9 \equiv 9 \text{ mod } 14, \\
3^9 = 3^6 \times 3^3 \equiv 1 \times 13 \equiv 13 \text{ mod } 14,
\]
and so on. The powers of 3 cycle around modulo 14, repeating the same 6 numbers.
So, the fact that \( 3^6 \equiv 1 \) mod 14 gives a very nice structure to powers of 3, modulo 14.
We can try the same thing starting from some different numbers — still working modulo 14, i.e. taking remainders upon division by 14.
If we do the same for powers of 5 modulo 14, we find the same thing: again \( 5^6 \equiv 1 \) mod 14, and the powers of 5 also repeat through 6 numbers.
With powers of 9 modulo 14, we find something similar, but not quite the same: here \( 9^3 \equiv 1 \) mod 14, so the powers of 9 form a cycle of length 3, repeating through 3 numbers.
With powers of 4 modulo 14, however, something goes wrong. Taking powers of 4, we never arrive back at 1 modulo 14. And if you think about it you can see why: 4 is even, hence so are all its powers. But a number congruent to 1 mod 14 must be odd, so this can never happen.
The same is true starting from 7. The powers of 7 are all divisible by 7, but a number congruent to 1 mod 14 must be 1 more than a multiple of 7.
In order to have a chance of arriving back at 1, with the powers cycling around, the number we start from must have no factors in common with 14. In other words, it must be relatively prime to 14.
The numbers 3, 5, 9 are all relatively prime to 14. And we found \( 3^6 \equiv 1 \) mod 14, \( 5^6 \equiv 1 \) mod 14, and \( 9^3 \equiv 1 \) mod 14. The power required is 6 in the first two cases and 3 in the other. But notice that 3 is a factor of 6, so in fact
\[
9^6 = (9^3)^2 \equiv 1 \text{ mod } 14
\]
as well. So starting from any of these numbers, its sixth power leaves a remainder of 1 modulo 14.
So now we arrive at a conjecture: if \( a \) is an integer relatively prime to 14, then \( a^6 \equiv 1 \) mod 14.
This conjecture turns out to be true. And in fact, something like it is true not just when we look modulo 14, but modulo any positive integer \( n \).
But as you might suspect, you don’t always raise numbers to the power 6. When you replace 14 by a general number \( n \), what do you replace the exponent 6 with?
The answer is, the Euler phi function \( \phi(n) \). Given a positive integer \( n \), we define \( \phi(n) \) as the number of positive integers less than \( n \) which are relatively prime to \( n \).
So, for instance, the positive integers less than 14 which are relatively prime to 14 are
\[
1, 3, 5, 9, 11, 13.
\]
There are six of these, so \( \phi(14)=6 \).
And so the Euler-Fermat theorem can be stated as follows.
THEOREM. For any positive integer \(n\) and any integer \( a \) relatively prime to \( n \),
\[
a^{\phi(n)} \equiv 1 \text{ mod } n.
\]
To really understand why this theorem is true, I think one should understand a little group theory. Just the first little bit of group theory.
And so, a long long time ago, in a galaxy far far away, I thought I would write up such a proof, introducing just as much group theory as one needs for it. The result is intended for talented high school students or interested members of the public.
Today, I rediscovered it. You can read it below!
Euler-Fermat-theorem