I almost forgot, but there is one more fact about the order of elements in a group that we will need. Suppose we have some and we happen to know that is the identity. What can we say about the order of ? Well, we don’t know that the order is , because the order is defined to be the *smallest* power of that yields the identity. But we certainly do know that is an upper bound for the order of , that is, .

The fact I want to prove today is that we can actually say more: if , then the order of must *be a divisor of* . (Note that counts as a divisor of itself.)

The proof is simple. Recall again our infinite sequence

Eventually must occur for the first time, say . But what happens after that? Well, if then we can combine both sides with to conclude , and then , and generally , until again. Then … and the cycle repeats. So we can see that the infinite sequence must be *periodic*, with a period equal to the order of . (The period cannot be *smaller* than the order of —can you see why? Hint: think about our proofs from the past few days.)

So this means that if , every th element—and *only* every th element—of this sequence is equal to . Put another way, for every , and these are the only ones. So if we find some such that , it must be the case that for some —which is another way of saying that is divisible by the order of .

You might be wondering how this relates to what I said yesterday— that the order of must evenly divide the size of the group, but that this is harder to prove. In the particular example group we have been looking at, (the first natural numbers with the operation being addition ), it is easy to see that combining any element with itself times will yield (adding to itself times yields , which is obviously divisible by , and hence equal to ). So according to what we just proved above, the order of every element must be a divisor of , which is the size of the group. So we have just proved that the order of every element of must divide the order of the group. But I claimed this was hard to prove! What gives?

Well, as you can see, there are some *particular* groups where it is not hard to prove. But we used more than just the laws of a group in our proof—we used things we already know about adding and modular arithmetic. If you want to prove that this is true for *all* groups, you have to show that it follows from *only* the group laws, without making any other assumptions. And that is still hard.

##
About Brent

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

Pingback: MaBloWriMo 22: the order of omega, part II | The Math Less Traveled