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, so the reason for the $*$ in $\mathbb{Z}_n^*$ is to stress 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$

\[ n = \sum_{d|n} \phi(d) . \]

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 once we have a generator $g$, we know $C_n = \{g, g^2,...,g^n = 1\}$ and the behaviour of $C_n$ is completely determined by this.

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

\[ \mathbb{Z}_n^* = \mathbb{Z}_{2^k}^* \times \mathbb{Z}_{p_1^{k_1}}^* \times ... \times \mathbb{Z}_{p_m^{k_m}}^* \]

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

\[ C_{2^{k-1}} \times C_{p_1^{k_1} - p_1^{k_1 - 1}} \times ... \times C_{p_m^{k_m} - p_m^{k_m-1}} \]

when $k = 1, 2$ and

\[ C_2 \times C_{2^{k-2}} \times C_{p_1^{k_1} - p_1^{k_1 - 1}} \times ... \times C_{p_m^{k_m} - p_m^{k_m-1}} \]

when $k \gt 2$.