﻿ ﻿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 : 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,a2,...,an 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) = ai

is a one-to-one correspondence from n 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 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⟩ = {. . .,a2,a1, e,a,a2,...}

There is obviously a one-to-one correspondence between this group and : In other words, the function

f(i) = ai

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 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 , ⟨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 S3, ⟨β⟩ = {ε, β, δ}, 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 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 (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 16.

2 List the elements of ⟨f⟩ in S6, where 3 Describe the cyclic subgroup in *. Describe the cyclic group in .

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 ( ).

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 > k2 > k3> ⋯ If k > 1, then k < k2 < k3 < ⋯ 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.)

﻿