In my previous post I mentioned Fermat’s Little Theorem, a beautiful, fundamental result in number theory that underlies lots of things like public-key cryptography and primality testing. (It’s called “little” to distinguish it from his (in)famous Last Theorem.) There are several different forms in which it is commonly presented, so I wanted to start by introducing them and showing how they are related.
Let’s start with the statement that looks the least general:
If is prime and is an integer where , then .
(Recall that means that and have the same remainder when you divide them by .) For example, is prime, and we can check that for each , if you raise to the th power, you get a number which is one more than a multiple of :
Here’s a second variant of the theorem that looks slightly more general than the first:
If is a prime and is any integer not divisible by , then .
This looks more general because can be any integer not divisible by , not just an integer between and . As an example, let . Then .
We can see that (2) is more general than (1), since if then it is certainly the case that is not divisible by . Hence (2) implies (1). But actually, it turns out that (1) implies (2) as well!
Here’s a proof: let’s assume (1) and use it to show (2). In order to show (2), we have to show that whenever is prime and is any integer not divisible by . So let be an arbitrary prime and an arbitrary integer not divisible by . Then by the Euclidean division theorem, we can write in the form , where is the quotient when dividing by , and is the remainder. can’t actually be , since we assumed is not divisible by . Hence , so (1) applies and we can conclude that . But notice that (since is more than a multiple of ), and hence as well.
So although (2) “looks” more general than (1), the two statements are in fact logically equivalent.
Here’s another version which seems to be yet more general, since it drops the restriction that can’t be divisible by :
If is prime and is any integer, then .
Notice, however, that the conclusion is different: rather than .
As an example, let and again. Then , that is, the remainder of when divided by is . As another example, if , then since both are divisible by .
Once again, although this seems more general, it turns out to be equivalent to (1) and (2).
First of all, to see that (2) implies (3), suppose is prime and any integer. If is divisible by , then and clearly . On the other hand, if is not divisible by , then (2) applies and we may conclude that ; multiplying both sides of this equation by yields .
Now, to see that (3) implies (2), let be a prime and any integer not divisible by . Then (3) says that ; we wish to show that . However, since is not divisible by we know that has a multiplicative inverse , that is, there is some such that . (I have written about this fact before; it is a consequence of Bézout’s Identity.) If we take and multiply both sides by , we get to cancel one from each side, yielding as desired.
The final form is the most general yet: it even drops the restriction that be prime.
If and is any integer relatively prime to , then .
[The first version of this post accidentally omitted the phrase “relatively prime to ” from the above statement, rendering it false; here’s my later post explaining and correcting the error.]
is the Euler totient function, i.e. the number of positive integers less than which are relatively prime to . For example, since there are four positive integers less than which have no factors in common with : namely, , , , and .
We can see that (4) implies (2), since when is prime, (since every integer in is relatively prime to ). None of (1), (2), or (3) directly imply (4)—so it is, in fact, a bit more general—but we can generalize some of the proofs of these other facts to prove (4).