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.