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!

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