MaBloWriMo 14: Element orders are no greater than group size

Today we will give an answer to the question:

What is the relationship between the order of a group and the orders of its elements?

Yesterday, I claimed we would prove that for any element $g$ of a group $G$ , it is the case that $|g| \leq |G|$ , that is, the order of $g$ is no larger than the size of the group.

The proof is just a strengthened variant of the proof from yesterday, where we do a more careful job wielding the pigeonhole principle. Yesterday, we simply observed that if you have an infinite list containing only finitely many elements, there must be duplicates. But we can say something stronger. Again, recall that the infinite list we are talking about is

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

for some $g \in G$ . Suppose $G$ has order $n$ , and consider the first $n+1$ elements of the list: we have $n+1$ things with only $n$ possible values, so by the pigeonhole principle there must be (at least) two which are the same. In other words, yesterday we just noted that there have to be duplicates somewhere in the list; today, we are making the stronger statement that there must be duplicates within the first $n+1$ items.

Again, call the duplicates $g^j = g^k$ where $j < k$ . But this time we know that $k \leq n+1$ . By the same argument as yesterday, $e = g^{k-j}$ . But $k-j \leq n+1 - j \leq n$ (the second step is because $j \geq 1$ ). So the order of $g$ is at most $k-j$ , which is at most $n$ . Voila!

If you play around with a few examples, you might suspect that something even stronger is true, namely, that the order of an element actually has to be a divisor of the size of the group. For example, with $\mathbb{Z}_8$ we only get elements with orders $1$ , $2$ , $4$ , and $8$ . This turns out to be true, and is called Lagrange’s Theorem. Proving it requires quite a bit more machinery, and would probably require on the order of ten blog posts. I won’t go through it now since we don’t need it for our Lucas-Lehmer proof. But it is an extremely cool theorem and proof, so perhaps I’ll go through it later if there is interest.