# Cyclic Groups

\(\mathbb{Z}_n^*\) is an example of a *group*. We won’t
formally introduce group theory,
but we do point out that a group only deals with one operation.
The \(*\) in \(\mathbb{Z}_n^*\) stresses that we are only considering
multiplication and forgetting about addition.

Notice we rarely add or subtract elements of \(\mathbb{Z}_n^*\). For one thing, the sum of two units might not be a unit. We performed addition in our proof of Fermat’s Theorem, but this can be avoided by using our proof of Euler’s Theorem instead. We did need addition to prove that \(\mathbb{Z}_n^*\) has a certain structure, but once this is done, we can focus on multiplication.

Let us see what can be said from studying multiplication alone.

When \(\mathbb{Z}_n^*\) has a generator,
we call \(\mathbb{Z}_n^*\) a *cyclic group*. If \(g\) is a generator
we write \(\mathbb{Z}_n^* = \langle g\rangle\).

A *subgroup* of \(\mathbb{Z}_n^*\) is a non-empty subset \(H\) of \(\mathbb{Z}_n^*\)
such that if \(a, b \in H\), then \(a b \in H\). Thus any subgroup contains \(1\),
and also the inverse of every element in the subgroup. (Why? Hint: our
definition of a subgroup only works when every element has a finite order; the
real definition is different!)

**Examples**:
Any \(a\in\mathbb{Z}_n^*\) can be used to generate cyclic subgroup
\(\langle a \rangle = \{a, a^2,...,a^d = 1\}\) (for some \(d\)). For example,
\(\langle 2 \rangle = \{2,4,1\}\) is a subgroup of \(\mathbb{Z}_7^*\).
Any group is always a subgroup
of itself. {1} is always a subgroup of any group. These last two
examples are the *improper* subgroups of a group.

## Lagrange’s Theorem

We prove Lagrange’s Theorem for \(\mathbb{Z}_n^*\). The proof can easily be modified to work for a general finite group.

Our proof of Euler’s Theorem has ideas in common with this proof.

**Theorem**: Let \(H\) be a subgroup of \(\mathbb{Z}_n^*\) of size \(m\).
Then \(m | \phi(n)\).

**Proof**: If \(H = \mathbb{Z}_n^*\) then \(m = \phi(n)\).
Otherwise, let \(H = \{h_1,...,h_m\}\).
let \(a\) be some element of \(\mathbb{Z}_n^*\) not in \(H\),
and consider the set \(\{h_1 a ,..., h_m a\}\) which we denote by
\(H a\). Every element in this set is distinct (since multiplying
\(h_i a = h_j a\) by \(a^{-1}\) implies \(h_i = h_j\)), and
furthermore no element of \(H a\) lies in \(H\) (since \(h_i = h_j a\) implies
\(a = h_j^{-1} h_i\) thus \(a \in H\), a contradiction).

Thus if every element of \(\mathbb{Z}_n^*\) lies in \(H\) or \(H a\) then \(2 m = \phi(n)\) and we are done. Otherwise take some element \(b\) in \(\mathbb{Z}_n^*\) not in \(H\) or \(H a\). By a similar argument, we see that \(H b = \{h_1 b ,..., h_m b \}\) contains exactly \(m\) elements and has no elements in common with either \(H\) or \(H a\).

Thus iterating this procedure if necessary, we eventually have \(\mathbb{Z}_n^*\) as the disjoint union of the sets \(H, H a, H b ,... \) where each set contains \(m\) elements. Thus \(m | \phi(n)\).∎

**Corollary**: Euler’s Theorem (and Fermat’s Theorem).
Any \(a \in \mathbb{Z}_n^*\) generates a cyclic subgroup \(\{a, a^2,...,a^d = 1\}\)
thus \(d | \phi(n)\), and hence \(a^{\phi(n)} = 1\).

## Subgroups of Cyclic Groups

**Theorem**: All subgroups of a cyclic group are cyclic.
If \(G = \langle g\rangle\) is a cyclic group of order \(n\) then for each
divisor \(d\) of \(n\) there exists exactly one subgroup of order \(d\) and
it can be generated by \(a^{n/d}\).

**Proof**: Given a divisor \(d\), let \(e = n/d\).
Let \(g\) be a generator of \(G\).
Then
\(\langle g^e \rangle = \{g^e, g^{2e},...,g^{d e} = 1\}\) is a cyclic subgroup
of \(G\) of size \(n/d\).

Now let \(H = \{a_1,...,a_{d-1},a_d = 1\}\) be some subgroup of \(G\). Then for each \(a_i\), we have \(a_i = g^k\) for some \(k\). By Lagrange’s Theorem the order of \(a_i\) must divide \(d\), hence \(g^{k d} = 1\).

Since the order of \(g\) is \(n\), we have \(k d = m n = m d e\) for some \(m\). Thus \(k = e m\) and \(a_i = (g^e)^m\), that is each \(a_i\) is some power of \(g^e\), hence \(H\) is one of the subgroups we previously described. ∎

## Counting Generators

**Theorem**: Let \(G\) be cyclic group of order \(n\). Then
\(G\) contains exactly \(\phi(n)\) generators.

**Proof**: Let \(g\) be a generator of \(G\), so \(G = \{g,...,g^n = 1\}\).
Then \(g^k\) generates \(G\) if and only if \(g^{k m} = g\) for some \(m\),
which happens when \(k m = 1 \pmod {n}\), that is \(k\) must be a unit
in \(\mathbb{Z}_n\), thus there are \(\phi(n)\) values of \(k\) for which
\(g^k\) is a generator.∎

**Example**: When \(\mathbb{Z}_n^*\) is cyclic (i.e. when \(n = 2,4,p^k , 2p^k\)
for odd primes \(p\)), \(\mathbb{Z}_n^*\) contains \(\phi(\phi(n))\) generators.

We can now prove a theorem often proved using multiplicative functions:

**Theorem**: For any positive integer \(n\)

**Proof**: Consider a cyclic group \(G\) of order \(n\), hence
\(G = \{g, ..., g^n = 1\}\). Each element \(a \in G\) is contained in some
cyclic subgroup. The theorem follows since
there is exactly one subgroup \(H\) of order \(d\) for
each divisor \(d\) of \(n\) and \(H\) has \(\phi(d)\) generators.∎

## Group Structure

In an abstract sense, for every positive integer \(n\), there is only one cyclic group of order \(n\), which we denote by \(C_n\). This is because if \(g\) is a generator, then \(C_n = \{g, g^2,...,g^n = 1\}\) which completely determines the behaviour of \(C_n\).

**Example**: Both \(\mathbb{Z}_3^*\) and \(\mathbb{Z}_4^*\) are cyclic of
order 2, so they both behave exactly like \(C_2\) (when considering multiplication
only). This is an example of a *group isomorphism*.

**Example**:
For \(n = 2^k p_1^{k_1} ... p_m^{k_m}\) for odd primes \(p_i\),
by the Chinese Remainder Theorem we have

Recall each \(\mathbb{Z}_{p_i^{k_i}}^*\) is cyclic, and so are \(\mathbb{Z}_2^*\) and \(\mathbb{Z}_4^*\). Also recall for \(k > 2\) we have that \(3 \in \mathbb{Z}_{2^k}^*\) has order \(2^{k-2}\) and no element has a higher order. Using some group theory this means the group structure of \(\mathbb{Z}_n^*\) is

when \(k = 1, 2\) and

when \(k > 2\).

*blynn@cs.stanford.edu*💡