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 of a group , it is the case that , that is, the order of 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
for some . Suppose has order , and consider the first elements of the list: we have things with only 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 items.
Again, call the duplicates where . But this time we know that . By the same argument as yesterday, . But (the second step is because ). So the order of is at most , which is at most . 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 we only get elements with orders , , , and . 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.