## 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
mulitplication 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.

In this section, we shall see what we 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?).

**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 \gt 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 \gt 2$.