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\)
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\).