Continuing our discussion of groups (see here and here), today I want to discuss the concept of order, which is defined both for groups themselves and for the elements of a group.

The order of a group simply means the size of the set . So instead of “a group with 8 elements” you will often hear “a group of order 8” instead.

Elements of a group also have an order. Recall the example , the group with elements , and with binary operation addition . Consider what happens if we start with and keep combining it with itself according to the group operation. , then , and so on, until we get to adding eight copies of , giving . If we add up copies of , on the other hand, it takes only copies to reach . What about ? Well, ; three copies yield ; four copies yield ; and so on. As you can verify, we actually need eight copies of before we get to .

In general, if is a group and is some element of the group, the order of is defined as the smallest number of copies of which combine to yield the identity element. So in , has order eight, has order four, also has order eight, and so on. itself has order 1, because one copy of is already .

A few questions immediately suggest themselves:

1. Does every group element have a well-defined order?
2. How does the order of group elements relate to the order of the group?

To answer the first question, recall that the integers form a group under addition, and obviously if you start with some nonzero integer , you can add to itself as many times as you like but you will never get zero! In such cases we say that the order is infinite.

OK, but the group itself has infinitely many elements. Let’s refine our question a bit:

1. (revised) Does every element of a finite group have a well-defined, finite order?

Even in a finite group, you could imagine having some element such that no matter how much you combine it with itself, you will never get the identity element. Can this happen? (Also, as a tangential challenge, can you come up with an example of an infinite group where some elements other than the identity do have a finite order?)

For now, I’ll let you think about these questions! Tomorrow, we’ll answer question 1; the next day, we’ll talk about a simple answer to question 2 which will be sufficient for our purposes (there is also a more nuanced answer which is harder to prove).

As an aside, remember that we’re trying to prove the Lucas-Lehmer test, and currently we’re trying to understand the related number . The point of all this stuff about groups is that (1) we’re going to construct a group containing as an element, and then (2) we’re going to figure out something about the order of in that group. We’ll see that if the Lucas-Lehmer test didn’t work, then the order of would be in contradiction to the answer to question 2.