MaBloWriMo 15: One more fact about element orders

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 $g \in G$ and we happen to know that $g^n$ is the identity. What can we say about the order of $g$ ? Well, we don’t know that the order is $n$ , because the order is defined to be the smallest power of $g$ that yields the identity. But we certainly do know that $n$ is an upper bound for the order of $g$ , that is, $|g| \leq n$ .

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

The proof is simple. Recall again our infinite sequence

$g, g^2, g^3, g^4, \dots$

Eventually $e$ must occur for the first time, say $g^k = e$ . But what happens after that? Well, if $g^k = e$ then we can combine both sides with $g$ to conclude $g^{k+1} = g$ , and then $g^{k+2} = g^2$ , and generally $g^{k+j} = g^j$ , until $g^{2k} = g^{k+k} = e$ again. Then $g^{2k+1} = g$ … and the cycle repeats. So we can see that the infinite sequence $g, g^2, g^3, g^4, \dots$ must be periodic, with a period equal to the order of $g$ . (The period cannot be smaller than the order of $g$ —can you see why? Hint: think about our proofs from the past few days.)

So this means that if $|g| = k$ , every $k$ th element—and only every $k$ th element—of this sequence is equal to $e$ . Put another way, $g^{km} = e$ for every $m \geq 1$ , and these are the only ones. So if we find some $n$ such that $g^n = e$ , it must be the case that $n = km$ for some $m \geq 1$ —which is another way of saying that $n$ is divisible by the order of $g$ .

You might be wondering how this relates to what I said yesterday— that the order of $g$ 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, $\mathbb{Z}_8$ (the first $8$ natural numbers with the operation being addition $\pmod 8$ ), it is easy to see that combining any element with itself $8$ times will yield $0$ (adding $x$ to itself $8$ times yields $8x$ , which is obviously divisible by $8$ , and hence equal to $0 \pmod 8$ ). So according to what we just proved above, the order of every element must be a divisor of $8$ , which is the size of the group. So we have just proved that the order of every element of $\mathbb{Z}_8$ 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

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

View all posts by Brent →