Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section15.1Cyclic 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.

Definition15.1.1Cyclic Group

Group \(G\) is cyclic if there exists \(a \in G\) such that the cyclic subgroup generated by a, \(\langle a \rangle\), equals all of \(G\). That is, \(G = \{n a |n \in \mathbb{Z}\}\), in which case a is called a generator of \(G\). The reader should note that additive notation is used for \(G\).

Example15.1.2A Finite Cyclic Group

\(\mathbb{Z}_{12} = [\mathbb{Z}_{12} , +_{12} ]\), 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}\) . One more obvious generator is 1. In fact, 1 is a generator of every \([\mathbb{Z}_n; +_n]\). 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}\). The remaining eight elements of the group are not generators.

Examples of “string art”
Figure15.1.3Examples of “string art”

Figure 15.1.3(a) is an example of “string art” that illustrates how 5 generates \(\mathbb{Z}_{12}\). 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}\)

Example15.1.4The Group of Integers is Cyclic

The additive group of integers, \([\mathbb{Z}; +]\text{,}\) is cyclic: \[\mathbb{Z} = \langle 1 \rangle = \{n\cdot 1 |n \in \mathbb{Z}\}\] This observation does not mean that every integer is the product of an integer times 1. It means that \[\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}\}\]

Proof

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, \[\langle a \rangle = \left\{a^n \mid n \in \mathbb{Z}\right\}\]

Example15.1.6A Cyclic Multiplicative Group

The group of positive integers modulo 11 with modulo 11 multiplication, \([\mathbb{Z}_{11}^* ;\times_{11}]\), is cyclic. One of its generators is 6: \(6^1 = 6\), \(6^2 = 3\), \(6^3= 7\),\(\ldots\) , \(6^9=2\), and \(6^{10}=1\), the identity of the group.

Example15.1.7A Non-cyclic 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}\), \(\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\), that are not in \(\langle r \rangle\).

Elements of the cylic subgroup generated by a real number
Figure15.1.8Elements 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.

Proof
Proof
Example15.1.11All subgroups of \(\mathbb{Z}_{10}\)

The only proper subgroups of \(\mathbb{Z}_{10}\) are \(H_1 = \{0, 5\}\) and \(H_2 = \{0, 2, 4, 6, 8\}\). They are both cyclic: \(H_1= \langle 5 \rangle\), while \(H_2 = \langle 2 \rangle = \langle 4 \rangle = \langle 6 \rangle = \langle 8 \rangle\). The generators of \(\mathbb{Z}_{10}\) are 1, 3, 7, and 9.

Example15.1.12All subgroups of \(\mathbb{Z}\)

With the exception of \(\{0\}\), all subgroups of \(\mathbb{Z}\) are isomorphic to \(\mathbb{Z}\text{.}\) If \(H \leq \mathbb{Z}\), 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}\).

We now cite a useful theorem for computing the order of cyclic subgroups of a cyclic group:

Proof
Example15.1.14Computation of an order in a cyclic group

To compute the order of \(\langle 18 \rangle\) in \(\mathbb{Z}_{30}\), we first observe that 1 is a generator of \(\mathbb{Z}_{30}\) and \(18= 18(1)\). 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) to an ancient theorem, the Chinese Remainder Theorem. We will present only an overview of the theory and rely primarily on examples. The interested reader can refer to Dornhoff and Hohn for details.

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\}\), the sum of a and b. Then, if \(a = 31 = (1, 1, 1, 1, 1, 0)\) and \(b = 1 = (1, 0, 0, 0, 0, 0)\), \(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.5, 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\).

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 many numbers modulo \(27720 = 8\cdot 9 \cdot \text 5 \cdot \text 7\cdot \text 11\). By the rule above, since \(2^{14} < 27720 < 2^{15}\), 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 the Chinese Remainder Theorem.

The Chinese Remainder Theorem can be stated in several different forms, and its proof can be found in many abstract algebra texts.

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 the CRT 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} \text{.} \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\). In this case the factors are \(2^5=32\), \(3^3=27\), and \(5^2=25\). 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\), we need \(\left\lceil \log _2n\right\rceil =15\) time units. Let \(G=\mathbb{Z}_{32}\times \mathbb{Z}_{27}\times \mathbb{Z}_{25}\). The CRT gives us an isomorphism between \(\mathbb{Z}_{21600}\) and \(G\). The basic idea behind the fast adder, illustrated in Figure 15.1.16, is to make use of this isomorphism.

Fast Adder Scheme
Figure15.1.16Fast Adder Scheme

Assume we have several integers \(a_1, \ldots , a_m\) to be added. Here, we assume \(m= 20\). We compute the sum s to compare our result with this true sum.

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

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}\). However the result is a triple in \(G\). The built-in function that performs the inverse of theta is built into most mathematics programs, including Sage. In Sage the function is crt. We use this function to compute the inverse of our triple, which is an element of \(\mathbb{Z}_{21600}\). The result isn't the true sum because the 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\). 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)\). 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}\). 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 the CRT, the time is reduced to \(\left\lceil \log _249\right\rceil =6\) time units per addition.

Subsection15.1.1Exercises for Section 15.1

1

What generators besides 1 does \([\mathbb{Z}, +]\) have?

Answer
2

Without doing any multiplications, determine the number of generators of \([\mathbb{Z}_{11}, +_{11}]\).

3

Prove that if \(\lvert G \rvert >2\) and \(G\) is cyclic, \(G\) has at least two generators.

Answer
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. \([\mathbb{Q}, +]\)

  2. \([\mathbb{R}^+,\cdot ]\)

  3. \([6\mathbb{Z}, +]\) where \(6\mathbb{Z} = \{6n |n \in \mathbb{Z}\}\)

  4. \(\mathbb{Z} \times \mathbb{Z}\)

  5. \(\mathbb{Z}_2\times \mathbb{Z}_3 \times \mathbb{Z}_{25}\)

Answer
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\)? What are the generators of \(\mathbb{Z}_{25}\)? Of \(\mathbb{Z}_{256}\)?

Answer
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\), and, hence, \(\mathbb{Z}_n\times \mathbb{Z}_m\) is isomorphic to \(\mathbb{Z}_{n m}\).

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

  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
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\}\), then \((p+q)a = \left(p+_nq\right)a\)