Now we’re going to figure out the order of in the group .
for all . In fact, this proof is valid in too, if we take everything . The proof deals only with and , integers, and addition and multiplication. We know and are in , and we know that addition and multiplication can be interchanged with taking remainders. So what about integers like ? I claim that every nonzero integer (or, in particular, its remainder ) is in as well, if is prime.1 That is, for every integer , there is some other integer such that . This is because of something called Bézout’s Identity (which I should probably prove in another post, for completeness; it is not hard to prove): if and have a greatest common divisor , then there exist integers and such that . In this case, if is prime then any nonzero number less than has a gcd of with . So by Bézout’s Identity for any there are numbers and such that . Taken , this says that .
So our equation for in terms of and is valid as an equation in the group ; from here on all our equations will similarly “live in in -world”. We have to take everything though. In particular, If is divisible by , then is also divisible by (since divides ), which means in . Hence
Now we multiply both sides by . First, multiplying by itself results in an exponent of . For the other term, . We therefore now have
If we add to both sides, we get
Squaring both sides also gives us
(To see that , you can either think of as acting like , or if you like you can expand it out to .)
Tomorrow we’ll see how to use some of the group properties we proved earlier to deduce from these equations the order of .
Aha! Here’s where we need to be prime!↩