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

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

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

Ben Lynn blynn@cs.stanford.edu 💡