## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 11. CYCLIC GROUPS

If *G* is a group and *a* ∈ *G*, it may happen that *every* element of *G* is a power of *a*. In other words, *G* may consist of all the powers of *a*, and nothing else:

*G* = {*a ^{n}* :

*n*∈ }

In that case, *G* is called a *cyclic group*, and *a* is called its *generator*. We write

*G* = ⟨*a*⟩

and say that *G* is the cyclic group generated by *a*.

If *G* = ⟨*a*⟩ is the cyclic group generated by *a*, and *a* has order *n*, we say that *G* is a *cyclic group of order n*. We will see in a moment that, in that case, *G* has exactly *n* elements. If the generator of *G* has order infinity, we say that *G* is a *cyclic group of order infinity*. In that case, we will see that *G* has infinitely many elements.

The simplest example of a cyclic group is , which consists of all the multiples of 1. (Remember that in additive notation we speak of “multiples” instead of “powers.”) is a cyclic group of order infinity; its generator is 1. Another example of a cyclic group is _{6}, which consists of all the multiples of 1, added modulo 6. _{6} is a cyclic group of order 6; 1 is a generator of _{6}, but _{6} has another generator too. What is it?

Suppose ⟨*a*⟩ is a cyclic group whose generator *a* has order *n*. Since ⟨*a*⟩ is the set of all the powers of *a*, it follows from __Theorem 3__ of __Chapter 10__ that

⟨*a*⟩ = {*e,a,a*^{2},...,*a ^{n}*

^{ }

^{−}

^{1}}

If we compare this group with * _{n}*, we notice a remarkable resemblance! For one thing, they are obviously in one-to-one correspondence:

In other words, the function

*f*(*i*) = *a ^{i}*

is a one-to-one correspondence from * _{n}* to ⟨

*a*⟩. But this function has an additional property, namely,

*f*(*i* + *j*) = *a ^{i}*

^{ + j}=

*a*=

^{i}a^{j}*f*(

*i*)

*f*(

*j*)

Thus, *f* is an *isomorphism* from * _{n}* to ⟨

*a*⟩. In conclusion,

* _{n}* ≅ ⟨

*a*⟩

Let us review the situation in the case where *a* has *order infinity*. In this case, by __Theorem 4__ of __Chapter 10__,

⟨*a*⟩ = {. . .,*a*^{−}^{2},*a*^{−}^{1}, *e*,*a*,*a*^{2},...}

There is obviously a one-to-one correspondence between this group and :

In other words, the function

*f*(*i*) = *a ^{i}*

is a one-to-one correspondence from to ⟨*a*⟩. As before, *f* is an isomorphism, and therefore

≅ ⟨*a*⟩

What we have just proved is a very important fact about cyclic groups; let us state it as a theorem.

**Theorem 1: Isomorphism of cyclic groups**

(i)*For every positive integer n, every cyclic group of order n is isomorphic to* * _{n}*.

*Thus, any two cyclic groups of order n are isomorphic to each other*.

(ii)*Every cyclic group of order infinity is isomorphic to* , *and therefore any two cyclic groups of order infinity are isomorphic to each other*.

If *G* is any group and *a* ∈ *G*, it is easy to see that

1. The product of any two powers of *a* is a power of *a*; for *a ^{m}a^{n}* =

*a*

^{m}^{ + n}.

2. Furthermore, the inverse of any power of *a* is a power of *a*, because (*a ^{n}*)

^{−}

^{1}=

*a*

^{−}

*.*

^{n}3. It therefore follows that the set of all the powers of *a* is a subgroup of *G*.

This subgroup is called the *cyclic subgroup of G generated by a*. It is obviously a cyclic group, and therefore we denote it by ⟨*a*⟩. If the element *a* has order *n*, then, as we have seen, ⟨*a*⟩ contains the *n* elements {*e*, *a*, *a*^{2},. . ., *a ^{n}*

^{ }

^{−}

^{1}}. If

*a*has order infinity, then ⟨

*a*⟩ = {. . .,

*a*

^{−}

^{2},

*a*

^{−}

^{1},

*e*,

*a*,

*a*

^{2},...} and has infinitely many elements.

For example, in , ⟨2⟩ is the cyclic subgroup of which consists of all the multiples of 2. In _{15}, ⟨3⟩ is the cyclic subgroup {0,3,6,9,12} which contains all the multiples of 3. In *S*_{3}, ⟨*β*⟩ = {*ε, β, δ*}, and contains all the powers of *β*.

Can a cyclic group, such as , have a *subgroup which is not cyclic?* This question is of great importance in our understanding of cyclic groups. Its answer is not obvious, and certainly not self-evident:

**Theorem 2** *Every subgroup of a cyclic group is cyclic*.

Let *G* = ⟨*a*⟩ be a cyclic group, and let *H* be any subgroup of *G*. We wish to prove that *H* is cyclic.

Now, *G* has a generator *a*; and when we say that *H* is cyclic, what we mean is that *H* too has a generator (call it *b*), and *H* consists of all the powers of *b*. The gist of this proof, therefore, is to *find* a generator of *H*, and then check that every element of *H* is a power of this generator.

Here is the idea: *G* is the cyclic group generated by *a*, and *H* is a subgroup of *G*. Every element of *H* is therefore in *G*, which means that every element of *H* is some power of *a*. The generator of *H* which we are searching for is therefore one of the powers of *a*—one of the powers of *a* which happens to be in *H*; but which one? Obviously the lowest one! More accurately, the lowest *positive* power of *a* in *H*.

And now, carefully, here is the proof:

PROOF: Let *m* be the smallest positive integer such that *a ^{m}* ∈

*H*. We will show that every element of

*H*is a power of

*a*, hence

^{m}*a*is a generator of

^{m}*H*.

Let *a ^{t}* be

*any*element of

*H*. Divide

*t*by

*m*using the division algorithm:

*t* = *mq* + *r* 0 ≤ *r* < *m*

Then *a ^{t}* =

*a*

^{mq}^{ + r}=

*a*

^{mq}a^{r}Solving for *a ^{r}*,

*a*= (

^{r}*a*)

^{mq}^{−}

^{1}

*a*= (

^{t}*a*)

^{m}^{−}

^{q}*a*

^{t}But *a ^{m}* ∈

*H*and

*a*∈

^{t}*H*; thus (

*a*)

^{m}^{−}

*∈*

^{q}*H*.

It follows that *a ^{r}* ∈

*H*. But

*r*<

*m*and

*m*is the smallest positive iriteger such that

*a*∈

^{m}*H*. So

*r*= 0, and therefore

*t*=

*mq*.

We conclude that every element *a ^{t}* ∈

*H*is of the form

*a*= (

^{t}*a*)

^{m}*, that is, a power of*

^{q}*a*. Thus,

^{m}*H*is the cyclic group generated by

*a*. ■

^{m}This chapter ends with a final comment regarding the different uses of the word “order” in algebra.

Let *G* be a group; as we have seen, the *order of an element a* in *G* is the least positive integer *n* such that

(The order of *a* is *infinity* if there is no such *n*.)

Earlier, we defined the *order of the group G* to be the number of elements in *G*. Remember that the order of *G* is denoted by |*G*|.

These are two separate and distinct definitions, not to be confused with one another. Nevertheless, there is a connection between them: Let *a* be an element of order *n* in a group. By __Chapter 10__, __Theorem 3__, there are exactly *n*different powers of *a*, hence ⟨*a*⟩ has *n* elements. Thus,

If ord(*a*) = *n* then |⟨*a*⟩| = *n*

That is, the order of a cyclic group is the same as the order of its generator.

**EXERCISES**

**A. Examples of Cyclic Groups**

**1** List the elements of ⟨6⟩ in _{16}.

**2** List the elements of ⟨*f*⟩ in *S*_{6}, where

**3** Describe the cyclic subgroup in *. Describe the cyclic group in .

**4** If *f*(*x*) = *x* + 1, describe the cyclic subgroup ⟨*f*⟩ of *S*_{R}.

**5** If *f*(*x*) = *x* + 1, describe the cyclic subgroup ⟨*f*⟩ of ().

** 6** Show that −1, as well as 1, is a generator of . Are there any other generators of ? Explain! What are the generators of an arbitrary infinite cyclic group ⟨

*a*⟩?

**7** Is *** cyclic? Try to prove your answer. HINT: Suppose *k* is a generator of **:*

If *k* < 1, then *k* > *k*^{2} > *k*^{3}> ⋯

If *k* > 1, then *k* < *k*^{2} < *k*^{3} < ⋯

**B. Elementary Properties of Cyclic Groups**

Prove each of the following:

**# 1** If

*G*is a group of order

*n, G*is cyclic iff

*G*has an element of order

*n*.

**2** Every cyclic group is abelian.

**3** If *G* = ⟨*a*⟩ and *b* ∈ *G*, the order of *b* is a factor of the order of *a*.

**4** In any cyclic group of order *n*, there are elements of order *k* for every integer *k* which divides *n*.

**5** Let *G* be an abelian group of order *mn*, where *m* and *n* are relatively prime. If *G* has an element of order *m* and an element of order *n, G* is cyclic. (See __Chapter 10__, __Exercise E4__.)

**6** Let ⟨*a*⟩ be a cyclic group of order *n*. If *n* and *m* are relatively prime, then the function *f*(*x*) = *x ^{m}* is an automorphism of ⟨

*a*⟩. (HINT: Use

__Exercise B3__and

__Chapter 10__,

__Theorem 5__.)

**C. Generators of Cyclic Groups**

For any positive integer *n*, let *ϕ*(*n*) denote the number of positive integers less than *n* and relatively prime to *n*. For example, 1, 2, 4, 5, 7, and 8 are relatively prime to 9, so *ϕ*(9) = 6. Let *a* have order *n*, and prove the following:

**1** *a ^{r}* is a generator of ⟨

*a*⟩ iff

*r*and

*n*are relatively prime. (HINT: See

__Chapter 10__,

__Exercise G2__.)

**2** ⟨*a*⟩ has *ϕ*(*n*) different generators. (Use part 1 in your proof.)

**3** For any factor *m* of *n*, let *C _{m}* = {

*x*∈ ⟨

*a*⟩ :

*x*=

^{m}*e*).

*C*is a subgroup of ⟨

_{m}*a*⟨.

**# 4**

*C*has exactly

_{m}*m*elements. (HINT: Use

__Exercise B4__.)

**5** An element *x* in ⟨*a*⟩ has order *m* iff *x* is a generator of *C _{m}*.

**6** There are *ϕ*(*m*) elements of order *m* in ⟨*a*⟩. (Use parts 1 and 5.)

**# 7** Let

*n*=

*mk*.

*a*has order

^{r}*m*iff

*r*=

*kl*where

*l*and

*m*are relatively prime. (HINT: See

__Chapter 10__,

__Exercise G1__, 2.)

**8** If *c* is any generator of ⟨*a*⟩, then {*c ^{r}* :

*r*is relatively prime to

*n*} is the set of all the generators of ⟨

*a*⟩.

**D. Elementary Properties of Cyclic Subgroups of Groups**

Let *G* be a group and let *a, b* ∈ *G*. Prove the following:

**1** If *a* is a power of *b*, say *a* = *b ^{k}*, then ⟨

*a*⟩ ⊆ ⟨

*b*⟩.

**2** Suppose *a* is a power of *b*, say *a* = *b ^{k}*. Then

*b*is equal to a power of

*a*iff ⟨

*a*⟩ = ⟨

*b*⟩.

**3** Suppose *a* ∈ ⟨*b*⟩. Then ⟨*a*⟩ = ⟨*b*⟩ iff *a* and *b* have the same order.

**4** Let ord(*a*) = *n*, and *b* = *a ^{k}*. Then ⟨

*a*⟩ = ⟨

*b*⟩ iff

*n*and

*k*are relatively prime.

**5** Let ord(*a*) = *n*, and suppose *a* has a *k*th root, say *a* = *b ^{k}*. Then ⟨

*a*⟩ = ⟨

*b*⟩ iff

*k*and

*n*are relatively prime.

** 6** Any cyclic group of order

*mn*has a unique subgroup of order

*n*.

**E. Direct Products of Cyclic Groups**

Let *G* and *H* be groups, with *a* ∈ *G* and *b* ∈ *H*. Prove parts 1-4:

**1** If (*a*, *b*) is a generator of *G* × *H*, then *a* is a generator of *G* and *b* is a generator of *H*.

**2** If *G* × *H* is a cyclic group, then *G* and *H* are both cyclic.

**3** The converse of part 2 is false. (Give an example to demonstrate this.)

**4** Let ord(*a*) = *m* and ord(*b*) = *n*. The order of (*a, b*) in *G* × *H* is the least common multiple of *m* and *n*. (HINT: Use __Chapter 10__, __Theorem 5__. Nothing else is needed!)

**5** Conclude from part 4 that if *m* and *n* are relatively prime, then (*a, b*) has order *mn*.

**6** Suppose (*c*, *d*) ∈ *G* × *H*, where *c* has order *m* and *d* has order *n*. Prove: If *m* and *n* are *not* relatively prime (hence have a common factor *q* > 1), then the order of (*c*, *d*) is less than *mn*.

**7** Conclude from parts 5 and 6 that ⟨*a*⟩ × ⟨*b*⟩ is cyclic iff ord(*a*) and ord(*b*) are relatively prime.

**8** Let *G* be an abelian group of order *mn*, where *m* and *n* are relatively prime. Prove: If *G* has an element *a* of order *m* and an element *b* of order *n*, then *G* ≅ ⟨*a*⟩ × ⟨*b*⟩. (HINT: See __Chapter 10__, __Exercise E1__, 2.)

**9** Let ⟨*a*⟩ be a cyclic group of order *mn*, where *m* and *n* are relatively prime, and prove that ⟨*a*⟩ ≅ ⟨*a ^{m}*⟩ × ⟨

*a*⟩.

^{n}**† F. kth Roots of Elements in a Cyclic Group**

Let ⟨*a*⟩ be a cyclic group of order *n*. For any integer *k*, we may ask: which elements in ⟨*a*⟩ have a *k*th root? The exercises which follow will answer this question.

**1** Let *a* have order 10. For what integers *k* (0 ≤ *k* ≤ 12), does *a* have a *k*th root? For what integers *k* (0 ≤ *k* ≤ 12), does *a*^{6} have fcth root?

Let *k* and *n* be any integers, and let gcd(*k*, *n*) denote the greatest common divisor of *k* and *n*. A linear combination of *k* and *n* is any expression *ck* + *dn* where *c* and *d* are integers. It is a simple fact of number theory (the proof is given on page 219), that an integer *m* is equal to a linear combination of *k* and *n* iff *m* is a multiple of gcd(*k*, *n*). Use this fact to prove the following, where *a* is an element of order *n* in a group *G*.

**2** If *m* is a multiple of gcd(*k*, *n*), then *a ^{m}* has a

*k*th root in ⟨

*a*⟩. [HINT: Compute

*a*, and show that

^{m}*a*= (

^{m}*a*)

^{c}*for some*

^{k}*a*∈ ⟨

^{c}*a*⟩.]

**# 3** If

*a*has a

^{m}*k*th root in ⟨

*a*⟩, then

*m*is a multiple of gcd(

*k*,

*n*). Thus,

*a*has a

^{m}*k*th root in ⟨

*a*⟩ iff gcd(

*k*,

*n*) is a factor of

*m*.

**4** *a* has a *k*th root in ⟨*a*⟩ iff *k* and *n* are relatively prime.

**5** Let *p* be a prime number.

(*a*) If *n* is not a multiple of *p*, then every element in ⟨*a*⟩ has a *p*th root.

(*b*) If *n* is a multiple of *p*, and *a ^{m}* has a

*p*th root, then

*m*is a multiple of

*p*.

(Thus, the only elements in ⟨*a*⟩ which have *p*th roots are *e*, *a ^{p}*,

*a*

^{2p}, etc.)

**6** The set of all the elements in ⟨*a*⟩ having a *k*th root is a subgroup of ⟨*a*⟩. Explain why this subgroup is cyclic, say ⟨*a ^{m}*⟩. What is the value of

*m*? (Use part 3.)