In my last post I explained the first proof of Fermat’s Little Theorem: in short, and hence . Today I want to show how to generalize this to prove Euler’s Totient Theorem, which is itself a generalization of Fermat’s Little Theorem:
If and is any integer relatively prime to , then .
Remember that is the function that tells us how many positive integers less than are relatively prime to (share no common factors with) . So, for example, suppose and . There are four positive integers among which are relatively prime to (namely, , , , and ), so the theorem says we should have , which we can verify: .
Once again, we start by considering the set of multiples of up to :
However, in this more general context we don’t want to use all of them! Our proof of Fermat’s Little Theorem relied on the fact that if (here, ) is prime, then none of have any factors in common with it. But if is not prime that may no longer be true. So, instead of the set above, we will look at the set of multiples of which are relatively prime to . Since we already assumed is relatively prime to , this is equivalent to saying we want multiples where is relatively prime to :
( is another way to say that and are relatively prime: they share no factors in common if and only if they have no nontrivial common divisor, that is, their greatest common divisor is .) Note that : the number of things relatively prime to between and is exactly what counts.
As an example, suppose and . The only multiples of which are relatively prime to are
If we take these , we get
and hey, look at that—it’s the numbers relatively prime to again, just in a different order! As another example, suppose and . The numbers relatively prime to are , and we can check that
So the claim is that if we start with all the numbers relatively prime to , multiply them all by , and then take their remainders , we get back the same set we started with (though quite possibly in a different order). More formally, let be the set of numbers relatively prime to . Then the claim is that
where multiplying a number by a set, like , means to multiply each element of the set by the given number.
The proof of this claim starts out quite similar to the proof from last time. First, suppose there are two multiples of , say, and , which have the same remainder when divided by . We can write this as . Subtracting from both sides and factoring out , we find that , that is, is divisible by . By assumption, is relatively prime to , so the only way for this to be true is if is divisible by , but since and are less than , the only way for this to happen is if , that is, . So this means that if we start with different multiples of , we get different remainders out.
However, this isn’t enough—this time we actually care about which remainders we get. We have to prove that if we start with only those multiples which are relatively prime to , we get exactly the same remainders out. So far, we haven’t used the fact that and are relatively prime to at all. Indeed, if we take all multiples of , we still end up with each remainder only once:
However, you’ll see later why we specifically want only the remainders which are relatively prime to .
So, assuming is relatively prime to , consider the remainder we get after dividing by . So, is more than some multiple of , that is, . We want to show that is relatively prime to . If had a factor in common with , then the whole right-hand side would be divisible by (because a sum of multiples of is also a multiple of ). But then the left-hand side, , would be divisible by also, but neither nor can be divisible by , since both are relatively prime to . Hence in fact has no factors in common with .
We’re almost done now. We start with the equation
and, just like last time, we now multiply together everything on the left and everything on the right. On the left we can factor out copies of , and this leaves us with
where means to take the product of all the elements in a set. Finally, we can see why it was important that we only took multiples of which are relatively prime to : this means the product shares no common factors with , which means we can divide by it on both sides, concluding that
If we had instead used the multiples of as before, we would end up with
which is a valid equation, but the problem is we are stuck here: dividing both sides by would not result in a valid modular equation, since shares one or more common factors with when is not prime.