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


\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.
This entry was posted in algebra, group theory, modular arithmetic, number theory, proof and tagged , , , , , , , , , , . Bookmark the permalink.

1 Response to MaBloWriMo 22: the order of omega, part II

  1. Pingback: MaBloWriMo 23: contradiction! | The Math Less Traveled

Comments are closed.