Now we’re going to figure out the order of in the group .

Remember that we started by assuming that passed the Lucas-Lehmer test, that is, that is divisible by . Remember that we also showed

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. 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

(since ).

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 .

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Pingback: MaBloWriMo 22: the order of omega, part II | The Math Less Traveled

Pingback: MaBloWriMo 24: Bezout’s identity | The Math Less Traveled