Cyclic Groups

Cyclic groups are the simplest groups there are: one element does all the work, and everything else is a power of it. That simplicity pays off. By the end of this page we'll know everything about a cyclic group: what it looks like (there's only one of each size), the order of every element, which elements generate it, and every single subgroup. That last one is rare. For most groups, finding all the subgroups is real work. For a cyclic group, it's a list of divisors.

Cyclic Groups

We met these back when we were classifying small groups. Here's the definition again.

The first big fact is that a cyclic group is completely determined by its size. If two cyclic groups have the same order, you can match them up by matching up their generators and then matching powers with powers.

So up to isomorphism there's exactly one cyclic group of each size, and we give them standard names.

• If $G$ is cyclic and $|G| = n \in \mathbb{N}$ then $G \cong C_n = \langle x \mid x^n = e \rangle$ (presentation).
• If $G$ is cyclic and $|G| = \infty$ then $G \cong C_\infty = \langle x \mid \emptyset \rangle$ (one generator and no relations).

The presentation $\langle x \mid x^n = e \rangle$ says: one generator $x$, and the only rule is that $x^n = e$ (plus whatever follows from it). With no rules at all, the powers of $x$ never collide, and you get $C_\infty$.

Everything on this page is written multiplicatively, with $C_n = \langle x \rangle$ or $C_\infty = \langle x \rangle$. Translate to $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}$ by reading $x^k$ as $k$.

Orders of Elements in Cyclic Groups

We already know how to find orders by brute force. In a cyclic group there's a formula.

And the link between the order of an element and the size of the subgroup it generates:

Now apply it to the elements of a cyclic group. The infinite case is quick: apart from $e$, nothing has finite order.

Infinite cyclic groups

Proof. $x^0 = e$ has order $1$. For $k \neq 0$, suppose $|x^k| = q$ for some $q \in \mathbb{N}$. Then $e = (x^k)^q = x^{kq}$ with $kq \neq 0$, so $|x| \le |kq|$. By Theorem 0, $|C_\infty| = |\langle x \rangle| = |x| \le |kq| \lt \infty$. Contradiction $\implies |x^k| = \infty$. $\blacksquare$

Finite cyclic groups

The finite case needs one lemma first. It's true in any group, not just cyclic ones: once you know $|g| = n$, the exponents that kill $g$ are exactly the multiples of $n$.

Proof. Suppose $g \in G$ and $|g| = n$.

• ($\Leftarrow$) $m \equiv 0 \pmod n \implies m = ln$ for some $l \in \mathbb{Z}$. Then $g^m = g^{ln} = (g^n)^l = e^l = e$.
• ($\Rightarrow$) Suppose $g^m = e$. Write $m = qn + r$, $0 \le r \lt n$ (Division Algorithm). Then $g^r = (g^{-n})^q g^m = (g^n)^{-q} g^m = e^{-q} e = e$. Since $n$ is the smallest element of $\mathbb{N}$ with $g^n = e$, we must have $r = 0$. So $m \equiv 0 \pmod n$. $\blacksquare$

Now the formula. Remember that $(k, n)$ means $\gcd(k, n)$.

Proof. Using the lemma,

$$\begin{align*} \{m \in \mathbb{Z} : (x^k)^m = e\} &= \{m \in \mathbb{Z} : x^{km} = e\} \\ &= \{m \in \mathbb{Z} : km \equiv 0 \pmod n\} \\ &= \left\{m \in \mathbb{Z} : m \equiv 0 \pmod{\tfrac{n}{(k, n)}}\right\}. \end{align*}$$

The order of $x^k$ is the smallest positive integer in this set, which is $\frac{n}{(k, n)}$. $\blacksquare$

Picture $C_n$ as $n$ dots around a circle, with $x^k$ meaning "jump $k$ dots." Starting from $e$ and jumping by $k$ over and over traces out a star, and the number of dots the star lands on before it closes up is $|x^k|$. Some stars land on every dot. Those are the interesting ones.

Generators for $C_n$

Which powers of $x$ generate all of $C_n = \langle x \rangle = \{e, x, x^2, \dots, x^{n-1}\}$? By Theorem 0, $x^k$ generates $C_n$ exactly when $|x^k| = n$, and by the formula that means $\frac{n}{(k, n)} = n$.

In the Star Hopper, these are exactly the jump sizes whose star touches every dot. Here's the count in action.

The same corollary says something useful about primitive roots, because a group of units mod $n$ can itself be cyclic.

Now with actual numbers. We already know one primitive root mod $103$.

Notice that $5^{101} \equiv 5^{-1}$ made the list. That's no accident: $(k, n) = 1 \iff (-k, n) = 1$, so the inverse of a generator is always a generator too.

Subgroups of Cyclic Groups

Now for the payoff. In a general group, subgroups can be generated by several elements at once and can be hard to pin down. In a cyclic group, every subgroup is generated by a single power of $x$, and we can say exactly which one.

In particular, every subgroup of a cyclic group is cyclic. The proof is the Division Algorithm again: any power of $x$ in $H$ that isn't a multiple of $k$ would leave a remainder smaller than $k$ inside $H$.

Show proof

---

Proof. Suppose $H \neq \{e\}$ and let $S = \{l \in \mathbb{N} : x^l \in H\}$.

Since $H \neq \{e\}$, $\exists l \in \mathbb{Z} \setminus \{0\}$ s.t. $x^l \in H$, and also $x^{-l} \in H$. One of $l, -l$ is positive, so $S \neq \emptyset$. Therefore, by the Well Ordering Principle, $S$ has a smallest element, which we call $k$. Now we have that:

• $\langle x^k \rangle \subseteq H$: $x^k \in H \implies \langle x^k \rangle \subseteq H$.
• $H \subseteq \langle x^k \rangle$: $\forall h \in H$, $h = x^l$ for some $l \in \mathbb{Z}$. Write $l = qk + r$, $0 \le r \lt k$ (Division Algorithm). Then $x^{-qk} \in H \implies x^r = x^{-qk} x^l \in H \implies r = 0$ ($k$ is the smallest positive integer with $x^k \in H$). Therefore $h = (x^k)^q \in \langle x^k \rangle$.

We conclude that $H = \langle x^k \rangle$. $\blacksquare$

You can watch the proof happen in $C_\infty$. Put any powers of $x$ you like into $H$, and $H$ fills in everything they generate. The smallest positive exponent that shows up is the $k$ from Theorem 1, and every other exponent in $H$ turns out to be a multiple of it.

Infinite cyclic groups

By Theorem 1, every subgroup of $C_\infty$ is $\langle x^k \rangle$ for some $k \ge 0$ (we can take $k \ge 0$ because $\langle x^k \rangle = \langle x^{-k} \rangle$). The next result says there's no double counting.

Proof. By Theorem 1, every subgroup of $C_\infty = \langle x \rangle$ is of the form $\langle x^k \rangle$, for some $k \in \{0, 1, 2, \dots\}$. Suppose $k, l \in \{0, 1, 2, \dots\}$ and $k \lt l$.

• If $k = 0$ then $\langle x^k \rangle = \{e\}$, but $|\langle x^l \rangle| = |x^l| = \infty$, so $\langle x^k \rangle \neq \langle x^l \rangle$.
• If $k \gt 0$ then $0 \lt k \lt l$, so $k \neq ql$ for any $q \in \mathbb{Z}$. So, by Theorem 0, $x^k \neq x^{ql}$, $\forall q \in \mathbb{Z}$. Therefore $x^k \notin \langle x^l \rangle$. So $\langle x^k \rangle \neq \langle x^l \rangle$. $\blacksquare$

This tells us exactly how many generators $C_\infty$ has.

To see this: suppose $C_\infty = \langle x^l \rangle$ for some $l \in \mathbb{Z}$. Then $C_\infty = \langle x^{|l|} \rangle = \langle x^1 \rangle$ and, since the subgroups listed above are distinct, $|l| = 1 \implies l = \pm 1$.

Finite cyclic groups

The finite case is even tidier. Lagrange says a subgroup's order has to divide $n$. For cyclic groups the converse holds too, as strongly as it possibly could: every divisor gets exactly one subgroup.

Part (i) says no other orders are possible, (ii) says each divisor's subgroup exists, and (iii) says it's the only one.

Proof of (i): Follows from Lagrange's Theorem.

Proof of (ii): Since $n = d \cdot \frac{n}{d}$, we have $\frac{n}{d} \mid n$, so $\left(\frac{n}{d}, n\right) = \frac{n}{d}$. By Theorem 0 and the order formula, $$|\langle x^{n/d} \rangle| = |x^{n/d}| = \frac{n}{(n/d, n)} = \frac{n}{n/d} = d.$$

Proof of (iii): Let $k$ be the smallest positive integer with the property that $x^k \in H$, so that $H = \langle x^k \rangle$ (Theorem 1). Then

$$d = |H| = |x^k| = \frac{n}{(k, n)} \implies (k, n) = \frac{n}{d}$$

$$\implies \frac{n}{d} \mid k \implies x^k \in \langle x^{n/d} \rangle \implies H \le \langle x^{n/d} \rangle.$$

But $|H| = d = |\langle x^{n/d} \rangle|$, and a subset of a finite set with the same size is the whole set, so $H = \langle x^{n/d} \rangle$. $\blacksquare$

Put the two halves of the page together. Each $x^k$ generates some subgroup, and by the theorem that subgroup is $\langle x^{(k, n)} \rangle$, the one of order $\frac{n}{(k, n)}$. So sorting the elements of $C_n$ by "which subgroup do you generate?" drops every element into a bin labeled by a divisor of $n$.

Examples: lattices of subgroups of cyclic groups

Since there's one subgroup per divisor, drawing the lattice of a cyclic group comes down to drawing the divisors of $n$. And containment is divisibility too: $\langle x^{n/d} \rangle \le \langle x^{n/d'} \rangle$ exactly when $d \mid d'$.

The next one has six divisors, so six subgroups.

For $C_\infty$ there's no top-to-bottom ordering by size (every nontrivial subgroup is infinite), but the divisibility pattern is still there, just turned upside down.

Spicy Bonus

If you sorted every tile in the Generator Sorter, you saw the bin of order $d$ fill up with exactly $\varphi(d)$ tiles, and the bins added up to $n$. Here's why that always happens.