# Prove that every element of a finite group has an order

I was reading Nielsen and Chuang's "Quantum Computation and Quantum Information" and in the appendices was a group theory refresher. In there, I found this question:

Exercise A2.1 Prove that for any element $g$ of a finite group, there always exists a positive integer $r$ such that $g^r=e$. That is, every element of such a group has an order.

My first thought was to look at small groups and try an inductive argument. So, for the symmetric groups of small order e.g. $S_1, S_2, S_3$ the integer $r$ is less than or equal to the order of the group. I know this because the groups are small enough to calculate without using a general proof.

For example, in $S_3$ there is an element that rearranges the identity $\langle ABC \rangle$ element by shifting one character to the left e.g. $s_1 = \langle BCA \rangle$. Multiplying this element by itself produces the terms $s_1^2 = \langle CAB \rangle$; and $s_1^3 = \langle ABC \rangle$ which is the identity element, so this element is equal to the order of the group, which is three.

I have no idea if this relation holds for $S_4$ which means I am stuck well before I get to the general case.

There's a second question I'd like to ask related to the first. Is the order or period of any given element always less than or equal to the order of the group it belongs to?

-
Consider the sequence $(g^n)_{n\in\mathbb N}$. It has infinitely many elements, so they can't all be different. Choose two equal elements with different $n$'s, and ... –  Henning Makholm Sep 14 '11 at 20:58
For the second question, yes -- a slight variant of the argument I hint at will show that the order of an element cannot be larger than the order of the group. –  Henning Makholm Sep 14 '11 at 21:01
What does $\langle A, B, C \rangle$ mean? Is the the bijection $A \mapsto B$, $B \mapsto C$, and $C \mapsto A$? –  William Sep 14 '11 at 21:07
@William Chan Yes. Supposing each denotes a vertex of a equilateral triangle on a plane, then this is a rotation. –  bwkaplan Sep 14 '11 at 21:10

Since the group is finite, it can not be the case that $g^n$ is different for all $n$. There must be $n_1$ and $n_2$ such that $g^{n_1} = g^{n_2}$ where $n_1 \neq n_2$ (unless $g = e$; ). Therefore, $g^{n_1 - n_2} = e$.

Yes, the order of an element is always less than or equal to the order of the group. In the proof above, assume $n_1$ and $n_2$ are all positive and that $n_1 < n_2$. Find the least such pair $n_1$ and $n_2$. If $n_1$ is greater than the order of the group, then that meant you saw at least $n_1$ different thing before seeing a repeat. But the group has only less than $n_1$ elements.

-
how can this work if the exponent is supposed to be positive? n1-n2 is surely negative since n1 < n2. –  Janus Troelsen Nov 16 at 12:49
Sometimes it is much clearer to argue the general case. Consider any $g \in G$, a finite group. Since $G$ is a group, we know that $g\cdot g = g^2 \in G$. Similarly, $g^n \in G$ for any $n$. So there is a sequence of elements,
$$g, g^2, g^3, g^4, g^5, \ldots, g^n, \ldots$$
in $G$. Now since $G$ is finite, there must be a pair of number $m \neq n$ such that $g^m = g^n$ (well, there are many of these, but that's irrelevant to this proof).
Can you finish the proof from this point? What does $g^m = g^n$ imply in a group?