## Four formats for Fermat: correction!

In my previous post I explained three variants on Fermat’s Little Theorem, as well as a fourth, slightly more general variant, which it turns out is often called Euler’s Totient Theorem. Here’s what I said:

If $n \geq 1$ and $a$ is any integer, then $a^{\varphi(n)} \equiv 1 \pmod n$.

However, this is wrong! We can easily find a counterexample. For example, let $n = 6$ and $a = 3$. Then $\varphi(6) = 2$, since there are only two numbers less than $6$ that are relatively prime to it (namely, $1$ and $5$; each of $2$, $3$, and $4$ shares a common factor with $6$). But then $a^{\varphi(n)} = 3^2 = 9$ which has a remainder of $3$, not $1$, when divided by $6$.

What’s wrong? It turns out I missed a small but important restriction: this is only true when $a$ is relatively prime to $n$. Note this is stronger than saying $a$ isn’t divisible by $n$; it says they cannot share any common factors at all. For example, $9$ is not divisible by $6$, but they share $3$ as a common factor, so this theorem does not apply (and indeed, $9^2 \equiv 3 \pmod 6$, not $1$).

For completeness, here’s a corrected statement of the theorem (I have also fixed the previous post):

If $n \geq 1$ and $a$ is any integer relatively prime to $n$, then $a^{\varphi(n)} \equiv 1 \pmod n$.

So what’s an example where this theorem does work? Let’s keep $n = 6$ but try $a = 5$ instead: now $a^{\varphi(6)} = 5^2 = 25 \equiv 1 \pmod 6$.

In my next post I’ll present a proof of Fermat’s Little Theorem.