Cyclic Groups and Generators

In this lesson you’ll learn what makes a group cyclic, how to find the order of an element, which elements generate a cyclic group, and the classification theorem that says there is essentially only one cyclic group of each size.

The order of an element $a$, written $|a|$, is the smallest positive integer $n$ with

$$a^n = e$$

If no such $n$ exists, $a$ has infinite order.

In $\mathbb{Z}_{12}$, the element $3$ has order 4, because $3 + 3 + 3 + 3 = 12 \equiv 0$ and no smaller count reaches $0$. In $(\mathbb{Z}, +)$, every nonzero element has infinite order, since no number of copies of $5$ ever sums to $0$.

Note the collision flagged in an earlier lesson: $|G|$ is how many elements the group has, while $|a|$ is a property of one element. Same notation, different meanings, distinguished only by whether the thing inside is a group or an element.

$G$ is cyclic if there is a single element $a$ with

$$G = \langle a \rangle$$

Such an $a$ is a generator. One element, applied over and over, produces the whole group.

Every cyclic group is abelian, and the proof is one line: $a^i a^j = a^{i+j} = a^j a^i$, since integer addition commutes. The converse is false - the Klein four-group is abelian and not cyclic - so “cyclic” is strictly stronger.

In $\mathbb{Z}_n$, the element $k$ generates the whole group exactly when

$$\gcd(k, n) = 1$$

More generally, $\langle k \rangle$ has order

$$|k| = \frac{n}{\gcd(k, n)}$$

Here’s why. Repeatedly adding $k$ produces the multiples of $k$ mod $n$, and you first return to $0$ at the least common multiple of $k$ and $n$, which is $\frac{kn}{\gcd(k,n)}$. Dividing by $k$ gives the number of steps, $\frac{n}{\gcd(k,n)}$. When the gcd is 1 that count is $n$, so you visit everything.

So $\mathbb{Z}_{12}$ has generators $1, 5, 7, 11$: four of them, which is $\varphi(12)$. In general a cyclic group of order $n$ has exactly $\varphi(n)$ generators.

A prime-order group is the extreme case: $\mathbb{Z}_7$ has $\varphi(7) = 6$ generators, meaning every element except the identity generates the whole thing.

Cyclic groups have the tidiest subgroup structure in all of group theory.

Every subgroup of a cyclic group is cyclic. And if $|G| = n$, then $G$ has exactly one subgroup of order $d$ for each divisor $d$ of $n$, and no others.

That’s why the lattice of $\mathbb{Z}_{12}$ from the previous lesson had exactly six nodes, matching the six divisors of 12. The subgroup of order $d$ is generated by $n/d$.

This is a strong property, and most groups don’t have it. $D_4$ has order 8 but five different subgroups of order 2.

Here is the first classification theorem in the section, and it is remarkably clean.

• Every infinite cyclic group is isomorphic to $(\mathbb{Z}, +)$.
• Every finite cyclic group of order $n$ is isomorphic to $(\mathbb{Z}_n, +)$.

So up to renaming, there is exactly one cyclic group of each size. When you understand $\mathbb{Z}_n$, you understand every cyclic group of order $n$ that anyone will ever show you.

The reason is easy to see: if $G = \langle a \rangle$ has order $n$, matching $a^k \leftrightarrow k$ turns $G$‘s multiplication into addition mod $n$, and that dictionary is a perfect translation.

Every group of prime order is cyclic. Take $|G| = p$ prime and any $a \ne e$. The subgroup $\langle a \rangle$ has order dividing $p$ (Lagrange, coming shortly), so its order is $1$ or $p$. It isn’t 1 because $a \ne e$. So $\langle a \rangle = G$.

That settles the structure of infinitely many groups in three lines. There is exactly one group of order 7, one of order 11, one of order 101.

Example 1: Find the order of each element of $\mathbb{Z}_{10}$.

Solution. Use $|k| = \frac{10}{\gcd(k,10)}$.

$k$	$\gcd(k,10)$	$\|k\|$
0	10	1
1	1	10
2	2	5
3	1	10
4	2	5
5	5	2
6	2	5
7	1	10
8	2	5
9	1	10

Generators are $1, 3, 7, 9$, and $\varphi(10) = 4$ confirms the count. Every order in the table divides 10.

Example 2: Is $U(9)$ cyclic?

Solution. $U(9) = \{1, 2, 4, 5, 7, 8\}$, the residues coprime to 9, so $|U(9)| = \varphi(9) = 6$.

Try 2 as a generator, computing powers mod 9:

$$2^1 = 2, \quad 2^2 = 4, \quad 2^3 = 8, \quad 2^4 = 16 \equiv 7, \quad 2^5 = 14 \equiv 5, \quad 2^6 = 10 \equiv 1$$

All six elements appear before returning to 1. Yes, cyclic, with $U(9) = \langle 2 \rangle \cong \mathbb{Z}_6$.

Contrast $U(8) = \{1,3,5,7\}$ from an earlier lesson, where every element squares to 1, so it is not cyclic. Whether $U(n)$ is cyclic is a genuinely delicate question: it is cyclic exactly when $n$ is $1, 2, 4$, a power of an odd prime, or twice such a power.

Example 3: Find all generators of $\mathbb{Z}_{18}$.

Solution. Need $\gcd(k, 18) = 1$ with $18 = 2 \cdot 3^2$, so exclude multiples of 2 and 3.

$$\{1, 5, 7, 11, 13, 17\}$$

Six generators, and $\varphi(18) = 18 \cdot \frac{1}{2} \cdot \frac{2}{3} = 6$. ✓

Example 4: Find the subgroup of order 6 in $\mathbb{Z}_{24}$.

Solution. For a subgroup of order $d$ in $\mathbb{Z}_n$, the generator is $n/d$. Here $24/6 = 4$:

$$\langle 4 \rangle = \{0, 4, 8, 12, 16, 20\}$$

Six elements ✓. And it is the only subgroup of order 6, by the classification of cyclic subgroups.

Example 5: The order of an element in a product.

Find the order of $(2, 3)$ in $\mathbb{Z}_4 \times \mathbb{Z}_6$.

Solution. The order of a pair is the least common multiple of the component orders.

In $\mathbb{Z}_4$: $|2| = \frac{4}{\gcd(2,4)} = 2$. In $\mathbb{Z}_6$: $|3| = \frac{6}{\gcd(3,6)} = 2$.

$$|(2,3)| = \operatorname{lcm}(2, 2) = 2$$

Check directly: $(2,3) + (2,3) = (4 \bmod 4, 6 \bmod 6) = (0,0)$. ✓

Since $|\mathbb{Z}_4 \times \mathbb{Z}_6| = 24$ and the largest possible element order is $\operatorname{lcm}(4,6) = 12 < 24$, no element generates the group, so it is not cyclic.

Example 6: Prove every group of order 5 is cyclic.

Solution. Let $|G| = 5$ and pick $a \ne e$. Consider $H = \langle a \rangle$.

$H$ is a subgroup, so by Lagrange’s theorem $|H|$ divides 5. The divisors of 5 are 1 and 5.

$|H| = 1$ would mean $H = \{e\}$, contradicting $a \in H$ with $a \ne e$.

So $|H| = 5 = |G|$, giving $H = G$. Therefore $G$ is cyclic and $G \cong \mathbb{Z}_5$. ∎

The same argument works for any prime, so there is exactly one group of each prime order.

Diffie-Hellman key exchange picks a large prime $p$ and a generator $g$ of the cyclic group $U(p)$. Alice sends $g^a$, Bob sends $g^b$, and each computes $g^{ab}$. An eavesdropper sees $g^a$ and $g^b$ and must solve the discrete logarithm problem to recover $a$. Generating the whole group matters: if $g$ generated only a small subgroup, the search space would collapse and the scheme would break. Choosing a bad generator is a real class of implementation bug.

Pseudorandom number generators. A linear congruential generator computes $x_{n+1} = (ax_n + c) \bmod m$. Its period is maximal exactly when certain coprimality conditions hold, which is the same gcd condition that decides generators in $\mathbb{Z}_m$. Get it wrong and your “random” sequence cycles after a few hundred values.

The circle of fifths. Pitch classes form $\mathbb{Z}_{12}$, and moving up a fifth is adding 7. Since $\gcd(7,12) = 1$, repeated fifths visit all twelve keys before returning, which is why the circle of fifths closes exactly once around. Stacking major thirds instead means adding 4, and $\gcd(4,12) = 4$, so you get a 3-cycle: an augmented triad.

Gear ratios and cicadas. Two meshed gears with $m$ and $n$ teeth return to their starting alignment after $\operatorname{lcm}(m,n)$ teeth, so coprime tooth counts spread wear evenly. The same arithmetic explains why periodical cicadas emerge on 13- and 17-year cycles: prime periods maximize the time before re-synchronizing with a predator’s cycle.

Hash tables. Open addressing with a probe step $k$ modulo table size $m$ visits every slot exactly when $\gcd(k, m) = 1$. Implementations often pick a prime table size for precisely this reason: with $m$ prime, any nonzero step works.