Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 15.1 Cyclic Groups

Groups are classified according to their size and structure. A group’s structure is revealed by a study of its subgroups and other properties (e.g., whether it is abelian) that might give an overview of it. Cyclic groups have the simplest structure of all groups.

Definition 15.1.1. Cyclic Group.

Group \(G\) is cyclic if there exists \(a \in G\) such that the cyclic subgroup generated by \(a\text{,}\) \(\langle a \rangle\text{,}\) equals all of \(G\text{.}\) That is, \(G = \{n a |n \in \mathbb{Z}\}\text{,}\) in which case \(a\) is called a generator of \(G\text{.}\) The reader should note that additive notation is used for \(G\text{.}\)
\(\mathbb{Z}_{12} = [\mathbb{Z}_{12}; +_{12} ]\text{,}\) where \(+_{12}\) is addition modulo 12, is a cyclic group. To verify this statement, all we need to do is demonstrate that some element of \(\mathbb{Z}_{12}\) is a generator. One such element is 5; that is, \(\langle 5 \rangle = \mathbb{Z}_{12}\text{.}\) One more obvious generator is 1. In fact, 1 is a generator of every \([\mathbb{Z}_n; +_n]\text{.}\) The reader is asked to prove that if an element is a generator, then its inverse is also a generator. Thus, \(-5 = 7\) and \(-1 = 11\) are the other generators of \(\mathbb{Z}_{12}\text{.}\) The remaining eight elements of the group are not generators.
Examples of “string art”
Figure 15.1.3. Examples of “string art”
Figure 15.1.3(a) is an example of “string art” that illustrates how 5 generates \(\mathbb{Z}_{12}\text{.}\) Twelve tacks are placed evenly around a circle and numbered 0 through 11. A string is tied to tack 0, and is then looped around every fifth tack. As a result, the numbers of the tacks that are reached are exactly the ordered multiples of 5 modulo 12: 5, 10, 3, ... , 7, 0. Note that if every seventh tack were used, the same artwork would be produced. If every third tack were connected, as in Figure 15.1.3(b), the resulting loop would only use four tacks; thus 3 does not generate \(\mathbb{Z}_{12}\text{.}\)
The additive group of integers, \([\mathbb{Z}; +]\text{,}\) is cyclic:
\begin{equation*} \mathbb{Z} = \langle 1 \rangle = \{n\cdot 1 |n \in \mathbb{Z}\} \end{equation*}
This observation does not mean that every integer is the product of an integer times 1. It means that
\begin{equation*} \mathbb{Z} = \{0\} \cup \{\overbrace{1+1+\cdots +1}^{n \textrm{ terms}} \mid n \in \mathbb{P} \} \cup \{\overbrace{(-1)+(-1)+\cdots +(-1)}^{n \textrm{ terms}} \mid n \in \mathbb{P}\} \end{equation*}
Let \(a\) be any generator of \(G\) and let \(b, c \in G\text{.}\) By the definition of the generator of a group, there exist integers \(m\) and \(n\) such that \(b = m a\) and \(c = n a\text{.}\) Thus, using Theorem 11.3.14,
\begin{equation*} \begin{split} b*c &= (m a)*(n a)\\ &= (m + n)a \\ &= (n + m)a \\ &= (n a)*(m a)\\ &= c*b\\ \end{split} \end{equation*}
One of the first steps in proving a property of cyclic groups is to use the fact that there exists a generator. Then every element of the group can be expressed as some multiple of the generator. Take special note of how this is used in theorems of this section.
Up to now we have used only additive notation to discuss cyclic groups. Theorem 15.1.5 actually justifies this practice since it is customary to use additive notation when discussing abelian groups. Of course, some concrete groups for which we employ multiplicative notation are cyclic. If one of its elements, \(a\text{,}\) is a generator,
\begin{equation*} \langle a \rangle = \left\{a^n \mid n \in \mathbb{Z}\right\} \end{equation*}
The group of positive integers modulo 11 with modulo 11 multiplication, \([\mathbb{U}_{11} ;\times_{11}]\text{,}\) is cyclic. One of its generators is 6: \(6^1 = 6\text{,}\) \(6^2 = 3\text{,}\) \(6^3= 7\text{,}\)\(\ldots\) , \(6^9=2\text{,}\) and \(6^{10}=1\text{,}\) the identity of the group.
The real numbers with addition, \([\mathbb{R};+]\) is a noncyclic group. The proof of this statement requires a bit more generality since we are saying that for all \(r \in \mathbb{R}\text{,}\) \(\langle r \rangle\) is a proper subset of \(\mathbb{R}\text{.}\) If \(r\) is nonzero, the multiples of \(r\) are distributed over the real line, as in Figure 15.1.8. It is clear then that there are many real numbers, like \(r/2\text{,}\) that are not in \(\langle r \rangle\text{.}\)
Elements of the cylic subgroup generated by a real number
Figure 15.1.8. Elements of \(\langle r \rangle, r > 0\)
The next two proofs make use of the Theorem 11.4.1.
The following theorem shows that a cyclic group can never be very complicated.
Case 1: \(\lvert G\rvert < \infty\text{.}\) If \(a\) is a generator of \(G\) and \(\lvert G\rvert =n\text{,}\) define \(\phi:\mathbb{Z}_n \to G\) by \(\phi(k) = k a\) for all \(k \in \mathbb{Z}_n\text{.}\)
Since \(\langle a \rangle\) is finite, we can use the fact that the elements of \(\langle a \rangle\) are the first \(n\) nonnegative multiples of \(a\text{.}\) From this observation, we see that \(\phi\) is a surjection. A surjection between finite sets of the same cardinality must be a bijection. Finally, if \(p,q \in \mathbb{Z}_n\text{,}\)
\begin{equation*} \begin{split} \phi(p)+\phi(q) &= p a + q a\\ &= (p+q)a \\ &= (p +_n q)a \quad \textrm{ see exercise 10}\\ & = \phi(p +_n q)\\ \end{split} \end{equation*}
Therefore \(\phi\) is an isomorphism.
Case 2: \(\lvert G\rvert =\infty\text{.}\) We will leave this case as an exercise.
Let \(G\) be cyclic with generator \(a\) and let \(H \leq G\text{.}\) If \(H = \{e\}\text{,}\) \(H\) has \(e\) as a generator. We may now assume that \(\lvert H\rvert \geq 2\) and \(a \neq e\text{.}\) Let \(m\) be the least positive integer such that \(m a\) belongs to \(H\text{.}\) This is the key step. It lets us get our hands on a generator of \(H\text{.}\) We will now show that \(c= m a\) generates \(H\text{.}\) Certainly, \(\langle c \rangle \subseteq H\text{,}\) but suppose that \(\langle c \rangle \neq H\text{.}\) Then there exists \(b \in H\) such that \(b \notin \langle c \rangle\text{.}\) Now, since \(b\) is in \(G\text{,}\) there exists \(n \in \mathbb{Z}\) such that \(b = n a\text{.}\) We now apply the division property and divide \(n\) by \(m\text{.}\) \(b = n a = (q m+r)a = (q m)a+r a\text{,}\) where \(0 \leq r < m\text{.}\) We note that \(r\) cannot be zero for otherwise we would have \(b = n a = q(m a) = q c \in \langle c \rangle\text{.}\) Therefore, \(r a = n a - (q m) a \in H\text{.}\) This contradicts our choice of \(m\) because \(0 < r < m\text{.}\)
The only proper subgroups of \(\mathbb{Z}_{10}\) are \(H_1 = \{0, 5\}\) and \(H_2 = \{0, 2, 4, 6, 8\}\text{.}\) They are both cyclic: \(H_1= \langle 5 \rangle\text{,}\) while \(H_2 = \langle 2 \rangle = \langle 4 \rangle = \langle 6 \rangle = \langle 8 \rangle\text{.}\) The generators of \(\mathbb{Z}_{10}\) are 1, 3, 7, and 9.
With the exception of \(\{0\}\text{,}\) all subgroups of \(\mathbb{Z}\) are isomorphic to \(\mathbb{Z}\text{.}\) If \(H \leq \mathbb{Z}\text{,}\) then \(H\) is the cyclic subgroup generated by the least positive element of \(H\text{.}\) It is infinite and so by Theorem 15.1.10 it is isomorphic to \(\mathbb{Z}\text{.}\)
We now cite a useful theorem for computing the order of cyclic subgroups of a cyclic group:
The proof of this theorem is left to the reader.
To compute the order of \(\langle 18 \rangle\) in \(\mathbb{Z}_{30}\text{,}\) we first observe that 1 is a generator of \(\mathbb{Z}_{30}\) and \(18= 18(1)\text{.}\) The greatest common divisor of 18 and 30 is 6. Hence, the order of \(\langle 18 \rangle\) is 30/6, or 5.
At this point, we will introduce the idea of a fast adder, a relatively modern application (Winograd, 1965) of an ancient theorem, Sun Tzu’s Theorem. We will present only an overview of the theory and rely primarily on examples.
Out of necessity, integer addition with a computer is addition modulo \(n\text{,}\) for \(n\) some larger number. Consider the case where \(n\) is small, like 64. Then addition involves the addition of six-digit binary numbers. Consider the process of adding 31 and 1. Assume the computer’s adder takes as input two bit strings \(a = \left\{a_0,a_1,a_2,a_3,a_4,a_5\right\}\) and \(b=\left\{b_0,b_1,b_2,b_3,b_4,b_5\right\}\) and outputs \(s = \left\{s_0,s_1,s_2,s_3,s_4,s_5\right\}\text{,}\) the sum of \(a\) and \(b\text{.}\) Then, if \(a = 31 = (1, 1, 1, 1, 1, 0)\) and \(b = 1 = (1, 0, 0, 0, 0, 0)\text{,}\) \(s\) will be (0, 0, 0, 0, 0, 1), or 32. The output \(s_{ }=1\) cannot be determined until all other outputs have been determined. If addition is done with a finite-state machine, as in Example 14.3.9, the time required to get \(s\) will be six time units, where one time unit is the time it takes to get one output from the machine. In general, the time required to obtain \(s\) will be proportional to the number of bits. Theoretically, this time can be decreased, but the explanation would require a long digression and our relative results would not change that much. We will use the rule that the number of time units needed to perform addition modulo \(n\) is proportional to \(\left\lceil \log_2n\right\rceil\text{.}\)
Now we will introduce a hypothetical problem that we will use to illustrate the idea of a fast adder. Suppose that we had to add 1,000 numbers modulo \(27720 = 8 \cdot 9 \cdot 5 \cdot 7\cdot 11\text{.}\) By the rule above, since \(2^{14} < 27720 < 2^{15}\text{,}\) each addition would take 15 time units. If the sum is initialized to zero, 1,000 additions would be needed; thus, 15,000 time units would be needed to do the additions. We can improve this time dramatically by applying Sun Tzu’s Theorem. Recall that \(k\%n\) is the remainder upon division of \(k\) by \(n\text{.}\)
Sun Tzu’s Theorem can be stated in several different forms, and its proof can be found in many abstract algebra texts. Older texts most likely will refer to the theorem as the Chinese Remainder Theorem.
As we saw in Chapter 11, \(\mathbb{Z}_6\) is isomorphic to \(\mathbb{Z}_2 \times \mathbb{Z}_3\) . This is the smallest case to which Sun Tzu’s Theorem can be applied. An isomorphism between \(\mathbb{Z}_6\) and \(\mathbb{Z}_2 \times \mathbb{Z}_3\) is
\begin{equation*} \begin{array}{cc} \theta(0) = (0,0) & \theta(3) = (1,0)\\ \theta(1) = (1, 1) & \theta(4) = (0, 1)\\ \theta(2) = (0, 2) & \theta(5) = (1,2)\\ \end{array} \end{equation*}
Let’s consider a somewhat larger case. We start by selecting a modulus that can be factored into a product of relatively prime integers: \(n=21,600=2^5 3^3 5^2\text{.}\) In this case the factors are \(2^5=32\text{,}\) \(3^3=27\text{,}\) and \(5^2=25\text{.}\) They need not be powers of primes, but it is easy to break the factors into this form to assure relatively prime numbers. To add in \(\mathbb{Z}_n\text{,}\) we need \(\left\lceil \log _2n\right\rceil =15\) time units. Let \(G=\mathbb{Z}_{32}\times \mathbb{Z}_{27}\times \mathbb{Z}_{25}\text{.}\) Sun Tzu’s Theorem gives us an isomorphism between \(\mathbb{Z}_{21600}\) and \(G\text{.}\) The basic idea behind the fast adder, illustrated in Figure 15.1.16, is to make use of this isomorphism. The notation x += a is interpreted as the instruction to add the value of a to the variable x.
Fast Adder Scheme
Figure 15.1.16. Fast Adder Scheme
Assume we have several integers \(a_1, \ldots , a_m\) to be added. Here, we assume \(m= 20\text{.}\) We compute the sum s to compare our result with this true sum.
Although our sum is an integer calculation, we will put our calculation in the context of the integers modulo 21600. The isomophism from \(\mathbb{Z}_{21600}\) into \(G=\mathbb{Z}_{32}\times \mathbb{Z}_{27}\times \mathbb{Z}_{25}\) is defined in Sage as theta. In addition we demonstrate that the operations in these groups are preserved by theta.
We initialize the sums in each factor of the range of theta to zero and decompose each summand \(t\) into a triple \(\theta(t)=\left(t_1,t_2,t_3\right)\in G\text{.}\)
Addition in \(G\) can be done in parallel so that each new subtotal in the form of the triple \((s_1,s_2, s_3)\) takes only as long to compute as it takes to add in the largest modulus, \(\log _232=5\) time units, if calculations are done in parallel. By the time rule that we have established, the addition of 20 numbers can be done in \(20\cdot 5= 100\) time units, as opposed to \(20\cdot 15 =300\) time units if we do the calculations in \(\mathbb{Z}_{21600}\text{.}\) However the result is a triple in \(G\text{.}\) The function that performs the inverse of theta is built into most mathematics programs, including Sage. In Sage the function is crt, short for Chinese Remainder Theorem, the other common name of Sun Tzu’s Theorem. We use this function to compute the inverse of our triple, which is an element of \(\mathbb{Z}_{21600}\text{.}\) The result isn’t the true sum because the modulus 21600 is not large enough. However, we verify that our result is congruent to the true sum modulo 21600.
In order to get the true sum from our scheme, the modulus would need to be increased by moving from 21600 to, for example, \(21600*23=496800\text{.}\) Mapping into the new group, \(G=\mathbb{Z}_{32}\times \mathbb{Z}_{27}\times \mathbb{Z}_{25}\times \mathbb{Z}_{23}\) will take slightly longer, as will the inversion process with crt, but adding the summands that are in the form of quadruples can be done with no additional time.
The computation of \(\theta^{-1}\left(s_1,s_2,s_3\right)\) that is done by the Sage function crt can be accomplished in a variety of ways. All of them ultimately are simplified by the fact that \(\theta^{-1}\) is also an isomorphism. One approach is to use the isomorphism property to realize that the value of \(\theta^{-1}\left(s_1,s_2,s_3\right)\) is \(s_1\theta^{-1}(1,0,0)+s_2\theta^{-1}(0,1,0)+s_3\theta^{-1}(0,0,1)\text{.}\) The arithmetic in this expression is in the domain of \(\theta\) and is more time consuming, but it need only be done once. This is why the fast adder is only practical in situations where many additions must be performed to get a single sum.
The inverse images of the “unit vectors” can be computed ahead of time.
The result we computed earlier can be computed directly by in the larger modulus.
To further illustrate the potential of fast adders, consider increasing the modulus to \(n=2^53^35^27^211\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31\cdot 37\cdot 41\cdot 43\cdot 47\approx 3.1\times 10^{21}\text{.}\) Each addition using the usual modulo \(n\) addition with full adders would take 72 time units. By decomposing each summand into 15-tuples according to Sun Tzu’s Theorem, the time is reduced to \(\left\lceil \log _249\right\rceil =6\) time units per addition.

Exercises Exercises

1.

What generators besides 1 does \([\mathbb{Z}; +]\) have?
Answer.
The only other generator is \(-1\text{.}\)

2.

Suppose \([G;*]\) is a cyclic group with generator \(g\text{.}\) If you build a graph of with vertices from the elements of \(G\) and edge set \(E= \{(a, g*a) \mid a\in G\}\text{,}\) what would the graph look like? If \(G\) is a group of even order, what would a graph with edge set \(E'= \{(a, g^2*a) \mid a\in G\}\) look like?

3.

Prove that if \(\lvert G \rvert >2\) and \(G\) is cyclic, \(G\) has at least two generators.
Answer.
If \(\lvert G \rvert = m\text{,}\) \(m>2\text{,}\) and \(G = \langle a \rangle\text{,}\) then \(a\text{,}\) \(a^2,\ldots\text{,}\) \(a^{m-1}\) , \(a^m=e\) are distinct elements of \(G\text{.}\) Furthermore, \(a^{-1}= a^{m-1}\neq a\text{,}\) If \(1 \leq k \leq m\text{,}\) \(a^{-1}\) generates \(a^k\text{:}\)
\begin{equation*} \begin{split} \left(a^{-1}\right)^{m-k} &= \left(a^{m-1}\right)^{m-k}\\ & = a^{m^2-m-m k + k}\\ & =\left(a^m\right)^{m-k-1}*a^k\\ &= e*a^k=a^k\\ \end{split} \end{equation*}
Similarly, if \(G\) is infinite and \(G = \langle a\rangle\text{,}\) then \(a^{-1}\) generates \(G\text{.}\)

4.

If you wanted to list the generators of \(\mathbb{Z}_n\) you would only have to test the first \(n/2\) positive integers. Why?

5.

Which of the following groups are cyclic? Explain.
  1. \(\displaystyle [\mathbb{Q}; +]\)
  2. \(\displaystyle [\mathbb{R}^+;\cdot ]\)
  3. \([6\mathbb{Z}; +]\) where \(6\mathbb{Z} = \{6n |n \in \mathbb{Z}\}\)
  4. \(\displaystyle \mathbb{Z} \times \mathbb{Z}\)
  5. \(\displaystyle \mathbb{Z}_2\times \mathbb{Z}_3 \times \mathbb{Z}_{25}\)
Answer.
  1. No. Assume that \(q \in \mathbb{Q}\) generates \(\mathbb{Q}\text{.}\) Then \(\langle q\rangle = \{n q : n \in \mathbb{Z}\}\text{.}\) But this gives us at most integer multiples of \(q\text{,}\) not every element in \(\mathbb{Q}\text{.}\)
  2. No. Similar reasoning to part a.
  3. Yes. 6 is a generator of \(6\mathbb{Z}\text{.}\)
  4. No.
  5. Yes, \((1,1, 1)\) is a generator of the group.

6.

For each group and element, determine the order of the cyclic subgroup generated by the element:
  1. \(\mathbb{Z}_{25}\) , 15
  2. \(\mathbb{Z}_4\times \mathbb{Z}_9\) , \((2, 6)\) (apply Exercise 8)
  3. \(\mathbb{Z}_{64}\) , 2

7.

How can Theorem 15.1.13 be applied to list the generators of \(\mathbb{Z}_n\text{?}\) What are the generators of \(\mathbb{Z}_{25}\text{?}\) Of \(\mathbb{Z}_{256}\text{?}\)
Answer.
Theorem 15.1.13 implies that \(a\) generates \(\mathbb{Z}_n\) if and only if the greatest common divisor of \(n\) and \(a\) is 1. Therefore the list of generators of \(\mathbb{Z}_n\) are the integers in \(\mathbb{Z}_n\) that are relatively prime to \(n\text{.}\) The generators of \(\mathbb{Z}_{25}\) are all of the nonzero elements except 5, 10, 15, and 20. The generators of \(\mathbb{Z}_{256}\) are the odd integers in \(\mathbb{Z}_{256}\) since 256 is \(2^8\text{.}\)

8.

Prove that if the greatest common divisor of \(n\) and \(m\) is 1, then (1, 1) is a generator of \(\mathbb{Z}_n\times \mathbb{Z}_m\text{,}\) and hence, \(\mathbb{Z}_n\times \mathbb{Z}_m\) is isomorphic to \(\mathbb{Z}_{n m}\text{.}\)

9.

  1. Illustrate how the fast adder can be used to add the numbers 21, 5, 7, and 15 using the isomorphism between \(\mathbb{Z}_{77}\) and \(\mathbb{Z}_7\times \mathbb{Z}_{11}\text{.}\)
  2. If the same isomorphism is used to add the numbers 25, 26, and 40, what would the result be, why would it be incorrect, and how would the answer differ from the answer in part a?
Answer.
  1. \(\theta :\mathbb{Z}_{77} \to \mathbb{Z}_7 \times \mathbb{Z}_{11}\) maps the given integers as follows:
    \begin{equation*} \begin{array}{ccc} 21 & \to & (0,10) \\ 5 & \to & (5,5) \\ 7 & \to & (0,7) \\ 15 & \to & \underline{(1,4)} \\ \textrm{ sum}=48 & \leftarrow & (6,4)=\textrm{ sum} \\ \end{array} \end{equation*}
    The final sum, 48, is obtained by using the facts that \(\theta ^{-1}(1,0) =22\) and \(\theta ^{-1}(0,1)=56\)
    \begin{equation*} \begin{split} \theta^{-1}(6,4)= 6 \times_{77}\theta ^{-1}(1,0) + 4 \times_{77}\theta^{-1}(0,1)\\ & =6\times_{77}22 +_{77} 4\times_{77} 56\\ & =55 +_{77}70\\ & =48\\ \end{split}\text{.} \end{equation*}
  2. Using the same isomorphism:
    \begin{equation*} \begin{array}{ccc} 25 & \to & (4,3) \\ 26 & \to & (5,4) \\ 40 & \to & (5,7) \\ & & \textrm{ sum}=(0,3) \\ \end{array} \end{equation*}
    \begin{equation*} \begin{split} theta ^{-1}(0,3) &= 3 \times_{77}\theta ^{-1}(0,1)\\ & = 3\times_{77} 56\\ & =14\\ \end{split}\text{.} \end{equation*}
    The actual sum is 91. Our result is incorrect, since 91 is not in \(\mathbb{Z}_{77}\text{.}\) Notice that 91 and 14 differ by 77. Any error that we get using this technique will be a multiple of 77.

10.

Prove that if \(G\) is a cyclic group of order \(n\) with generator \(a\text{,}\) and \(p, q \in \{0, 1, \ldots , n - 1\}\text{,}\) then \((p+q)a = \left(p+_nq\right)a\text{.}\)
<Prev^TopNext>