Skip to main content
Logo image

Intro to Abstract Algebra Fall 2025

Blake Farman

Chapter 7 Cyclic Groups

Section 7.1 Integer Powers of Group Elements

Definition 7.1. Natural Number Powers.

Assume \(G\) is a group. For all \(g \in G\text{,}\) define \(g^0 = 1\) and for all \(n \in \N\text{,}\)
\begin{equation*} g^n = \underbrace{gg\cdots g}_n\text{.} \end{equation*}
🔗
🔗

Remark 7.2.

This is an example of a recursive definition. We write
\begin{equation*} g^n = \underbrace{gg\cdots g}_n \end{equation*}
to intuitively communicate that exponentiation is simply repeated multiplication. What we are really saying is that we have defined each power \(g^n\) in terms of the natural numbers less than \(n\text{:}\)
\begin{align*} g^0 \amp= 1\\ g^1 \amp= g\\ g^2 \amp= gg\\ g^3 \amp= ggg\\ \amp\phantom{=}\vdots\\ g^{n-1} \amp= \underbrace{gg\cdots g}_{n-1}\\ g^n \amp= \underbrace{gg \cdots g}_n\text{.} \end{align*}
🔗
We make this more concise by writing
\begin{align*} g^0 \amp= 1,\\ g^{n+1} \amp= g^n g \end{align*}
The validity of this approach is guaranteed by the Recursion Theorem
 1 
en.wikipedia.org/wiki/Recursion#The_recursion_theorem
, which is equivalent to the Well-Ordering Principle
 2 
en.wikipedia.org/wiki/Well-ordering_principle
.
🔗
When we define operations recursively, we tend to prove facts about the operation using induction. The following results provide some practice proving things about inductively defined operations.
🔗
🔗

Proof.

Let \(g \in G\) be given. We proceed by induction on \(n\text{.}\) The base case \(n = 1\) holds because
\begin{equation*} g^{m + 1} = g^m g = g^m g^1 \end{equation*}
by Definition 7.1.
🔗
Let \(k \in \N\) be given. Assume \(g^{m + k} = g^m g^k\text{.}\) By the induction hypothesis, associativity for \((\N,+)\text{,}\) associativity for \(G\text{,}\) and Definition 7.1,
\begin{align*} g^{m + (k+1)} \amp= g^{(m + k) + 1}\\ \amp= g^{m+k} g\\ \amp= \left(g^mg^k\right)g\\ \amp= g^m\left(g^kg\right)\\ \amp= g^mg^{k+1} \end{align*}
Therefore for all \(n \in \N\text{,}\) \(g^{m+n} = g^{m}g^n\) by induction.
🔗
🔗

Definition 7.4. Integer Powers.

Assume \(G\) is a group. For all \(g \in G\text{,}\) define \(g^0 = 1\) and \(g^{-n} = \left(g^{-1}\right)^n\text{.}\)
🔗
🔗

Proof.

Let \(g \in G\) be given. We proceed by induction on \(n\text{.}\) The base case \(n = 1\) is trivial because \(g^{-1}\) is, by definition, the inverse of \(g\text{.}\)
🔗
Let \(k \in \N\) be given. Assume \(g^{-k} = \left(g^{k}\right)^{-1}\text{.}\) Observe that
\begin{align*} g^{k+1}g^{-(k+1)} \amp= g^{k+1}\left(g^{-1}\right)^{k+1}\\ \amp= g^{1+k}\left(g^{-1}\right)^kg^{-1}\\ \amp= \left(gg^k\right)g^{-k}g^{-1}\\ \amp= g\left(g^kg^{-k}\right)g^{-1}\\ \amp= gg^{-1}\\ \amp= 1 \end{align*}
implies \(\left(g^{k+1}\right)^{-1}\) and \(g^{-(k+1)}\) are both solutions to the linear equation \(g^{k+1} x = 1\text{.}\) Hence \(g^{-(k+1)} = \left(g^{k+1}\right)^{-1}\) by Corollary 2.32. Therefore for all \(n \in \N\text{,}\) \(g^{-n} = \left(g^n\right)^{-1}\text{.}\)
🔗
🔗

Proof.

We have already handled the case where \(m\) and \(n\) are both positive. Since we have defined \(g^{-m - n} = \left(g^{-1}\right)^{m+n}\text{,}\) we obtain
\begin{equation*} g^{-m}g^{-n} = g^{-m - n} = g^{-n - m} = g^{-n}g^{-m} \end{equation*}
from the first case.
🔗
Assume one of \(m\) and \(n\) is zero. Since addition is commutative, we may assume without loss of generality that \(m = 0\) and
\begin{equation*} g^{0+n} = g^n = g^0 g^n = g^n g^0 = g^{n+0}\text{.} \end{equation*}
🔗
It remains only to show the equality holds when \(m\) and \(n\) have opposite signs. Since addition is commutative, we may assume without loss of generality that \(m,n \in \N\) and prove that
\begin{equation*} g^{m-n} = g^mg^{-n}\text{.} \end{equation*}
We have already proven that
\begin{equation*} g^{m-m} = g^0 = 1 = g^mg^{-m}\text{,} \end{equation*}
so we may assume \(m \neq n\text{.}\) Hence either \(m \lt n\) or \(n \lt m\text{.}\)
🔗
When \(m \lt n\text{,}\) \(n - m \in \N\) implies
\begin{align*} g^{m-n} \amp= g^{-(n-m)}\\ \amp= \left(g^{-1}\right)^{n-m}\\ \amp= g^{m}\left(g^{-1}\right)^m\left(g^{-1}\right)^{n-m}\\ \amp= g^m\left(g^{-1}\right)^{m+n-m}\\ \amp= g^m\left(g^{-1}\right)^n\\ \amp= g^mg^{-n} \end{align*}
🔗
When \(n \lt m\text{,}\) \(m - n \in \N\) implies
\begin{align*} g^{m - n} \amp= g^{m-n}g^ng^{-n}\\ \amp= g^{m-n + n}g^{-n}\\ \amp= g^{m}g^{-n} \end{align*}
Therefore for all \(g \in G\text{,}\) for all \(m,n \in \Z\text{,}\) \(g^{m+n} = g^mg^n\text{.}\)
🔗
🔗

Proof.

We proceed by induction on \(n\text{.}\) The base case \(n=1\) holds by assumption:
\begin{equation*} ab^1 = ab = ba = b^1a\text{.} \end{equation*}
🔗
Let \(k \in \N\) be given. Assume \(ab^k = b^ka\text{.}\) By the induction hypothesis,
\begin{align*} ab^{k+1} \amp= a\left(b^kb\right)\\ \amp= \left(ab^k\right)b\\ \amp= \left(b^ka\right)b\\ \amp= b^k(ab)\\ \amp= b^k(ba)\\ \amp= \left(b^kb\right)a\\ \amp= b^{k+1}a \end{align*}
Therefore for all \(a,b \in G\text{,}\) if \(ab = ba\text{,}\) then for all \(n \in \N\text{,}\) \(ab^n = b^na\) by induction.
🔗
🔗

Proof.

We proceed by induction on \(n\text{.}\) The base case \(n=1\) holds because \((ab)^1 = ab = a^1b^1\text{.}\)
🔗
Let \(k \in \N\) be given. Assume \((ab)^k = a^kb^k = b^ka^k\text{.}\) By the induction hypothesis and Lemma 7.7,
\begin{align*} (ab)^{k+1} \amp= (ab)^k(ab)\\ \amp=a^kb^k(ab)\\ \amp= a^k\left(b^ka\right)b\\ \amp= a^k\left(ab^k\right)b\\ \amp= \left(a^ka\right)\left(b^kb\right)\\ \amp= a^{k+1}b^{k+1}\text{.} \end{align*}
Hence for all \(a,b \in G\text{,}\) if \(ab = ba\text{,}\) then for all \(n \in \N\text{,}\) \((ab)^n = a^nb^n\) by induction.
🔗
🔗

Proof.

First, observe that \((ab)^0 = 1 = a^0b^0\text{.}\) Let \(n \in \N\) be given. Then
\begin{align*} (ab)^{-n} \amp= \left((ab)^{-1}\right)^n\\ \amp=\left((ba)^{-1}\right)^n\\ \amp= \left(a^{-1}b^{-1}\right)^n\\ \amp= \left(a^{-1}\right)^n\left(b^{-1}\right)^n\\ \amp= a^{-n}b^{-n}\text{.} \end{align*}
Therefore for all \(a,b \in G\text{,}\) if \(ab = ba\text{,}\) then for all \(n \in \Z\text{,}\) \((ab)^n = a^nb^n\text{.}\)
🔗
🔗

Proof.

Let \(g \in G\) and \(n \in \N\) be given. We first prove the result for \(m \in \N\) by induction. When \(m = 1\text{,}\)
\begin{equation*} g^{(1)n} = g^n = \left(g^1\right)^n\text{.} \end{equation*}
🔗
Let \(k \in \N\) be given. Assume \(g^{kn} = \left(g^k\right)^n\text{.}\) By the induction hypothesis and Corollary 7.9
\begin{align*} g^{(k+1)n} \amp= g^{kn + n}\\ \amp= g^{kn}g^n\\ \amp= g^{nk}g^n\\ \amp= \left(g^n\right)^kg^n\\ \amp= \left(g^n\right)^{k+1}\text{.} \end{align*}
Hence for all \(g \in G\text{,}\) for all \(m \in \Z\text{,}\) for all \(n \in \N\text{,}\)
\begin{equation*} g^{mn} = \left(g^m\right)^n\text{.} \end{equation*}
by induction.
🔗
We extend to \(\Z\) by the observation that \(g^{0n} = g^0 = 1 = \left(g^0\right)^n\) and
\begin{align*} g^{(-m)n} \amp= g^{-(mn)}\\ \amp= \left(g^{-1}\right)^{mn}\\ \amp= \left(\left(g^{-1}\right)^m\right)^n\\ \amp= \left(g^{-m}\right)^n\text{.} \end{align*}
Therefore for all \(g \in G\text{,}\) for all \(m,n \in \Z\text{,}\) \(g^{mn} = \left(g^m\right)^n\text{.}\)
🔗
🔗

Remark 7.11.

When \(G\) is an additive group we denote by \(0\) the identity for the binary operation on \(G\) and write \(-g\) for the inverse of \(g\) under addition. In this case, we utilize the familiar notation
\begin{equation*} ng = \sum_{i=1}^n g = \underbrace{g + g + \cdots + g}_n \end{equation*}
to indicate repeated addition. The results above, when translated into this notation, can be stated as \(0g = 0\text{,}\) \((-n)g = n(-g) = -(ng)\text{,}\) \((m+n)g = mg + ng\text{,}\) and \((mn)g = m(ng) = n(mg)\text{.}\)
🔗
🔗
🔗

Section 7.2 Cyclic Subgroup and Cyclic Groups

Proof.

It is clear that \(g \in \langle g \rangle\) implies \(\langle g \rangle\) is non-empty. For all \(m,n \in \Z\text{,}\)
\begin{equation*} g^m g^{-n} = g^{m - n} \in \langle g \rangle\text{.} \end{equation*}
Therefore \(\langle g \rangle\) is a subgroup of \(G\) by The Subgroup Criterion.
🔗
🔗

Remark 7.13.

When \(G\) is an additive group, \(\langle g \rangle = \left\{ng \;\middle\vert\; n \in \Z\right\}\text{.}\)
🔗
🔗

Definition 7.14. Cyclic Subgroups and Cyclic Groups.

Assume \(G\) is a group. We say a subgroup \(H\) is a cyclic subgroup of \(G\) if there exists \(h \in H\) such that \(H = \langle h \rangle\text{.}\) We say that \(h\) generates the subgroup \(H\) or that \(h\) is a generator for \(H\text{.}\)
🔗
If there exists \(g \in G\) such that \(G = \langle g \rangle\text{,}\) then we say \(G\) is a cyclic group.
🔗
🔗
🔗

Section 7.3 Basic Examples

Example 7.15. Integers.

The additive group of integers is cyclic and generated by \(1\) because \(0 = 0(1)\) and for every \(n \in \N\text{,}\)
\begin{equation*} n = \underbrace{1 + 1 + \cdots + 1}_n = n(1)\text{,} \end{equation*}
and
\begin{equation*} -n = \underbrace{-1 - 1 - \cdots - 1}_n = (-n)1\text{.} \end{equation*}
🔗
🔗

Example 7.16. Integers Modulo \(n\).

Given \(n \in \Z\text{,}\) the group
\begin{equation*} \Z/n\Z = \{\overline{0}, \overline{1}, \ldots, \overline{n-1}\} \end{equation*}
is cyclic because, e.g., for every \(\overline{a} \in \Z/n\Z\text{,}\)
\begin{equation*} \overline{a} = \overline{\underbrace{1 + 1 + \cdots + 1}_a} = \underbrace{\overline{1} + \overline{1} + \cdots + \overline{1}}_a = a \left(\overline{1}\right) \end{equation*}
🔗
🔗
🔗

Section 7.4 The Structure of Cyclic Groups

In a sense, these are the only cyclic groups. Moreover, the structure of a cyclic group is incredibly rigid. To see this, we’ll need to build up a little machinery.
🔗

Definition 7.17. Order of an Element.

Assume \(G\) is a group. For every \(g \in G\text{,}\) we define the order of \(g\) in \(G\) to be the smallest positive integer solution to the equation \(g^x = 1\text{.}\) If no such integer exists, we say that the order of \(g\) is infinite.
🔗
We denote the order of \(g\) in the group \(G\) by \(\abs{g}\text{.}\)
🔗
🔗

Proof.

Assume \(\abs{g} = \infty\text{.}\) Observe that \(g^0 = 1\) by definition. For every \(n \in \N\text{,}\) \(g^n \neq 1\) by Definition 7.17. This must also hold for the negative integers, for if there exists \(n \in \N\) such that \(g^{-n} = 1\text{,}\) then
\begin{equation*} g^n = g^{(-n)(-1)} = \left(g^{-n}\right)^{-1} = 1^{-1} = 1\text{,} \end{equation*}
a contradiction. Hence if \(\abs{g} = \infty\text{,}\) then the only integer solution to \(g^x = 1\) is \(x = 0\text{.}\)
🔗
Conversely, assume the only integer solution to \(g^x = 1\) is \(x = 0\text{.}\) Then for every positive integer, \(n\text{,}\) \(g^n \neq 1\text{.}\) Hence \(\abs{g} = \infty\) by Definition 7.17. Therefore \(\abs{g} = \infty\) if and only if the only integer solution to \(g^x = 1\) is \(x = 0\text{.}\)
🔗
🔗

Remark 7.19.

We note the order of \(g \in G\) is precisely the number of elements in the subgroup \(\langle g \rangle \leq G\text{.}\) Hence if \(G\) is a cyclic group, then the cardinality of \(G\) is equal to the order of a generator. This at least partially justifies the following abuse of language.
🔗
🔗

Definition 7.20. Order of a Group.

Assume \(G\) is a group. The order of \(G\) is the cardinality of the set \(G\text{.}\) We denote the order of \(G\) by the same notation as the cardinality, \(\lvert G \rvert\text{.}\)
🔗
🔗

Proof.

We leave the proof as an exercise for the reader.
🔗
🔗

Proof.

Assume \(n \mid m\text{.}\) There exists \(k \in \Z\) such that \(m = kn\) and thus
\begin{equation*} g^m = g^{mk} = \left(g^n\right)^k = 1^k = 1 \end{equation*}
by Proposition 7.10.
🔗
Conversely, assume that \(g^m = 1\text{.}\) Suppose to the contrary that \(m\) is not a multiple of \(n\text{.}\) By definition, \(n\) is the smallest integer that satisfies the equation \(g^x = 1\) and hence \(n \leq m\text{.}\) Use the Euclidean algorithm to produce non-negative integers \(q\) and \(0 \lt r \lt n \) that satisfy \(m = qn + r\) (see Appendix A). Now observe that
\begin{equation*} 1 = g^m = g^{qn + r} = \left(g^n\right)^qg^r = g^r \end{equation*}
contradicts the assumption that \(n\) is the smallest integer solution to the equation \(g^x = 1\text{.}\) Therefore \(m = qn\) is divisible by \(n\text{,}\) as desired.
🔗
🔗

Proof.

Since the order of the element \(g\) is either finite or infinite, there are two cases to handle.
🔗
First assume that \(\abs{g} = \infty\text{.}\) Define the function
\begin{align*} \varphi \colon \Z \amp\to G\\ n \amp\mapsto g^n \end{align*}
and note that it is a morphism of groups by Proposition 7.3 because
\begin{equation*} \varphi(m + n) = g^{m + n} = g^m g^n = \varphi(m) \varphi(n)\text{.} \end{equation*}
🔗
To see this morphism is surjective, observe that for every \(a \in G\text{,}\) there exists \(n \in \Z\) such that \(a = g^n = \phi(n)\text{.}\)
🔗
To see that \(\varphi\) is injective, observe that
\begin{equation*} \phi(x) = g^x = 1 \iff x = 0 \end{equation*}
by Proposition 7.18. Hence \(\ker{\varphi} = \{0\}\) implies \(\phi\) is injective by Theorem 6.17. Therefore if \(G\) is an infinite cyclic group, \(G \cong \Z\text{.}\)
🔗
Now assume there exists \(n \in \N\) such that \(\abs{g} = n\text{.}\) Let \(a,b \in \Z\) be given. By Proposition 7.22,
\begin{align*} g^a = g^b \amp\iff 1 = g^{b - a}\\ \amp\iff n \mid b - a \\ \amp\iff a \equiv b \pmod{n}\\ \amp\iff \overline{a} = \overline{b} \in \Z/n\Z \end{align*}
from which it follows the function
\begin{align*} \varphi \colon \Z/n\Z \amp\to G\\ \overline{a} \amp\mapsto g^a \end{align*}
is a well-defined injection. Moreover, \(\varphi\) is a morphism of groups because
\begin{equation*} \varphi(\overline{a} + \overline{b}) = \varphi(\overline{a + b}) = g^{a + b} = g^a g^b = \varphi(\overline{a}) \varphi(\overline{b}) \end{equation*}
by Proposition 7.3.
🔗
To show that \(\varphi\) is surjective, let \(g^\prime \in G\) be given. By assumption, there exists \(a \in \Z\) such that \(g^\prime = g^a = \varphi(\overline{a})\text{.}\) Hence \(\varphi\) is surjective. Therefore if \(G\) is a finite cyclic group, there exists \(n \in \Z\) such that \(G \cong \Z/n\Z\text{.}\)
🔗
🔗

Example 7.24. Primitive Roots of Unity.

Recall that for \(n \in \N\text{,}\) we defined \(\zeta = e^{i\frac{2\pi}{n}} \in \C\) to be an \(n^\text{th}\) root of unity. We observed that all other \(n^\text{th}\) roots of unity can be obtained by rotating (counter-clockwise) along the circle by \(2\pi/n\text{.}\) Using the complex exponential notation, this says the \(n^\text{th}\) roots of unity are
\begin{equation*} U_n = \left\{1,\, \zeta,\, \zeta^2,\, \zeta^3,\, \ldots,\, \zeta^{n-1}\right\} = \langle \zeta \rangle\text{.} \end{equation*}
This establishes that \(U_n\) is a cyclic group. We call a generator for \(U_n\text{,}\) such as \(e^{i\frac{2\pi}{n}}\text{,}\) a primitive \(n^\text{th}\) root of unity. By Proposition 7.23, \(U_n \cong \Z/n\Z\text{.}\)
🔗
🔗

Proof.

  1. Assume that \(\abs{g} = \infty\text{.}\) Let \(\varphi \colon \Z \to \langle g \rangle\) be the isomorphism from Proposition 7.23. Let \(m \in \Z \setminus \{0\}\) be given. For every \(n \in \N\text{,}\) \(mn \neq 0\) and hence
    \begin{equation*} \left(g^m\right)^n = g^{mn} = \varphi(mn) \neq \varphi(0) = 1. \end{equation*}
    Therefore \(\abs{g^m} = \infty\text{.}\)
    🔗
    🔗
  2. Assume there exists \(n \in \N\) such that \(\abs{g} = n\text{.}\) Let \(m \in \Z\) be given and let \(d = \operatorname{gcd}(m,n)\text{.}\) If \(m = 0\text{,}\) then \(d = n\) and \(g^0 = 1\) has order
    \begin{equation*} 1 = \frac{n}{n} = \frac{n}{\operatorname{gcd}(0,n)}. \end{equation*}
    Hence we may assume \(m \neq 0.\)
    🔗
    There exist integers \(m^\prime, n^\prime\) such that \(m = dm^\prime\) and \(n = dn^\prime\text{.}\) Hence
    \begin{equation*} \left(g^m\right)^{n^\prime} = g^{mn^\prime} = g^{(dm^\prime) n^\prime} = g^{(dn^\prime) m^\prime}= g^{nm^\prime} = \left(g^n\right)^{m^\prime} = 1 \end{equation*}
    implies there exists \(k \in \N\) so that \(k = \abs{g^m}\text{.}\) Moreover, \(k \mid n^\prime\) by Proposition 7.22.
    🔗
    Since \(n\) is the order of \(g\) and \(g^{mk} = \left(g^m\right)^k = 1\text{,}\) Proposition 7.22 implies that \(n\) divides \(mk\text{.}\) By definition of divisibility, there exists \(\ell \in \Z\) such that
    \begin{equation*} mk = n\ell \iff \left(dm^\prime\right) k = \left(dn^\prime\right) \ell \iff m^\prime k = n^\prime\ell. \end{equation*}
    Hence \(n^\prime \mid m^\prime k\text{.}\) Since \(d\) is the greatest common divisor of \(m\) and \(n\text{,}\) there exist \(x,y \in \Z\) such that
    \begin{align*} d \amp= mx + ny\\ \amp= dm^\prime x + dn^\prime y\\ \amp= d(m^\prime x + n^\prime y) \end{align*}
    and, dividing both sides by \(d\text{,}\) we obtain \(1 = m^\prime x + n^\prime y\text{.}\) Hence the greatest common divisor of \(m^\prime\) and \(n^\prime\) is \(1\) by Proposition A.9. Apply Proposition A.10 to see that \(n^\prime \mid k\text{.}\) Since divisibility is antisymmetric, \(n \mid k^\prime\) and \(k^\prime \mid n\) imply \(n = k^\prime\text{.}\) Therefore
    \begin{equation*} \abs{g^m} = k = n^\prime = \frac{dn^\prime}{d} = \frac{n}{d} = \frac{n}{\operatorname{gcd}(m,n)}\text{.} \end{equation*}
    🔗
    🔗
🔗
🔗

Proof.

  1. Let \(\varphi \colon \Z \to G\) be the isomorphism from Proposition 7.23. If \(a = 1\text{,}\) then \(G = \langle g \rangle\) by assumption. If \(a = -1\text{,}\) then
    \begin{align*} \langle g^{-1} \rangle \amp= \left\{\left(g^{-1}\right)^n \;\middle\vert\; n \in \Z\right\}\\ \amp= \left\{g^{-n} \;\middle\vert\; n \in \Z\right\}\\ \amp= \left\{g^n \;\middle\vert\; n \in \Z\right\}\\ \amp= \langle g \rangle\\ \amp = G \end{align*}
    🔗
    Conversely, assume \(G = \langle g^a \rangle\text{.}\) For every \(b \in \Z\text{,}\) there exists \(c \in \Z\) such that
    \begin{equation*} \varphi(b) = g^b = \left(g^a\right)^c = g^{ac} = \varphi(ac)\text{.} \end{equation*}
    In particular, if \(b = 1\text{,}\) then \(ac = 1\) because \(\varphi\) is injective. Hence \(a = c = 1\) or \(a = c = -1\text{.}\) Therefore \(\langle g^a \rangle = G\) if and only if \(a \in \{\pm 1\}\text{.}\)
    🔗
    🔗
  2. Let \(\varphi \colon \Z/n\Z \to G\) be the isomorphism from Proposition 7.23. Assume \(a \in \Z\) and \(\operatorname{gcd}(a,n) = 1\text{.}\) By Proposition A.9 there exist \(x,y \in \Z\) such that \(ax + ny = 1\text{.}\) Let \(h \in G\) be given. By assumption, there exists \(b \in \Z\) such that \(h = \varphi(\overline{b}) = g^b\text{.}\) Hence
    \begin{align*} h \amp= \varphi(\overline{b})\\ \amp = \varphi(\overline{b(ax + ny}))\\ \amp = \varphi(\overline{abx} + \overline{bny})\\ \amp = \varphi(\overline{abx}) + \varphi(\overline{bny})\\ \amp = \varphi(\overline{abx}) + \varphi(\overline{0})\\ \amp = g^{abx}g^{0}\\ \amp = \left(g^a\right)^{bx} \end{align*}
    implies \(G = \langle g \rangle\text{.}\)
    🔗
    Conversely, assume that \(G = \langle g^a \rangle\text{.}\) For every \(b \in \Z\text{,}\) there exists \(c \in \Z\) such that
    \begin{equation*} \varphi(\overline{b}) = g^b = \left(g^a\right)^c = g^{ac} = \varphi(\overline{ac}). \end{equation*}
    In particular, for \(b = 1\text{,}\) there exists \(c \in \Z\) such that
    \begin{align*} \overline{ac} = \overline{1} \amp \iff ac \equiv 1 \pmod{n}\\ \amp \iff \exists d \in \Z,\, ac - 1 = dn\\ \amp \iff \exists d \in \Z,\, ac + (-d)n = 1. \end{align*}
    Hence \(\operatorname{gcd}(a,n) = 1\) by Proposition A.9. Therefore \(G = \langle g^a \rangle\) if and only if \(\operatorname{gcd}(a,n) = 1\text{.}\)
    🔗
    🔗
🔗
🔗

Proof.

Assume \(H\) is a subgroup of the cyclic group \(G = \langle g \rangle\text{.}\) The trivial group \(\{1\} = \langle 1 \rangle\) is cyclic, so we assume that \(H\) is nontrivial. Define the set
\begin{equation*} E = \left\{e \in \Z \;\middle\vert\; g^e \in H\right\} \subseteq \Z \end{equation*}
and note it is non-empty and symmetric about \(0\) because
\begin{equation*} e \in E \iff g^e \in H \iff g^{-e} = \left(g^{e}\right)^{-1} \in H \iff -e \in E\text{.} \end{equation*}
Moreover, the assumption that \(H\) is non-trivial implies the existence of a non-zero element of \(E\) and thus
\begin{equation*} E_+ = E \cap \N \subseteq \N \end{equation*}
is non-empty. By the Well-Ordering Principle, \(E_+\) admits a minimum, \(m \in E_+\text{.}\) We prove that \(H = \langle g^m \rangle\text{.}\)
🔗
Suppose to the contrary that \(H \setminus \langle g^m \rangle\) is non-empty. By assumption, the set
\begin{equation*} F = \left\{e \in E \;\middle\vert\; g^e \not \in \langle g^m \rangle\right\} \subseteq E \end{equation*}
is necessarily non-empty and symmetric about zero because
\begin{equation*} e \in F \iff g^{e} \not \in \langle g^m \rangle \iff g^{-e} = \left(g^{e}\right)^{-1} \not\in \langle g^m \rangle \iff -e \in F\text{.} \end{equation*}
Since \(F\) is nonempty and \(g^0 = 1 \in \langle g^m \rangle\) implies \(0 \not \in F\text{,}\) it follows that \(F_+ = F \cap \N \subseteq E_+ \subseteq \N\) is non-empty. By the Well-Ordering Principle, \(F_+\) admits a minimum element, \(n\text{.}\)
🔗
We observe that \(n \in F_+ \subseteq E_+\) implies \(m \lt n\) and thus \(0 \lt n - m \lt n\text{.}\) Minimality of \(n\) forces \(g^{n-m} \in \langle g^m \rangle\text{.}\) Since \(\langle g^m \rangle\) is closed under multiplication,
\begin{equation*} g^n = g^{n-m + m} = g^{n-m}g^m \in \langle g^m \rangle \end{equation*}
implies \(n \not\in F_+\text{,}\) a contradiction. Therefore \(H = \langle g^m \rangle\text{,}\) as desired.
🔗
🔗

Proof.

Let \(S\) be the set of subgroups of \(G\text{.}\) Let \(\varphi \colon \Z \to G\) be the isomorphism from Proposition 7.23 and note that
\begin{equation*} g^m = g^n \iff \varphi(m) = \varphi(n) \iff m = n\text{.} \end{equation*}
🔗
Define the function
\begin{align*} f \colon \N \cup \{0\} \amp\to S\\ n \amp\mapsto \langle g^n \rangle \end{align*}
and note that it is surjective by Theorem 7.27.
🔗
To see that \(f\) is injective, assume \(a \leq b \in \N \cup \{0\}\) and \(\langle g^a \rangle = \langle g^b \rangle\text{.}\) Note that if \(a = 0\text{,}\) then \(\langle g^b \rangle = \langle 1 \rangle = \{1\}\) implies \(g^b = 1\) and thus \(b = 0\text{.}\) Hence we may assume that \(a \in \N\text{.}\)
🔗
Since \(g^a \in \langle g^b \rangle\) and \(g^b \in \langle g^a \rangle\text{,}\) there exist \(m,n \in \Z\) such that
\begin{align*} g^a = \left(g^b\right)^m = g^{bm} \amp\iff a = bm \iff b \mid a,\,\text{and}\\ g^b = \left(g^a\right)^n = g^{an} \amp\iff b = an \iff a \mid b \end{align*}
Antisymmetry of the divisibility relation implies \(a = b\) and thus \(\varphi\) is injective. Therefore \(f\) is a bijection.
🔗
🔗

Example 7.29. Subgroups of \(\Z\).

Every integer generates a subgroup
\begin{equation*} n\Z = \left\{nk \;\middle\vert\; k \in \Z\right\} \leq \Z\text{.} \end{equation*}
The content of Corollary 7.28 is that these are all of the subgroups of \(\Z\text{.}\) Note that when \(n \neq 0\text{,}\) these subgroups are infinite by Proposition 7.25 and cyclic by Theorem 7.27, hence isomorphic to \(\Z\) via
\begin{align*} \varphi \colon \Z \amp\to n\Z\\ x \amp\mapsto nx \end{align*}
🔗
🔗

Proof.

Let \(S\) be the set of subgroups of \(G\) and define the function
\begin{align*} f \colon D \amp\to S\\ d \amp\mapsto \langle g^d \rangle \end{align*}
By Theorem 7.27 the only subgroups of \(G\) are of the form \(\langle g^a \rangle\) for \(0 \leq a \in \Z\text{.}\) Given \(0 \leq a \in \Z\text{,}\) let \(d = \operatorname{gcd}(a,n)\text{.}\) There exists \(a^\prime \in \Z\) such that \(a = a^\prime d\text{.}\) Hence
\begin{equation*} g^a = g^{a^\prime d} = \left(g^d\right)^{a^\prime} \in \langle g^d \rangle \end{equation*}
implies \(\langle g^a \rangle \subseteq g^d\text{.}\) Now observe
\begin{equation*} \abs{g^a} = \frac{n}{\operatorname{gcd}(a,n)} = \frac{n}{d} = \frac{n}{\operatorname{gcd}(d,n)} = \abs{g^d} \end{equation*}
by Proposition 7.25 and thus \(f(d) = \langle g^d \rangle = \langle g \rangle\text{.}\) Hence \(f\) is surjective.
🔗
It remains only to show that \(f\) is injective. Assume \(a, b \in D\) and \(\langle g^a \rangle = \langle g^b \rangle\text{.}\) By Proposition 7.25
\begin{equation*} \frac{n}{a} = \abs{g^a} = \abs{\langle g^a \rangle} = \abs{\langle g^b \rangle} = \abs{g^b} = \frac{n}{b} \iff nb = na \iff a = b. \end{equation*}
Therefore \(f\) is a bijection.
🔗
🔗

Example 7.31. Subgroups of \(\Z/60\Z\).

To find the subgroups of \(\Z/60\Z\text{,}\) it suffices to write down all of the divisors by Corollary 7.30. We can use Proposition 7.25 to find a generator for each one as follows: Given a divisor \(d\) of \(60\text{,}\) write \(n = 60/d\) so the order of \(\overline{n} \in \Z/60\Z\) is
\begin{equation*} \abs{\overline{n}} = \frac{60}{\gcd(60,n)} = \frac{60}{n} = d\text{.} \end{equation*}
Hence \(\langle \overline{n} \rangle\) is the unique group of order \(d\) in \(\Z/60\Z\text{.}\)
🔗
From the factorization \(60 = 2^2(3)(5)\text{,}\) we see the divisors are
\begin{equation*} 1,\, 2,\, 3,\, 4,\, 5,\, 6,\, 10,\, 12,\, 15,\, 20,\, 30,\,\text{and}\ 60\text{.} \end{equation*}
This means the 12 subgroups of \(\Z/60\Z\text{,}\) arranged from order 1 to order 60, are
\begin{equation*} \langle \overline{0} \rangle, \langle \overline{30} \rangle, \langle \overline{20} \rangle, \langle \overline{15} \rangle, \langle \overline{12} \rangle, \langle \overline{10} \rangle, \langle \overline{6} \rangle, \langle \overline{5} \rangle, \langle \overline{4} \rangle, \langle \overline{2} \rangle, \langle \overline{1} \rangle = \Z/60\Z. \end{equation*}
🔗
🔗

Remark 7.32.

It should be pointed out that most of the generators from Example 7.31 are not unique. If \(d\) is a divisor of \(60\text{,}\) the subgroup generated by \(\overline{d}\) has order \(n = 60/d\text{.}\) For every positive integer \(a \lt n\) that is coprime to \(n\)—i.e. \(\gcd(a,n) = 1\)—the element \(a\overline{d} \in \langle \overline{d}\rangle\) is also a generator for the subgroup \(\langle \overline{d}\rangle\) of order \(n\) because
\begin{equation*} \abs{a\overline{d}} = \frac{n}{\gcd(a,n)} = \frac{n}{1} = n\text{.} \end{equation*}
🔗
As a concrete example, consider the subgroup
\begin{equation*} \langle \overline{4} \rangle = \{\overline{0}, \overline{4}, \overline{8}, \overline{12}, \overline{16}, \overline{20}, \overline{24}, \overline{28}, \overline{32}, \overline{36}, \overline{40}, \overline{44}, \overline{48}, \overline{52}, \overline{56}\} \end{equation*}
of order 15. The integers 1, 2, 4, 7, 8, 11, 13, and 14 are the only positive integers less than 15 and coprime to 15. Hence \(\overline{8}\text{,}\) \(\overline{16}\text{,}\) \(\overline{28}\text{,}\) \(\overline{44}\text{,}\) \(\overline{52}\text{,}\) and \(\overline{56}\) are also generators for the subgroup of order 15.
🔗
If we choose to use a generator of the form \(a\overline{d}\) instead of \(\overline{d}\text{,}\) we obtain a permutation of the elements. For example, if we were to generate \(\langle \overline{4} \rangle\) using the element \(\overline{16}\text{,}\) then we obtain the elements of this subgroup in the following order:
\begin{equation*} \{\overline{0}, \overline{16}, \overline{32}, \overline{48}, \overline{4}, \overline{20}, \overline{36}, \overline{52}, \overline{8}, \overline{24}, \overline{40}, \overline{56}, \overline{12}, \overline{28}, \overline{44}\}\text{.} \end{equation*}
🔗
🔗
🔗

Exercises 7.5 Exercises for Undergrads & Grads

1.

Let \(G\) be a group with a finite number of elements. Show that for all \(a \in G\text{,}\) there exists \(n \in \N\) such that \(a^n = 1\text{.}\)
🔗
Hint.
Let \(k\) be the number of elements of \(G\text{.}\) Consider the set \(\{a, a^2, \ldots, a^k, a^{k+1}\} \subseteq G\text{.}\)
🔗
🔗
Solution.
Assume \(G\) is a group with \(k\) elements. Let \(a \in G\) be given and let \(S =\{a,a^2,\ldots,a^k,a^{k+1}\}\text{.}\) Since \(S \subseteq G\) and the list \(a, a^2, \ldots, a^{k+1}\) has \(k+1\) elements, it follows that there exist \(m \neq n \in \N\) such that \(a^m = a^n\text{.}\) Without loss of generality, we may assume that \(m \lt n\) and thus
\begin{equation*} 1 = a^{-m}a^m = a^{-m}a^n = a^{n - m}\text{.} \end{equation*}
Therefore for all \(a \in G\text{,}\) there exists \(n \in \N\) such that \(a^n = 1\text{.}\)
🔗
🔗
🔗

2.

Prove that a nonempty subset of a finite group is a subgroup if and only if it is closed under the group operation.
🔗
Hint.
🔗
Solution.
Assume \(G\) is a finite group and \(\emptyset \neq H \subseteq G\text{.}\) If \(H \leq G\text{,}\) then \(H\) is closed under multiplication.
🔗
Conversely, assume \(H\) is closed under the group operation. By Exercise 7.5.1, there exists \(n \in \N\) such that \(1 = a^n \in H\text{.}\) Hence \(H\) is non-empty. Since \(H\) is assumed to be closed under the operation, it suffices to show for all \(a \in H\text{,}\) \(a^{-1} \in H\) by The Subgroup Criterion.
🔗
Let \(a \in H\) be given. By Exercise 7.5.1, there exists \(n \in \N\) such that \(a^n = 1\text{.}\) If \(n = 1\text{,}\) then \(a = 1\) and \(a^{-1} = 1 \in H\text{.}\) Otherwise, \(1 \lt n\) implies \(n - 1 \in \N\) and hence
\begin{equation*} aa^{-1} = 1 = a^n = aa^{n-1} \end{equation*}
implies \(a^{-1} = a^{n-1} \in H\) by Left Cancellation. Therefore \(H\) is a group.
🔗
🔗
🔗

3. Orbits.

Assume \(X\) is a set. Fix a permutation \(\sigma \in S_X\text{.}\) For all \(a \in X\text{,}\) define the orbit of \(a\) under \(\sigma\) to be the set
\begin{equation*} \mathcal{O}_{a,\sigma} = \left\{\sigma^n(a) \;\middle\vert\; n \in \Z\right\}\text{.} \end{equation*}
🔗
Define the following equivalence relation on \(X\text{:}\) for all \(a,b \in X\text{,}\) \(a \sim_\sigma b\) if and only if there exists an integer \(n\) such that \(\sigma^n(a) = b\text{.}\)
🔗
Prove that \(\sim_\sigma\) is an equivalence relation on \(X\text{.}\) Conclude that \(\mathcal{O}_{a,\sigma}\) is the equivalence class of \(a\) under \(\sim_\sigma\text{.}\)
🔗
Solution.
We must prove that \(\sim_\sigma\) is reflexive, symmetric, and transitive.
Reflexive
🔗
Let \(a \in X\) be given. Then \(\sigma^0(a) = \id_X(a) = a\text{.}\) Hence \(a \sim_\sigma a\text{.}\) Therefore \(\sim_\sigma\) is reflexive.
🔗
Symmetric
🔗
Let \(a,b \in X\) be given. Assume \(a \sim_\sigma b\text{.}\) There exists \(n \in \N\) such that \(\sigma^n(a) = b\text{.}\) By Theorem 7.6,
\begin{align*} a \amp= \id_X(a)\\ \amp= \sigma^0(a)\\ \amp= \sigma^{-n + n}(a)\\ \amp= \sigma^{-n} \circ \sigma(a)\\ \amp= \sigma^{-n}(b) \end{align*}
Hence \(b \sim a\text{.}\) Therefore \(\sim_\sigma\) is symmetric.
🔗
Transitive
🔗
Let \(a,b,c \in X\) be given. Assume \(a \sim b\) and \(b \sim c\text{.}\) There exist \(m,n \in \Z\) satisfying \(\sigma^m(a) = b\) and \(\sigma^n(b) = c\text{.}\) By Theorem 7.6,
\begin{align*} \sigma^{n+m}(a) \amp= \sigma^n \circ \sigma^m(a)\\ \amp= \sigma^n(b)\\ \amp= c \end{align*}
Hence \(a \sim c.\text{.}\) Therefore \(\sim_\sigma\) is transitive.
🔗
🔗
Finally, the equivalence class of \(a\) under \(\sim_\sigma\) is
\begin{align*} \left[a\right] \amp= \left\{b \in X \;\middle\vert\; a \sim_\sigma b\right\}\\ \amp= \left\{b \in X \;\middle\vert\; \exists n \in \Z,\, \sigma^n(a) = b\right\}\\ \amp= \left\{\sigma^n(a) \;\middle\vert\; n \in \Z\right\}\\ \amp= \mathcal{O}_{a,\sigma}\text{.} \end{align*}
🔗
🔗
🔗
🔗
🔗
PrevTopNext