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.
This entry was posted in number theory, primes and tagged , , , , , , . Bookmark the permalink.