MaBloWriMo 21: the order of omega, part I

Now we’re going to figure out the order of \omega in the group X^*.

Remember that we started by assuming that M_n passed the Lucas-Lehmer test, that is, that s_{n-2} is divisible by M_n. Remember that we also showed

s_m = \omega^{2^m} + \overline{\omega}^{2^m}

for all m \geq 0. In fact, this proof is valid in X^* too, if we take everything \pmod q. The proof deals only with \omega and \overline{\omega}, integers, and addition and multiplication. We know \omega and \overline{\omega} are in X^*, and we know that addition and multiplication can be interchanged with taking remainders. So what about integers like s_m? I claim that every nonzero integer (or, in particular, its remainder \pmod q) is in X^* as well, if q is prime.1 That is, for every integer a < q, there is some other integer x < q such that ax = 1 \pmod q. 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 a and b have a greatest common divisor d, then there exist integers x and y such that ax + by = d. In this case, if q is prime then any nonzero number less than q has a gcd of 1 with q. So by Bézout’s Identity for any a < q there are numbers x and y such that ax + qy = 1. Taken \pmod q, this says that ax = 1.

So our equation for s_m in terms of \omega and \overline{\omega} is valid as an equation in the group X^*; from here on all our equations will similarly “live in in X^*-world”. We have to take everything \pmod q though. In particular, If s_{n-2} is divisible by M_n, then s_{n-2} is also divisible by q (since q divides M_n), which means s_{n-2} = 0 in X^*. Hence

\omega^{2^{n-2}} + \overline{\omega}^{2^{n-2}} = 0.

Now we multiply both sides by \omega^{2^{n-2}}. First, multiplying \omega^{2^{n-2}} by itself results in an exponent of 2^{n-2} + 2^{n-2} = 2 \cdot 2^{n-2} = 2^{n-1}. For the other term, \overline{\omega}^{2^{n-2}} \omega^{2^{n-2}} = (\overline{\omega} \omega)^{2^{n-2}} = 1. We therefore now have

\omega^{2^{n-1}} + 1 = 0.

If we add q-1 to both sides, we get

\omega^{2^{n-1}} = q-1

(since 1 + (q-1) = q = 0 \pmod q).

Squaring both sides also gives us

\omega^{2^n} = 1.

(To see that (q-1)^2 = 1, you can either think of (q-1) as acting like -1, or if you like you can expand it out to q^2 - 2q + 1 = 1 \pmod q.)

Tomorrow we’ll see how to use some of the group properties we proved earlier to deduce from these equations the order of \omega.

  1. Aha! Here’s where we need q to be prime!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, group theory, modular arithmetic, number theory, proof and tagged , , , , , , , , , , . Bookmark the permalink.

2 Responses to MaBloWriMo 21: the order of omega, part I

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

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

Comments are closed.