Firstly, apologies for the long gap. Very far from being Theorem of the Week, I know. Here’s another theorem for now, and I’ll do what I can to revert to a weekly post.
So, to this week’s theorem. I have previously promised to write about Fermat‘s Little Theorem, and I think it’s time to keep that promise. In that post (Theorem 10, about Lagrange’s theorem in group theory), I introduced the theorem, so I’m going to state it straightaway. If you haven’t seen the statement before, I suggest you look back at that post to see an example.
Theorem (Fermat’s Little Theorem) Let be a prime, and let be an integer not divisible by . Then .
If you aren’t comfortable with the notation of modular arithmetic, you might like to phrase the conclusion of the theorem as saying that divides . (I do encourage you to learn about modular arithmetic, though, because it’s incredibly helpful.)
The theorem can be presented in a slightly different (but equivalent) way. I’ll record that here, for convenience.
Theorem (Fermat’s Little Theorem, alternative statement) Let be a prime, and any integer. Then .
One important point to note. The name of this theorem is sometimes abbreviated to FLT, but it should not be confused with a rather more famous theorem with the same abbreviation!
Why are these equivalent?
In one direction, if , then, multiplying by , we have . That deals with the case that is not divisible by . If is divisible by , then and so certainly .
In the other direction, suppose that is not divisible by and that . Then the fact that is not divisible by means that has a multiplicative inverse . So we can cancel one from each side, to get .
The fact that these two statements are equivalent is supposed to be pretty easy. The important thing to remember that the first is true only if is not divisible by , whereas the second is true for all . But that should be reasonably easy to remember, just by thinking about it. (If , then it’s going to be difficult to make congruent to …)
I’d like to give outlines of three proofs of this theorem, since I think they are all interesting and have nice features.
The idea here is to exploit the fact that is prime, in the form that it means we can divide by numbers coprime to (numbers not divisible by ).
Let’s think about the numbers , , , …, . If we multiply them together, we get . (Here, means factorial.)
But we know more about these numbers. They are all different, . Indeed, if , then , because we can “cancel the ” (because it’s coprime to ). So we have numbers, all different, and none of them is . So they must be congruent to , , , …, in some order. So their product is congruent to .
We now have two expressions for this product, so we can equate them. We have . Now is coprime to , so we can again cancel, to give — and that’s exactly what we wanted!
I’m not going to write out this proof in detail, but I’ll describe the ideas. The main idea is to use induction on to prove that . This is easy for , the base case, and it’s also pretty easy for . The interesting bit is to justify the induction step, so let’s think about that.
We’re allowed to suppose that , and we want to deduce that . We can expand , using the binomial theorem. We get , together with a bunch of terms of the form , with . It turns out that if then the binomial coefficient is divisible by . I think I’m going to leave this as an exercise; it’s a nice problem, and not too hard. Using this fact, we now have . But our induction hypothesis tells us that , so we have , and that completes the proof of the induction step.
The third proof I’d like to mention uses Lagrange’s theorem (a result about groups). I described that proof in my previous post about that theorem (link in the last sentence), so I think I’ll point readers there and not say any more here.
Generalisation and applications
One very natural question to ask now is: what happens if isn’t prime? It turns out that the result as stated isn’t true if is prime (think of an example!). But one can come up with an analogous result. I think that Proofs 1 and 3 above generalise most naturally, and if you think about it for a bit you can use these arguments to see what the result should be. The result is often called the Fermat-Euler theorem. I’ll state it here, and leave the proof as an exercise (try to generalise proofs 1 and 3 above).
Theorem (Fermat-Euler) Let be an integer greater than 1, and let be an integer coprime to . Let denote the number of positive integers less than that are coprime to (see below for more about ). Then .
The function is called the Euler totient function, or the Euler phi function, and it is extremely useful in number theory. It has many interesting properties. Quick example: , because there are 4 positive integers less than 12 that are coprime to 12 (namely 1, 5, 7, and 11).
Notice that if is prime, then this theorem is exactly Fermat’s Little Theorem, because if is prime then (I’ll let you check that!).
Applications. Fermat’s Little Theorem and the Fermat-Euler Theorem are very useful, both in number theory and in applications to the outside world (such as cryptography). But I think this post is long enough now, so I shan’t say more about that: I’ll let you enjoy the results on their own merits!
Any introduction to number theory should talk about these results. As usual, I’d like to plug Davenport’s The Higher Arithmetic. No doubt there are also loads of online resources that are good too.