Cyclic Groups

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

A cyclic group may have several generators: $⟨x⟩=⟨x^{-1}⟩$ 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 $⟨r⟩=\{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}=⟨1⟩$ 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.

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.¹ The finite case also says the arithmetic of powers is exactly arithmetic modulo $n$, the observation that modular arithmetic makes precise.

A short divisibility lemma controls which powers give the identity.

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$.² 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.

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.³ 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 ik/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.

Generators and the order of a power

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

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.⁴ The generators fall out immediately: $x^a$ generates the whole group exactly when $|x^a|=n$, i.e. $\gcd (a,n)=1$.

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

Subgroups: one per divisor

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

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=⟨x^d⟩$.⁵ For finite $H$, matching orders to divisors gives the bijection. The containment rule is divisibility reversed: $⟨x^{n/a}⟩\le ⟨x^{n/b}⟩$ if and only if $a\mid b$.

The lattice reproduces the divisor diagram of $12$: below $⟨1⟩$ (the whole group) sit the subgroups of order $6$ and $4$, and so on down to the trivial subgroup. Containment is divisibility read backwards, $⟨\bar{a}⟩\le ⟨\bar{b}⟩$ if and only if $\gcd (b,12)\mid \gcd (a,12)$, and each subgroup has $\phi$-many generators of its own: $⟨\bar{2}⟩=⟨\overline{10}⟩$ (order $6$, $\phi (6)=2$ generators), $⟨\bar{3}⟩=⟨\bar{9}⟩$ (order $4$), $⟨\bar{4}⟩=⟨\bar{8}⟩$ (order $3$). Summing over the lattice recovers the divisor identity ${\sum }_{d\mid n}\phi (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 lesson.

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$.⁶ 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 ik/n}$ with $\gcd (k,n)=1$, so there are $\phi (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 $\frac{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.

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\mathrm{mod}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}+\cdots +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.⁷

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.