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 and is any integer, then .

However, **this is wrong**! We can easily find a counterexample. For example, let and . Then , since there are only two numbers less than that are relatively prime to it (namely, and ; each of , , and shares a common factor with ). But then which has a remainder of , *not* , when divided by .

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

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

If and is any integer relatively prime to , then .

So what’s an example where this theorem *does* work? Let’s keep but try instead: now .

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

##
About Brent

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

Pingback: Four formats for Fermat | The Math Less Traveled

Pingback: Fermat’s Little Theorem: proof by modular arithmetic | The Math Less Traveled

Pingback: Euler’s Theorem: proof by modular arithmetic | The Math Less Traveled

Pingback: Fermat’s Little Theorem: proof by group theory | The Math Less Traveled