In number theory the order of $a$ mod $n$ was the first power of $a$ that is $1$. The same idea works in every group, and it is the most useful single number attached to an element.
Definition. The order of $a$, written $|a|$, is the least positive integer $n$ with $a^{n} = e$. If no such $n$ exists, $a$ has infinite order. In additive notation the condition reads $na = a + a + \cdots + a = 0$.
Here $a^{n}$ means $a$ multiplied by itself $n$ times, $a^{0} = e$, and $a^{-n} = (a^{-1})^{n}$; the usual rules $a^{m}a^{n} = a^{m+n}$ and $(a^{m})^{n} = a^{mn}$ hold in any group (by associativity), while $(ab)^{n} = a^{n}b^{n}$ needs $ab = ba$.
Why it works
Proof. If $k = nq$ then $a^{k} = (a^{n})^{q} = e^{q} = e$. Conversely, suppose $a^{k} = e$ and divide: $k = nq + r$ with $0 \le r < n$. Then $$e = a^{k} = (a^{n})^{q}a^{r} = a^{r}.$$ Since $n$ is the least positive exponent giving $e$ and $0 \le r < n$, we must have $r = 0$, so $n \mid k$. $\square$ Consequence: $a^{i} = a^{j}$ exactly when $i \equiv j \pmod{n}$, so exponents can be reduced mod $|a|$. In particular the powers $e, a, a^{2}, \dots, a^{n-1}$ are all different: if two of them agreed, a smaller positive power would already be $e$.
Worked example: Order in $\mathbb{Z}_{16}$
- We need the least $m \ge 1$ with $6m \equiv 0 \pmod{16}$, that is, $16 \mid 6m$, that is, $8 \mid 3m$.
- Since $\gcd(8, 3) = 1$, this means $8 \mid m$.
- Check by adding: $6, 12, 2, 8, 14, 4, 10, 0$: eight steps.
Answer: $|6| = 8$.
Worked example: Order in $U(10)$
- Powers: $3^{1} = 3$, $3^{2} = 9$, $3^{3} = 27 \equiv 7$, $3^{4} = 21 \equiv 1$.
Answer: $|3| = 4$, which equals $|U(10)|$, so the powers of $3$ fill $U(10)$.
Worked example: A matrix of finite order
- $A^{2} = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} = -I$, the rotation by $180^\circ$.
- $A^{4} = (A^{2})^{2} = I$, and no smaller power is $I$.
- Then, for example, $A^{103} = A^{103 \bmod 4} = A^{3}$.
Answer: $|A| = 4$.
Common mistake
Key idea