Fermat–Euler Theorem

Fermat's Little Theorem (FLT) is an incredibly useful theorem in its own right. However, it only applies to prime bases, and "most" integers are certainly not prime. How can we generalize FLT to any integer base?

It is clear that simply stating $a^{n-1} \equiv 1 \pmod{n}$ if $(a,n)=1$ will not work here. As a simple counterexample, take $a=-1$ and $n=12$. Looking at why this doesn't work will give us a clue regarding how we should generalize FLT.

Recall the proof of FLT. If you trace through it, you will find that it works in almost exactly the same way ... until the very end: $$a^{p-1}(p-1)!\equiv (p-1)! \pmod{p}$$ In the very last step, we divide both sides of the congruence by $(p-1)!$ to obtain our final result: $$a^{p-1}\equiv 1 \pmod{p}$$ But if $n$ is not prime, then this no longer works! Think about why not before moving on.

For $n$ not prime, $(n-1)!\equiv 0 \pmod{n}$, meaning that $(n-1)!$ is definitely not relatively prime to $n$. Remember that, in general, you cannot divide in congruences unless the factor being removed on both sides is relatively prime to the base. For example, $$4\times 3\equiv 4\times 5\pmod{8}\rightarrow 3\equiv 5\pmod{8}$$ is not valid, because $4$ and $8$ are not relatively prime, but $$4\times 3\equiv 4\times 10\pmod{7}\rightarrow 3\equiv 10\pmod{7}$$ is valid, because $4$ and $7$ are relatively prime.

This gives us the clue we need. Instead of taking the set ${a, 2a, 3a, ..., (p-1)a}$, we need to take a set with all numbers relatively prime to $n$. How many positive integers less than or equal to $n$ are relatively prime to $n$? It's our familiar friend: Euler's totient function, $\phi(n)$! We are now ready to state Euler's Theorem:

If $(a,n)=1$, then: $$a^{\phi(n)}\equiv 1\pmod{n}$$

Our proof of Euler's Theorem will mimic that of FLT very closely. Let $x_1, x_2, ..., x_{\phi(n)}$ be all of the integers between $1$ and $n$, inclusive, that are relatively prime to $n$. Now, consider the set ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$. We will prove that this set is an abbreviated residue class modulo $n$, meaning that it contains every remainder relatively prime to $n$ exactly once.

It is clear that all of the elements in the set are relatively prime to $n$. Assume, for the sake of contradiction, that $ax_i\equiv ax_j \pmod{n}$ for $0\lt j\lt i\lt \phi(n)$. Then, $a(i-j)\equiv 0 \pmod{n}$, which is a contradiction, since $i-j$ is not a multiple of $n$. Therefore, all of the elements ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$ are distinct modulo $n$. Thus, since these $\phi(n)$ elements can only occupy $\phi(n)$ residue classes, each residue class must be occupied exactly once.

Since ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$ is an abbreviated residue class, it follows that: $$x_1a \times x_2a \times x_3a \times ... \times x_{\phi(n)}a \equiv x_1\times x_2\times x_3\times ... \times x_{\phi(n)} \pmod{p}$$ $$a^{\phi(n)}\prod_{i=1}^{\phi(n)}x_i\equiv \prod_{i=1}^{\phi(n)}x_i \pmod{p}$$ Since $\prod_{i=1}^{\phi(n)}x_i$ is relatively prime to $p$, we may divide by $\prod_{i=1}^{\phi(n)}x_i$ in the above congruence to obtain: $$a^{\phi(n)}\equiv 1 \pmod{n}$$ Thus, we have proved Euler's Theorem.