## MaBloWriMo 22: the order of omega, part II

Yesterday, from the assumption that $s_{n-2}$ is divisible by $M_n$, we deduced the equations

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

and

$\omega^{2^n} = 1$

which hold in the group $X^*$. So what do these tell us about the order of $\omega$? Well, first of all, the second equation tells us that the order of $\omega$ must be a divisor of $2^n$, and the only divisors of $2^n$ are other powers of $2$. So the order of $\omega$ must be $2^k$ for some $k \leq n$.

Now suppose the order of $\omega$ is $2^k$, so $\omega^{2^k} = 1$. But then if we square both sides we get $\omega^{2^{k+1}} = 1$. Squaring again gives $\omega^{2^{k+2}} = 1$, and so on. So once we hit $1$, we are stuck there: raising $\omega$ to all bigger powers of $2$ will also yield $1$.

But now look at the first equation: $\omega^{2^{n-1}} = q-1$. Remember that the order of $\omega$ has to be a power of $2$. From this equation we can see that the order can’t be $2^{n-1}$. Could it be a smaller power of two? In fact, no, it can’t, by the argument in the previous paragraph: once you hit a power of two that yields $1$, all the higher powers also have to yield $1$. So if $\omega$ raised to any smaller power of $2$ were the identity, then $\omega^{2^{n-1}}$ would also have to be the identity—but it isn’t.

The inescapable conclusion is that the only possibility for the order of $\omega$ is exactly $2^n$.

So, how does that help? Hint: think about the order of the group $X^*$… the triumphant conclusion tomorrow!