<section>
<title>Subgroups of a Cyclic Group</title>
<p>
We can ask some interesting questions about cyclic subgroups of a group and subgroups of a cyclic group.
If <m>G</m> is a group, which subgroups of <m>G</m> are cyclic?
If <m>G</m> is a cyclic group,
what type of subgroups does <m>G</m> possess?
</p>
<theorem xml:id="theorem-cyclic-subgroups">
<statement>
<p>
Every subgroup of a cyclic group is cyclic.
</p>
</statement>
<proof>
<p>
The main tools used in this proof are the division algorithm and the Principle of Well-Ordering.
Let <m>G</m> be a cyclic group generated by <m>a</m> and suppose that <m>H</m> is a subgroup of <m>G</m>.
If <m>H = \{ e \}</m>, then trivially <m>H</m> is cyclic.
Suppose that <m>H</m> contains some other element <m>g</m> distinct from the identity.
Then <m>g</m> can be written as <m>a^n</m> for some integer <m>n</m>.
Since <m>H</m> is a subgroup,
<m>g^{-1} = a^{n}</m> must also be in <m>H</m>.
Since either <m>n</m> or <m>-n</m> is positive,
we can assume that <m>H</m> contains positive powers of <m>a</m> and <m>n \gt 0</m>.
Let <m>m</m> be the smallest natural number such that <m>a^m \in H</m>.
Such an <m>m</m> exists by the Principle of Well-Ordering.
</p>
<p>
We claim that <m>h = a^m</m> is a generator for <m>H</m>.
We must show that every <m>h' \in H</m> can be written as a power of <m>h</m>.
Since <m>h' \in H</m> and <m>H</m> is a subgroup of <m>G</m>,
<m>h' = a^k</m> for some integer <m>k</m>.
Using the division algorithm,
we can find numbers <m>q</m> and <m>r</m> such that
<m>k = mq +r</m> where <m>0 \leq r \lt m</m>; hence,
<me>
a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r
</me>.
So <m>a^r = a^k h^{-q}</m>.
Since <m>a^k</m> and <m>h^{-q}</m> are in <m>H</m>,
<m>a^r</m> must also be in <m>H</m>.
However, <m>m</m> was the smallest positive number such that <m>a^m</m> was in <m>H</m>;
consequently, <m>r=0</m> and so <m>k=mq</m>.
Therefore,
<me>
h' = a^k = a^{mq} = h^q
</me>
and <m>H</m> is generated by <m>h</m>.
</p>
</proof>
</theorem>
<corollary>
<statement>
<p>
The subgroups of <m>{\mathbb Z}</m> are exactly
<m>n{\mathbb Z}</m> for <m>n = 0, 1, 2,\ldots</m>.
</p>
</statement>
</corollary>
<proposition xml:id="proposition-cyclic-subgrp-order">
<statement>
<p>
Let <m>G</m> be a cyclic group of order <m>n</m> and suppose that <m>a</m> is a generator for <m>G</m>.
Then <m>a^k=e</m> if and only if <m>n</m> divides <m>k</m>.
</p>
</statement>
<proof>
<p>
First suppose that <m>a^k=e</m>.
By the division algorithm,
<m>k = nq + r</m> where <m>0 \leq r \lt n</m>; hence,
<me>
e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r
</me>.
Since the smallest positive integer <m>m</m> such that <m>a^m = e</m> is <m>n</m>,
<m>r= 0</m>.
</p>
<p>
Conversely, if <m>n</m> divides <m>k</m>,
then <m>k=ns</m> for some integer <m>s</m>.
Consequently,
<me>
a^k = a^{ns} = (a^n)^s = e^s = e
</me>.
</p>
</proof>
</proposition>
<theorem xml:id="theorem-cyclic-orders">
<statement>
<p>
Let <m>G</m> be a cyclic group of order <m>n</m> and suppose that <m>a \in G</m> is a generator of the group.
If <m>b = a^k</m>, then the order of <m>b</m> is <m>n/d</m>,
where <m>d = \gcd(k,n)</m>.
</p>
</statement>
<proof>
<p>
We wish to find the smallest integer <m>m</m> such that <m>e = b^m = a^{km}</m>.
By <xref ref="proposition-cyclic-subgrp-order" />,
this is the smallest integer <m>m</m> such that <m>n</m> divides <m>km</m> or,
equivalently,
<m>n/d</m> divides <m>m(k/d)</m>.
Since <m>d</m> is the greatest common divisor of <m>n</m> and <m>k</m>,
<m>n/d</m> and <m>k/d</m> are relatively prime.
Hence, for <m>n/d</m> to divide <m>m(k/d)</m> it must divide <m>m</m>.
The smallest such <m>m</m> is <m>n/d</m>.
</p>
</proof>
</theorem>
<corollary xml:id="corollary-cyclic-modngenerators">
<statement>
<p>
The generators of <m>{\mathbb Z}_n</m> are the integers <m>r</m> such that
<m>1 \leq r \lt n</m> and <m>\gcd(r,n) = 1</m>.
</p>
</statement>
</corollary>
<example xml:id="example-cyclic-z16">
<title>A Finite Cyclic Group of Order <m>16</m></title>
<p>
Let us examine the group <m>{\mathbb Z}_{16}</m>.
The numbers 1, 3, 5, 7, 9, 11, 13,
and 15 are the elements of
<m>{\mathbb Z}_{16}</m> that are relatively prime to 16.
Each of these elements generates <m>{\mathbb Z}_{16}</m>.
For example,
<md>
<mrow>1 \cdot 9 & = 9 & 2 \cdot 9 & = 2 & 3 \cdot 9 & = 11</mrow>
<mrow>4 \cdot 9 & = 4 & 5 \cdot 9 & = 13 & 6 \cdot 9 & = 6</mrow>
<mrow>7 \cdot 9 & = 15 & 8 \cdot 9 & = 8 & 9 \cdot 9 & = 1</mrow>
<mrow>10 \cdot 9 & = 10 & 11 \cdot 9 & = 3 & 12 \cdot 9 & = 12</mrow>
<mrow>13 \cdot 9 & = 5 & 14 \cdot 9 & = 14 & 15 \cdot 9 & = 7</mrow>
</md>.
</p>
</example>
</section>
Section 2.2 Subgroups of a Cyclic Group
View Source for section
We can ask some interesting questions about cyclic subgroups of a group and subgroups of a cyclic group. If \(G\) is a group, which subgroups of \(G\) are cyclic? If \(G\) is a cyclic group, what type of subgroups does \(G\) possess?
Theorem 2.2.1.
View Source for theorem
<theorem xml:id="theorem-cyclic-subgroups">
<statement>
<p>
Every subgroup of a cyclic group is cyclic.
</p>
</statement>
<proof>
<p>
The main tools used in this proof are the division algorithm and the Principle of Well-Ordering.
Let <m>G</m> be a cyclic group generated by <m>a</m> and suppose that <m>H</m> is a subgroup of <m>G</m>.
If <m>H = \{ e \}</m>, then trivially <m>H</m> is cyclic.
Suppose that <m>H</m> contains some other element <m>g</m> distinct from the identity.
Then <m>g</m> can be written as <m>a^n</m> for some integer <m>n</m>.
Since <m>H</m> is a subgroup,
<m>g^{-1} = a^{n}</m> must also be in <m>H</m>.
Since either <m>n</m> or <m>-n</m> is positive,
we can assume that <m>H</m> contains positive powers of <m>a</m> and <m>n \gt 0</m>.
Let <m>m</m> be the smallest natural number such that <m>a^m \in H</m>.
Such an <m>m</m> exists by the Principle of Well-Ordering.
</p>
<p>
We claim that <m>h = a^m</m> is a generator for <m>H</m>.
We must show that every <m>h' \in H</m> can be written as a power of <m>h</m>.
Since <m>h' \in H</m> and <m>H</m> is a subgroup of <m>G</m>,
<m>h' = a^k</m> for some integer <m>k</m>.
Using the division algorithm,
we can find numbers <m>q</m> and <m>r</m> such that
<m>k = mq +r</m> where <m>0 \leq r \lt m</m>; hence,
<me>
a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r
</me>.
So <m>a^r = a^k h^{-q}</m>.
Since <m>a^k</m> and <m>h^{-q}</m> are in <m>H</m>,
<m>a^r</m> must also be in <m>H</m>.
However, <m>m</m> was the smallest positive number such that <m>a^m</m> was in <m>H</m>;
consequently, <m>r=0</m> and so <m>k=mq</m>.
Therefore,
<me>
h' = a^k = a^{mq} = h^q
</me>
and <m>H</m> is generated by <m>h</m>.
</p>
</proof>
</theorem>
Every subgroup of a cyclic group is cyclic.
Proof.
View Source for proof
<proof>
<p>
The main tools used in this proof are the division algorithm and the Principle of Well-Ordering.
Let <m>G</m> be a cyclic group generated by <m>a</m> and suppose that <m>H</m> is a subgroup of <m>G</m>.
If <m>H = \{ e \}</m>, then trivially <m>H</m> is cyclic.
Suppose that <m>H</m> contains some other element <m>g</m> distinct from the identity.
Then <m>g</m> can be written as <m>a^n</m> for some integer <m>n</m>.
Since <m>H</m> is a subgroup,
<m>g^{-1} = a^{n}</m> must also be in <m>H</m>.
Since either <m>n</m> or <m>-n</m> is positive,
we can assume that <m>H</m> contains positive powers of <m>a</m> and <m>n \gt 0</m>.
Let <m>m</m> be the smallest natural number such that <m>a^m \in H</m>.
Such an <m>m</m> exists by the Principle of Well-Ordering.
</p>
<p>
We claim that <m>h = a^m</m> is a generator for <m>H</m>.
We must show that every <m>h' \in H</m> can be written as a power of <m>h</m>.
Since <m>h' \in H</m> and <m>H</m> is a subgroup of <m>G</m>,
<m>h' = a^k</m> for some integer <m>k</m>.
Using the division algorithm,
we can find numbers <m>q</m> and <m>r</m> such that
<m>k = mq +r</m> where <m>0 \leq r \lt m</m>; hence,
<me>
a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r
</me>.
So <m>a^r = a^k h^{-q}</m>.
Since <m>a^k</m> and <m>h^{-q}</m> are in <m>H</m>,
<m>a^r</m> must also be in <m>H</m>.
However, <m>m</m> was the smallest positive number such that <m>a^m</m> was in <m>H</m>;
consequently, <m>r=0</m> and so <m>k=mq</m>.
Therefore,
<me>
h' = a^k = a^{mq} = h^q
</me>
and <m>H</m> is generated by <m>h</m>.
</p>
</proof>
The main tools used in this proof are the division algorithm and the Principle of Well-Ordering. Let \(G\) be a cyclic group generated by \(a\) and suppose that \(H\) is a subgroup of \(G\text{.}\) If \(H = \{ e \}\text{,}\) then trivially \(H\) is cyclic. Suppose that \(H\) contains some other element \(g\) distinct from the identity. Then \(g\) can be written as \(a^n\) for some integer \(n\text{.}\) Since \(H\) is a subgroup, \(g^{-1} = a^{n}\) must also be in \(H\text{.}\) Since either \(n\) or \(-n\) is positive, we can assume that \(H\) contains positive powers of \(a\) and \(n \gt 0\text{.}\) Let \(m\) be the smallest natural number such that \(a^m \in H\text{.}\) Such an \(m\) exists by the Principle of Well-Ordering.
We claim that \(h = a^m\) is a generator for \(H\text{.}\) We must show that every \(h' \in H\) can be written as a power of \(h\text{.}\) Since \(h' \in H\) and \(H\) is a subgroup of \(G\text{,}\) \(h' = a^k\) for some integer \(k\text{.}\) Using the division algorithm, we can find numbers \(q\) and \(r\) such that \(k = mq +r\) where \(0 \leq r \lt m\text{;}\) hence,
\begin{equation*}
a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r\text{.}
\end{equation*}
So \(a^r = a^k h^{-q}\text{.}\) Since \(a^k\) and \(h^{-q}\) are in \(H\text{,}\) \(a^r\) must also be in \(H\text{.}\) However, \(m\) was the smallest positive number such that \(a^m\) was in \(H\text{;}\) consequently, \(r=0\) and so \(k=mq\text{.}\) Therefore,
\begin{equation*}
h' = a^k = a^{mq} = h^q
\end{equation*}
and \(H\) is generated by \(h\text{.}\)
Corollary 2.2.2.
View Source for corollary
<corollary>
<statement>
<p>
The subgroups of <m>{\mathbb Z}</m> are exactly
<m>n{\mathbb Z}</m> for <m>n = 0, 1, 2,\ldots</m>.
</p>
</statement>
</corollary>
The subgroups of \({\mathbb Z}\) are exactly \(n{\mathbb Z}\) for \(n = 0, 1, 2,\ldots\text{.}\)
Proposition 2.2.3.
View Source for proposition
<proposition xml:id="proposition-cyclic-subgrp-order">
<statement>
<p>
Let <m>G</m> be a cyclic group of order <m>n</m> and suppose that <m>a</m> is a generator for <m>G</m>.
Then <m>a^k=e</m> if and only if <m>n</m> divides <m>k</m>.
</p>
</statement>
<proof>
<p>
First suppose that <m>a^k=e</m>.
By the division algorithm,
<m>k = nq + r</m> where <m>0 \leq r \lt n</m>; hence,
<me>
e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r
</me>.
Since the smallest positive integer <m>m</m> such that <m>a^m = e</m> is <m>n</m>,
<m>r= 0</m>.
</p>
<p>
Conversely, if <m>n</m> divides <m>k</m>,
then <m>k=ns</m> for some integer <m>s</m>.
Consequently,
<me>
a^k = a^{ns} = (a^n)^s = e^s = e
</me>.
</p>
</proof>
</proposition>
Let \(G\) be a cyclic group of order \(n\) and suppose that \(a\) is a generator for \(G\text{.}\) Then \(a^k=e\) if and only if \(n\) divides \(k\text{.}\)
Proof.
View Source for proof
<proof>
<p>
First suppose that <m>a^k=e</m>.
By the division algorithm,
<m>k = nq + r</m> where <m>0 \leq r \lt n</m>; hence,
<me>
e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r
</me>.
Since the smallest positive integer <m>m</m> such that <m>a^m = e</m> is <m>n</m>,
<m>r= 0</m>.
</p>
<p>
Conversely, if <m>n</m> divides <m>k</m>,
then <m>k=ns</m> for some integer <m>s</m>.
Consequently,
<me>
a^k = a^{ns} = (a^n)^s = e^s = e
</me>.
</p>
</proof>
First suppose that \(a^k=e\text{.}\) By the division algorithm, \(k = nq + r\) where \(0 \leq r \lt n\text{;}\) hence,
\begin{equation*}
e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r\text{.}
\end{equation*}
Since the smallest positive integer \(m\) such that \(a^m = e\) is \(n\text{,}\) \(r= 0\text{.}\)
Conversely, if \(n\) divides \(k\text{,}\) then \(k=ns\) for some integer \(s\text{.}\) Consequently,
\begin{equation*}
a^k = a^{ns} = (a^n)^s = e^s = e\text{.}
\end{equation*}
Theorem 2.2.4.
View Source for theorem
<theorem xml:id="theorem-cyclic-orders">
<statement>
<p>
Let <m>G</m> be a cyclic group of order <m>n</m> and suppose that <m>a \in G</m> is a generator of the group.
If <m>b = a^k</m>, then the order of <m>b</m> is <m>n/d</m>,
where <m>d = \gcd(k,n)</m>.
</p>
</statement>
<proof>
<p>
We wish to find the smallest integer <m>m</m> such that <m>e = b^m = a^{km}</m>.
By <xref ref="proposition-cyclic-subgrp-order" />,
this is the smallest integer <m>m</m> such that <m>n</m> divides <m>km</m> or,
equivalently,
<m>n/d</m> divides <m>m(k/d)</m>.
Since <m>d</m> is the greatest common divisor of <m>n</m> and <m>k</m>,
<m>n/d</m> and <m>k/d</m> are relatively prime.
Hence, for <m>n/d</m> to divide <m>m(k/d)</m> it must divide <m>m</m>.
The smallest such <m>m</m> is <m>n/d</m>.
</p>
</proof>
</theorem>
Let \(G\) be a cyclic group of order \(n\) and suppose that \(a \in G\) is a generator of the group. If \(b = a^k\text{,}\) then the order of \(b\) is \(n/d\text{,}\) where \(d = \gcd(k,n)\text{.}\)
Proof.
View Source for proof
<proof>
<p>
We wish to find the smallest integer <m>m</m> such that <m>e = b^m = a^{km}</m>.
By <xref ref="proposition-cyclic-subgrp-order" />,
this is the smallest integer <m>m</m> such that <m>n</m> divides <m>km</m> or,
equivalently,
<m>n/d</m> divides <m>m(k/d)</m>.
Since <m>d</m> is the greatest common divisor of <m>n</m> and <m>k</m>,
<m>n/d</m> and <m>k/d</m> are relatively prime.
Hence, for <m>n/d</m> to divide <m>m(k/d)</m> it must divide <m>m</m>.
The smallest such <m>m</m> is <m>n/d</m>.
</p>
</proof>
We wish to find the smallest integer \(m\) such that \(e = b^m = a^{km}\text{.}\) By Proposition 2.2.3, this is the smallest integer \(m\) such that \(n\) divides \(km\) or, equivalently, \(n/d\) divides \(m(k/d)\text{.}\) Since \(d\) is the greatest common divisor of \(n\) and \(k\text{,}\) \(n/d\) and \(k/d\) are relatively prime. Hence, for \(n/d\) to divide \(m(k/d)\) it must divide \(m\text{.}\) The smallest such \(m\) is \(n/d\text{.}\)
Corollary 2.2.5.
View Source for corollary
<corollary xml:id="corollary-cyclic-modngenerators">
<statement>
<p>
The generators of <m>{\mathbb Z}_n</m> are the integers <m>r</m> such that
<m>1 \leq r \lt n</m> and <m>\gcd(r,n) = 1</m>.
</p>
</statement>
</corollary>
The generators of \({\mathbb Z}_n\) are the integers \(r\) such that \(1 \leq r \lt n\) and \(\gcd(r,n) = 1\text{.}\)
Example 2.2.6. A Finite Cyclic Group of Order \(16\).
View Source for example
<example xml:id="example-cyclic-z16">
<title>A Finite Cyclic Group of Order <m>16</m></title>
<p>
Let us examine the group <m>{\mathbb Z}_{16}</m>.
The numbers 1, 3, 5, 7, 9, 11, 13,
and 15 are the elements of
<m>{\mathbb Z}_{16}</m> that are relatively prime to 16.
Each of these elements generates <m>{\mathbb Z}_{16}</m>.
For example,
<md>
<mrow>1 \cdot 9 & = 9 & 2 \cdot 9 & = 2 & 3 \cdot 9 & = 11</mrow>
<mrow>4 \cdot 9 & = 4 & 5 \cdot 9 & = 13 & 6 \cdot 9 & = 6</mrow>
<mrow>7 \cdot 9 & = 15 & 8 \cdot 9 & = 8 & 9 \cdot 9 & = 1</mrow>
<mrow>10 \cdot 9 & = 10 & 11 \cdot 9 & = 3 & 12 \cdot 9 & = 12</mrow>
<mrow>13 \cdot 9 & = 5 & 14 \cdot 9 & = 14 & 15 \cdot 9 & = 7</mrow>
</md>.
</p>
</example>
Let us examine the group \({\mathbb Z}_{16}\text{.}\) The numbers 1, 3, 5, 7, 9, 11, 13, and 15 are the elements of \({\mathbb Z}_{16}\) that are relatively prime to 16. Each of these elements generates \({\mathbb Z}_{16}\text{.}\) For example,
\begin{align*}
1 \cdot 9 & = 9 & 2 \cdot 9 & = 2 & 3 \cdot 9 & = 11\\
4 \cdot 9 & = 4 & 5 \cdot 9 & = 13 & 6 \cdot 9 & = 6\\
7 \cdot 9 & = 15 & 8 \cdot 9 & = 8 & 9 \cdot 9 & = 1\\
10 \cdot 9 & = 10 & 11 \cdot 9 & = 3 & 12 \cdot 9 & = 12\\
13 \cdot 9 & = 5 & 14 \cdot 9 & = 14 & 15 \cdot 9 & = 7\text{.}
\end{align*}
