Skip to main content

Section 4.2 Subgroups of a Cyclic Group

View Source for section
<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, <md>a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r</md>. 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, <md>h' = a^k = a^{mq} =  h^q</md>
            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, <md>e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r</md>. 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, <md>a^k = a^{ns} = (a^n)^s = e^s = e</md>.</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  &amp; =  9  &amp;  2 \cdot 9  &amp; = 2  &amp; 3 \cdot 9  &amp; = 11</mrow>
            <mrow>4 \cdot 9  &amp; =  4  &amp;  5 \cdot 9  &amp; = 13 &amp;     6 \cdot 9 &amp; = 6</mrow>
            <mrow>7 \cdot 9  &amp; =  15 &amp; 8 \cdot 9  &amp; = 8  &amp;  9 \cdot 9 &amp;  = 1</mrow>
            <mrow>10 \cdot 9 &amp; =  10 &amp; 11 \cdot 9 &amp; = 3  &amp; 12 \cdot 9 &amp;  = 12</mrow>
            <mrow>13 \cdot 9 &amp; =  5 &amp; 14 \cdot 9 &amp; = 14 &amp;   15 \cdot 9 &amp; = 7</mrow>
        </md>.</p>
    </example>
</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?

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, <md>a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r</md>. 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, <md>h' = a^k = a^{mq} =  h^q</md>
    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{.}\)

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, <md>e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r</md>. 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, <md>a^k = a^{ns} = (a^n)^s = e^s = e</md>.</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*}

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 4.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{.}\)

Example 4.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  &amp; =  9  &amp;  2 \cdot 9  &amp; = 2  &amp; 3 \cdot 9  &amp; = 11</mrow>
        <mrow>4 \cdot 9  &amp; =  4  &amp;  5 \cdot 9  &amp; = 13 &amp;     6 \cdot 9 &amp; = 6</mrow>
        <mrow>7 \cdot 9  &amp; =  15 &amp; 8 \cdot 9  &amp; = 8  &amp;  9 \cdot 9 &amp;  = 1</mrow>
        <mrow>10 \cdot 9 &amp; =  10 &amp; 11 \cdot 9 &amp; = 3  &amp; 12 \cdot 9 &amp;  = 12</mrow>
        <mrow>13 \cdot 9 &amp; =  5 &amp; 14 \cdot 9 &amp; = 14 &amp;   15 \cdot 9 &amp; = 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*}
You have attempted of activities on this page.
PrevTopNext