---
title: Cyclic Groups
module: Subgroups and Quotients
moduleNumber: 3
lessonNumber: 2
order: 302
summary: >
  A cyclic group is generated by one element. Two facts organize the whole
  theory: the order of an element equals the order of the subgroup it generates,
  and cyclic groups of equal order are isomorphic, so $\mathbb{Z}$ and
  $\mathbb{Z}/n\mathbb{Z}$ are the only ones. From there the generators
  ($\varphi(n)$ of them), the subgroups (one per divisor of $n$), and a fast
  exponentiation algorithm all follow.
topics: [Subgroups and Quotients]
sources:
  - book: Dummit & Foote
    ref: "Ch. 2; §2.3 Cyclic Groups and Cyclic Subgroups"
  - book: Judson
    ref: "Ch. 4 Cyclic Groups; §4.1 Cyclic Subgroups, §4.3 The Method of Repeated Squares"
draft: false
---

The simplest way to build a subgroup is to pick one element $x \in G$ and take
all of its integer powers. Closure and inverses come for free, and the result is
the smallest subgroup containing $x$. Groups built this way, from a single
element, are the cyclic groups, the simplest to describe: two theorems settle
their generators, their subgroups, and their isomorphism type.

## Cyclic groups and the order of an element

> **Definition (Cyclic group).** A group $H$ is **cyclic** if
> $H = \langle x \rangle = \{ x^n \mid n \in \mathbb{Z} \}$ for some $x \in H$.
> Then $x$ is a **generator** of $H$. In additive notation
> $H = \{ nx \mid n \in \mathbb{Z} \}$.

A cyclic group may have several generators: $\langle x \rangle = \langle x^{-1} \rangle$
always, since as $n$ runs over $\mathbb{Z}$ so does $-n$. By the laws of
exponents cyclic groups are abelian. Two examples set the pattern.

- The rotations in $D_{2n}$ are $\langle r \rangle = \{1, r, r^2, \dots, r^{n-1}\}$,
  a **finite** cyclic group of order $n$. Powers cycle with period $n$: reduce
  any $r^t$ by the division algorithm, $t = nq + k$ with $0 \le k < n$, so
  $r^t = (r^n)^q r^k = r^k$.
- The integers $\mathbb{Z} = \langle 1 \rangle$ under addition are an
  **infinite** cyclic group; every element is a unique multiple $n \cdot 1$, and
  distinct multiples are distinct.

The order of a generator and the size of the group it generates are the same
number, which is why the symbol $|\cdot|$ serves for both.

> **Theorem (Order equals size).** If $H = \langle x \rangle$, then
> $|H| = |x|$. If $|x| = n < \infty$, the elements $1, x, x^2, \dots, x^{n-1}$
> are distinct and exhaust $H$. If $|x| = \infty$, then $x^a \neq x^b$ for all
> $a \neq b$, so all powers are distinct.

For the finite case, if $x^a = x^b$ with $0 \le a < b < n$ then $x^{b-a} = 1$
with $0 < b - a < n$, contradicting that $n$ is the least positive power giving
$1$. So the $n$ listed powers are distinct, and the division-algorithm reduction
shows every power of $x$ is one of them.[^df-order] The finite case also says
the arithmetic of powers is exactly arithmetic modulo $n$, the observation that
[modular arithmetic](/abstract-algebra/foundations/integers-and-modular-arithmetic)
makes precise.

A short divisibility lemma controls which powers give the identity.

> **Lemma.** For $x \in G$ and $m, n \in \mathbb{Z}$, if $x^n = 1$ and
> $x^m = 1$ then $x^{d} = 1$ where $d = \gcd(m, n)$. In particular, if
> $x^m = 1$ then $|x|$ divides $m$.

Bézout writes $d = mr + ns$, so $x^d = (x^m)^r (x^n)^s = 1$. Taking $n = |x|$
gives $\gcd(m, |x|) = |x|$, i.e. $|x| \mid m$.[^df-div] Everything about a single
element's powers reduces to divisibility.

## Classification up to isomorphism

These two behaviors, finite reduction and infinite non-collapse, exhaust the
possibilities for a cyclic group.

> **Theorem (Classification of cyclic groups).** Any two cyclic groups of the
> same order are isomorphic. If $\langle x \rangle$ and $\langle y \rangle$ both
> have order $n$, then $x^k \mapsto y^k$ is an isomorphism; if
> $\langle x \rangle$ is infinite, then $k \mapsto x^k$ is an isomorphism
> $\mathbb{Z} \xrightarrow{\sim} \langle x \rangle$.

The map $x^k \mapsto y^k$ is well defined because $x^r = x^s$ forces
$n \mid r - s$, and then $y^r = y^s$; it is a surjective homomorphism between
finite sets of equal size, hence an isomorphism.[^df-class] So up to
isomorphism there is one cyclic group of each finite order $n$, written $Z_n$
(multiplicatively) or $\mathbb{Z}/n\mathbb{Z}$ (additively), and one infinite
cyclic group, $\mathbb{Z}$.

The **$n$-th roots of unity** are the standard geometric model of $Z_n$:
$\zeta_k = e^{2\pi i k/n}$ for $k = 0, 1, \dots, n-1$, sitting equally spaced on
the unit circle. Multiplication adds angles, so $\zeta = e^{2\pi i/n}$ generates
the group and $\zeta^k$ runs through every root.

$$
% caption: The sixth roots of unity form a cyclic group of order six; the
% highlighted point is a generator, and repeated multiplication steps around the
% circle by a fixed angle.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black] (0,0) circle (1.7);
  \draw[black, ->] (-2.1,0) -- (2.1,0);
  \draw[black, ->] (0,-2.1) -- (0,2.1);
  \foreach \k in {0,...,5} {
    \node[circle, fill=black!65, inner sep=1.6pt] (r\k) at (\k*60:1.7) {};
  }
  \node[circle, draw=acc, fill=acc, inner sep=1.9pt] at (60:1.7) {};
  \node[acc, anchor=south west, font=\scriptsize] at (60:1.9) {generator};
  \node[black, anchor=west, font=\scriptsize] at (0:1.8) {$1$};
  \draw[acc, ->, thick] (0:1.35) arc (0:55:1.35);
\end{tikzpicture}
$$

## Generators and the order of a power

Once one generator is known, the order of a power determines the rest.

> **Theorem (Order of a power).** Let $|x| = n < \infty$ and $a \neq 0$. Then
> $$
> |x^a| = \frac{n}{\gcd(n, a)}.
> $$
> If $|x| = \infty$ then $|x^a| = \infty$. In particular, for $a \mid n$,
> $|x^a| = n/a$.

Writing $d = \gcd(n, a)$, $n = db$, $a = dc$ with $\gcd(b, c) = 1$, one checks
$(x^a)^b = (x^n)^c = 1$ so $|x^a| \mid b$, and conversely $b \mid |x^a|$, forcing
equality.[^df-pow] The generators fall out immediately: $x^a$ generates the
whole group exactly when $|x^a| = n$, i.e. $\gcd(a, n) = 1$.

> **Theorem (Generators).** For $H = \langle x \rangle$ of order $n$,
> $H = \langle x^a \rangle$ if and only if $\gcd(a, n) = 1$. The number of
> generators is $\varphi(n)$, Euler's totient. For infinite $H$, the only
> generators are $x$ and $x^{-1}$.

For $\mathbb{Z}/12\mathbb{Z}$ the generators are the residues coprime to $12$,
namely $1, 5, 7, 11$, so there are $\varphi(12) = 4$ of them. The order of each
residue is $12/\gcd(a,12)$.

| $a$ | $\gcd(a,12)$ | order $= 12/\gcd$ | generator? |
| --- | --- | --- | --- |
| $1$ | $1$ | $12$ | yes |
| $2$ | $2$ | $6$ | no |
| $3$ | $3$ | $4$ | no |
| $4$ | $4$ | $3$ | no |
| $5$ | $1$ | $12$ | yes |
| $6$ | $6$ | $2$ | no |
| $8$ | $4$ | $3$ | no |

## Subgroups: one per divisor

The subgroup structure of a cyclic group is the divisor structure of $n$.

> **Theorem (Subgroups of a cyclic group).** Let $H = \langle x \rangle$ be
> cyclic. Every subgroup of $H$ is cyclic. If $|H| = n < \infty$, then for each
> positive divisor $a$ of $n$ there is a **unique** subgroup of order $a$,
> namely $\langle x^{n/a} \rangle$, and the subgroups correspond bijectively
> with the positive divisors of $n$. If $|H| = \infty$, the nontrivial
> subgroups are the $\langle x^m \rangle = \langle x^{|m|} \rangle$, one per
> positive integer $m$.

That every subgroup is cyclic uses the division algorithm: a nontrivial
subgroup $K$ contains a smallest positive power $x^d$, and dividing any
$x^a \in K$ by $x^d$ leaves a remainder power of smaller exponent, which must be
$x^0$, so $K = \langle x^d \rangle$.[^df-sub] For finite $H$, matching orders to
divisors gives the bijection. The containment rule is divisibility reversed:
$\langle x^{n/a} \rangle \le \langle x^{n/b} \rangle$ if and only if $a \mid b$.

$$
% caption: The subgroup lattice of $\mathbb{Z}/12\mathbb{Z}$, one node per
% divisor of $12$; each subgroup is generated by a single residue and orders
% multiply along upward paths.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={draw, inner sep=2.5pt, fill=acc!8, minimum width=15mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[nd, draw=acc] (top) at (0,3.2) {$< 1 >$\\order $12$};
  \node[nd] (l2) at (-1.8,1.7) {$< 2 >$\\order $6$};
  \node[nd] (l3) at (1.8,1.7) {$< 3 >$\\order $4$};
  \node[nd] (l4) at (-1.8,0.2) {$< 4 >$\\order $3$};
  \node[nd] (l6) at (1.8,0.2) {$< 6 >$\\order $2$};
  \node[nd] (bot) at (0,-1.3) {$< 0 >$\\order $1$};
  \draw[black] (bot) -- (l4);
  \draw[black] (bot) -- (l6);
  \draw[black] (l4) -- (l2);
  \draw[black] (l6) -- (l2);
  \draw[black] (l6) -- (l3);
  \draw[black] (l2) -- (top);
  \draw[black] (l3) -- (top);
\end{tikzpicture}
$$

The lattice reproduces the divisor diagram of $12$: below $\langle 1 \rangle$
(the whole group) sit the subgroups of order $6$ and $4$, and so on down to the
trivial subgroup. Containment is divisibility read backwards,
$\langle \bar{a} \rangle \le \langle \bar{b} \rangle$ if and only if
$\gcd(b, 12) \mid \gcd(a, 12)$, and each subgroup has $\varphi$-many generators
of its own: $\langle \bar{2} \rangle = \langle \bar{10} \rangle$ (order $6$,
$\varphi(6) = 2$ generators), $\langle \bar{3} \rangle = \langle \bar{9} \rangle$
(order $4$), $\langle \bar{4} \rangle = \langle \bar{8} \rangle$ (order $3$).
Summing over the lattice recovers the divisor identity
$\sum_{d \mid n} \varphi(d) = n$: every element of $\mathbb{Z}/12\mathbb{Z}$ is
a generator of exactly one subgroup. The full theory of such diagrams for
arbitrary groups is the subject of the
[subgroup lattice](/abstract-algebra/subgroups-and-quotients/generation-and-subgroup-lattices)
lesson.

$$
% caption: Grouping the twelve elements of $\mathbb{Z}/12\mathbb{Z}$ by order:
% each block is the $\varphi(d)$ generators of the order-$d$ subgroup, and the
% block sizes sum to $12$, the identity $\sum_{d \mid n} \varphi(d) = n$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  blk/.style={draw, minimum height=8mm, fill=acc!8, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[blk, minimum width=11mm] (d1) at (0,0)   {order $1$};
  \node[blk, minimum width=11mm] (d2) at (1.5,0)  {order $2$};
  \node[blk, minimum width=15mm] (d3) at (3.3,0)  {order $3$};
  \node[blk, minimum width=15mm] (d4) at (5.3,0)  {order $4$};
  \node[blk, minimum width=15mm] (d6) at (7.3,0)  {order $6$};
  \node[blk, minimum width=23mm, draw=acc] (d12) at (10.0,0) {order $12$};
  \node[black, font=\scriptsize, below] at (d1.south)  {$1$};
  \node[black, font=\scriptsize, below] at (d2.south)  {$1$};
  \node[black, font=\scriptsize, below] at (d3.south)  {$2$};
  \node[black, font=\scriptsize, below] at (d4.south)  {$2$};
  \node[black, font=\scriptsize, below] at (d6.south)  {$2$};
  \node[acc, font=\scriptsize, below] at (d12.south) {$4$};
  \node[black, font=\scriptsize, anchor=west] at (-0.55,-1.15)
    {block sizes $1 + 1 + 2 + 2 + 2 + 4 = 12$};
\end{tikzpicture}
$$

## Roots of unity inside the circle group

The multiplicative group $\mathbb{C}^\times$ contains the **circle group**
$\mathbb{T} = \{ z \in \mathbb{C} : |z| = 1 \}$, and inside it every finite
cyclic group appears exactly once: the $n$-th roots of unity
$\mu_n = \{ z : z^n = 1 \}$ form the unique subgroup of $\mathbb{T}$ of order
$n$.[^ju-roots] A **primitive** $n$-th root of unity is a generator of $\mu_n$;
by the generator count these are the $\zeta^k = e^{2\pi i k/n}$ with
$\gcd(k, n) = 1$, so there are $\varphi(n)$ of them. The subgroup theorem reads
geometrically: $\mu_d \le \mu_n$ exactly when $d \mid n$, the $d$-gon's vertices
sitting among the $n$-gon's. Stacking all the $\mu_n$ together gives the group
of **all** roots of unity, an infinite locally-cyclic group that is not finitely
generated — each element has finite order, yet no finite set generates the
whole. Cyclic structure also transfers along the exponential: the map
$\theta \mapsto e^{i\theta}$ is a homomorphism from $(\mathbb{R}, +)$ onto
$\mathbb{T}$ carrying the discrete subgroup
$\tfrac{2\pi}{n}\mathbb{Z} / 2\pi\mathbb{Z}$ onto $\mu_n$, which is where the
"equally spaced points, add the angles" picture comes from. These groups return
as the central object of
[cyclotomic field theory](/abstract-algebra/field-theory/separable-and-cyclotomic-extensions).

## Application: fast modular exponentiation

Because $Z_n \cong \mathbb{Z}/n\mathbb{Z}$, computing a high power $a^k$ in a
cyclic group is computing $a^k \bmod n$, and the group structure gives an
algorithm far faster than $k - 1$ multiplications. Write $k$ in binary,
$k = 2^{k_1} + 2^{k_2} + \dots + 2^{k_r}$; then $a^k$ is the product of the
values $a^{2^{k_i}}$, each obtained from the previous power of two by a single
squaring.[^ju-sq]

$$
% caption: Repeated squaring for $271^{321} \bmod 481$, using
% $321 = 2^0 + 2^6 + 2^8$; each rung squares the one below it modulo $481$, and
% the three selected rungs are multiplied together.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  rung/.style={draw, minimum width=18mm, minimum height=8mm, font=\scriptsize},
  sel/.style={draw=acc, fill=acc!10, minimum width=18mm, minimum height=8mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[sel]  (e0) at (0,0)   {$271^{1}$};
  \node[rung] (e1) at (0,0.95){$271^{2}$};
  \node[rung] (e2) at (0,1.9) {$271^{4}$};
  \node[black, font=\scriptsize] at (0,2.75) {$\vdots$};
  \node[sel]  (e6) at (0,3.55){$271^{64}$};
  \node[rung] (e7) at (0,4.5) {$271^{128}$};
  \node[sel]  (e8) at (0,5.45){$271^{256}$};
  \foreach \a/\b in {e0/e1, e1/e2, e6/e7, e7/e8}
    \draw[->, black] (\a) -- (\b) node[midway, right, font=\scriptsize]{square};
  \node[draw=acc, text=acc, align=center, font=\scriptsize, anchor=west]
    at (2.6,2.7) {multiply the\\three selected\\rungs mod $481$};
  \draw[acc, ->] (0.95,0) to[out=0,in=200] (2.55,2.3);
  \draw[acc, ->] (0.95,3.55) -- (2.55,2.9);
  \draw[acc, ->] (0.95,5.45) to[out=0,in=160] (2.55,3.3);
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{ModPow}(a, k, n)$ — exponentiation by repeated squaring
$result \gets 1$
$base \gets a \bmod n$
while $k > 0$ do
  if $k$ is odd then
    $result \gets (result \cdot base) \bmod n$
  $base \gets (base \cdot base) \bmod n$ // square for the next bit
  $k \gets \lfloor k / 2 \rfloor$
return $result$
```

> **Worked example.** Compute $271^{321} \bmod 481$. The binary expansion is
> $321 = 2^0 + 2^6 + 2^8$, so only the rungs $2^0$, $2^6$, $2^8$ of the squaring
> ladder are needed.[^ju-sq] Squaring successively modulo $481$:
>
> $$
> \begin{aligned}
> 271^{2^0} &\equiv 271, &\quad 271^{2^1} &\equiv 271^2 = 73441 \equiv 329, &\quad 271^{2^2} &\equiv 329^2 \equiv 16, \\
> 271^{2^3} &\equiv 256, &\quad 271^{2^4} &\equiv 120, &\quad 271^{2^5} &\equiv 451, \\
> 271^{2^6} &\equiv 419, &\quad 271^{2^7} &\equiv 477, &\quad 271^{2^8} &\equiv 16 \pmod{481}.
> \end{aligned}
> $$
>
> Multiplying the three selected rungs,
> $$
> 271^{321} \;\equiv\; 271 \cdot 419 \cdot 16
> \;\equiv\; 47 \pmod{481},
> $$
> eight squarings and two multiplications in place of $320$ multiplications.

For a cryptographic exponent of $300$ digits, the ladder needs roughly a
thousand modular multiplications; the naive method needs more than the number
of atoms in the universe.

The loop runs once per binary digit of $k$, so it uses $O(\log k)$
multiplications modulo $n$ instead of $O(k)$. This is the arithmetic behind
public-key cryptography, and it is entirely a statement about powers in a
cyclic group.

[^df-order]: **Dummit & Foote**, _Abstract Algebra_, §2.3, Proposition 2 — $|\langle x \rangle| = |x|$, with the distinct-powers argument in the finite and infinite cases.
[^df-div]: **Dummit & Foote**, §2.3, Proposition 3 — if $x^n = x^m = 1$ then $x^{\gcd(m,n)} = 1$, so $|x|$ divides any exponent killing $x$.
[^df-class]: **Dummit & Foote**, §2.3, Theorem 4 — any two cyclic groups of the same order are isomorphic; $Z_n \cong \mathbb{Z}/n\mathbb{Z}$ and the infinite cyclic group is $\mathbb{Z}$.
[^df-pow]: **Dummit & Foote**, §2.3, Proposition 5 — $|x^a| = n/\gcd(n, a)$ for $|x| = n$.
[^df-sub]: **Dummit & Foote**, §2.3, Proposition 6 and Theorem 7 — the generators of a cyclic group ($\varphi(n)$ of them) and the classification of its subgroups by the divisors of $n$.
[^ju-roots]: **Judson**, _Abstract Algebra: Theory and Applications_, §4.2 — the multiplicative group of complex numbers, the circle group, $n$-th roots of unity as a cyclic group, and primitive roots; **Dummit & Foote**, §2.4, Exercise 18 — the group of all $p$-power roots of unity is not finitely generated.
[^ju-sq]: **Judson**, _Abstract Algebra: Theory and Applications_, §4.3 — The Method of Repeated Squares: computing $a^k \bmod n$ in $O(\log k)$ multiplications by squaring along the binary expansion of $k$.