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?
Best Answer
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.