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

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.