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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →