## 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! 