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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →