It’s time for our third and final proof of Fermat’s Little Theorem, this time using some group theory. This proof is probably the shortest—explaining this proof to a professional mathematician would probably take only a single sentence—but requires you to know some group theory as background. Fortunately I’ve written about the relevant group theory before, so I will link to the relevant posts if you want to read up on the background.
This time we’re going to prove statement 1:
If is prime and is an integer where , then .
Consider the set . I claim that this set forms a group under the operation of multiplication . To verify this we need to check several things:
- First, we need to check that the set is closed under the given operation, that is, if we start with two elements from and multiply them , we will end up with an element in again. If we reduce the product , we will definitely get something less than ; so the real question is why we will never get . This is because if and is prime, then neither nor is divisible by , and hence neither is .
- We need to check that this operation is associative—and indeed, multiplication is associative.
- There needs to be an identity element, and there is: .
- Finally, every element must have a multiplicative inverse, that is, for any , there must be some such that . But we already know this is true (this also came up when proving two of the statements of Fermat’s Little Theorem equivalent).
So is a group under the operation of multiplication , and it has elements, that is, its order is . But by Lagrange’s Theorem, the order of each element evenly divides the order of the group. So let and suppose has order , that is, . Then divides , that is, there is some such that . Then .
It is also easy to generalize this proof to a proof of Euler’s Theorem; I will leave it to interested readers to fill in the details. Recall that Euler’s Theorem says that if is any integer and is relatively prime to , then . Consider the set of all positive integers which are relatively prime to . This also forms a group under the multiplication , and hence any element raised to the order of the group () results in the identity element ().
There are many more proofs of Fermat’s Little Theorem, but this has been a representative sampling! In future posts, I’m going to explore the mathematics behind several computational tests for primality, most of which end up relying on Fermat’s Little Theorem in one way or another.