If you know the order of $a$, you know the order of every power of $a$, with one gcd. This formula drives everything about cyclic groups.
Why it works
Look at the shape of that proof, because it recurs all course: turn the statement about the group into a divisibility statement with the order lemma ($a^{j} = e \iff n \mid j$), then finish with plain number theory. Nothing about the particular group was used, so the formula holds in $\mathbb{Z}_{n}$, in $U(n)$, for rotations, for matrices.
In $\mathbb{Z}_{n}$, where $k = k \cdot 1$ and $|1| = n$, the formula says the element $k$ has order $n/\gcd(n, k)$. Two consequences:
- $\langle a^{k} \rangle = \langle a^{\gcd(n, k)} \rangle$: both have $n/\gcd(n, k)$ elements, and $a^{k}$ is a power of $a^{\gcd(n,k)}$, so the first sits inside the second, with the same size.
- $a^{k}$ generates $\langle a \rangle$ exactly when $\gcd(n, k) = 1$; and $a^{i}$, $a^{j}$ generate the same subgroup exactly when $\gcd(n, i) = \gcd(n, j)$.
Worked example: A power in an abstract group
- $\gcd(30, 12) = 6$, so $|a^{12}| = 30/6 = 5$.
- $\gcd(30, 18) = 6$ too, so $|a^{18}| = 5$, and in fact $\langle a^{12} \rangle = \langle a^{18} \rangle = \langle a^{6} \rangle$.
- Check: $(a^{12})^{5} = a^{60} = (a^{30})^{2} = e$.
Answer: Both have order $5$. A group of order $30$ that is cyclic has exactly $\varphi(5) = 4$ elements of order $5$: $a^{6}, a^{12}, a^{18}, a^{24}$.
Worked example: Orders in $\mathbb{Z}_{36}$
- $\gcd(36, 27) = 9$, so $|27| = 36/9 = 4$: indeed $27, 54 \equiv 18, 45 \equiv 9, 36 \equiv 0$.
- $\gcd(36, 10) = 2$, so $|10| = 18$.
Answer: $|27| = 4$ and $|10| = 18$.
Worked example: Counting elements of a given order
- $|k| = 36/\gcd(36, k) = 12$ means $\gcd(36, k) = 3$.
- So $k = 3j$ with $\gcd(j, 12) = 1$ and $1 \le j \lt 12$: $j = 1, 5, 7, 11$.
- The elements are $3, 15, 21, 33$.
Answer: $\varphi(12) = 4$ elements.
Common mistake
Key idea