## MaBloWriMo 12: Groups and Order

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 $G$. 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 $\mathbb{Z}_8$, the group with elements $\{0, 1, \dots, 7\}$, and with binary operation addition $\pmod 8$. Consider what happens if we start with $1$ and keep combining it with itself according to the group operation. $1 +_8 1 = 2$, then $1 +_8 1 +_8 1 = 3$, and so on, until we get to adding eight copies of $1$, giving $1 +_8 \dots +_8 1 = 0$. If we add up copies of $2$, on the other hand, it takes only $4$ copies to reach $0$. What about $3$? Well, $3 +_8 3 = 6$; three copies yield $1$; four copies yield $4$; and so on. As you can verify, we actually need eight copies of $3$ before we get to $0$.

In general, if $G$ is a group and $g \in G$ is some element of the group, the order of $g$ is defined as the smallest number of copies of $g$ which combine to yield the identity element. So in $\mathbb{Z}_8$, $1$ has order eight, $2$ has order four, $3$ also has order eight, and so on. $0$ itself has order 1, because one copy of $0$ is already $0$.

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 $n$, you can add $n$ 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 $\mathbb{Z}$ 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 $g \in G$ 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 $\omega = 2 + \sqrt{3}$. The point of all this stuff about groups is that (1) we’re going to construct a group containing $\omega$ as an element, and then (2) we’re going to figure out something about the order of $\omega$ in that group. We’ll see that if the Lucas-Lehmer test didn’t work, then the order of $\omega$ would be in contradiction to the answer to question 2. 