CYCLIC GROUPS - A Book of Abstract Algebra

A Book of Abstract Algebra, Second Edition (1982)

Chapter 11. CYCLIC GROUPS

If G is a group and aG, 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 = {an : nimage}

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 image, which consists of all the multiples of 1. (Remember that in additive notation we speak of “multiples” instead of “powers.”) image is a cyclic group of order infinity; its generator is 1. Another example of a cyclic group is image6, which consists of all the multiples of 1, added modulo 6. image6 is a cyclic group of order 6; 1 is a generator of image6, but image6 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,a2,...,an 1}

If we compare this group with imagen, we notice a remarkable resemblance! For one thing, they are obviously in one-to-one correspondence:

image

In other words, the function

f(i) = ai

is a one-to-one correspondence from imagen to ⟨a⟩. But this function has an additional property, namely,

f(i + j) = ai + j = aiaj = f(i)f(j)

Thus, f is an isomorphism from imagen to ⟨a⟩. In conclusion,

imagen ≅ ⟨a

Let us review the situation in the case where a has order infinity. In this case, by Theorem 4 of Chapter 10,

a⟩ = {. . .,a2,a1, e,a,a2,...}

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

image

In other words, the function

f(i) = ai

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

image ≅ ⟨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 imagen. Thus, any two cyclic groups of order n are isomorphic to each other.

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

If G is any group and aG, it is easy to see that

1. The product of any two powers of a is a power of a; for aman = am + n.

2. Furthermore, the inverse of any power of a is a power of a, because (an)1 = an.

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, a2,. . ., an 1}. If a has order infinity, then ⟨a⟩ = {. . ., a2, a1, e, a, a2,...} and has infinitely many elements.

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

Can a cyclic group, such as image, 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.

image

And now, carefully, here is the proof:

PROOF: Let m be the smallest positive integer such that amH. We will show that every element of H is a power of am, hence am is a generator of H.

Let at be any element of H. Divide t by m using the division algorithm:

t = mq + r 0 ≤ r < m

Then at = amq + r = amq ar

Solving for ar, ar = (amq)1 at = (am)q at

But amH and atH; thus (am)qH.

It follows that arH. But r < m and m is the smallest positive iriteger such that amH. So r = 0, and therefore t = mq.

We conclude that every element atH is of the form at = (am)q, that is, a power of am. Thus, H is the cyclic group generated by am. ■

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

image

(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 ndifferent 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 image16.

2 List the elements of ⟨f⟩ in S6, where

image

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

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

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

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

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

If k < 1, then k > k2 > k3> ⋯ image

If k > 1, then k < k2 < k3 < ⋯ image

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 bG, 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) = xm 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 ar is a generator of ⟨a⟩ iff r and n are relatively prime. (HINT: See Chapter 10, Exercise G2.)

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

3 For any factor m of n, let Cm = {x ∈ ⟨a⟩ : xm = e). Cm is a subgroup of ⟨a⟨.

# 4 Cm has exactly m elements. (HINT: Use Exercise B4.)

5 An element x in ⟨a⟩ has order m iff x is a generator of Cm.

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

# 7 Let n = mk. ar has order 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 {cr : 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, bG. Prove the following:

1 If a is a power of b, say a = bk, then ⟨a⟩ ⊆ ⟨b⟩.

2 Suppose a is a power of b, say a = bk. 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 = ak. Then ⟨a⟩ = ⟨b⟩ iff n and k are relatively prime.

5 Let ord(a) = n, and suppose a has a kth root, say a = bk. 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 aG and bH. 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⟩ ≅ ⟨am⟩ × ⟨an⟩.

† 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 kth 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 kth root? For what integers k (0 ≤ k ≤ 12), does a6 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 am has a kth root in ⟨a⟩. [HINT: Compute am, and show that am = (ac)k for some ac ∈ ⟨a⟩.]

# 3 If am has a kth root in ⟨a⟩, then m is a multiple of gcd(k, n). Thus, am has a kth root in ⟨a⟩ iff gcd(k, n) is a factor of m.

4 a has a kth 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 pth root.

(b) If n is a multiple of p, and am has a pth root, then m is a multiple of p.

(Thus, the only elements in ⟨a⟩ which have pth roots are e, ap, a2p, etc.)

6 The set of all the elements in ⟨a⟩ having a kth root is a subgroup of ⟨a⟩. Explain why this subgroup is cyclic, say ⟨am⟩. What is the value of m? (Use part 3.)