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

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.

View all posts by Brent →