Subgroups of finite cyclic groups

On example sheet 2 there was a question about finding subgroups of small cyclic groups, and a followup question about predicting the number of subgroups in some rather larger cyclic groups. After the first of these questions, you probably noted that in all the cases considered, all subgroups were cyclic and that there was one of each possible order, and these orders were the factors of that of the original group. Assuming this is true in general, then the number of subgroups of each finite cyclic group equals the number of factors of its order. In this note I’ll prove this and draw some corollaries.

We need to recall Lagrange’s theorem and its most useful corollary.

Theorem 1 (Lagrange) Let H be a subgroup of the finite group G. Then |H| is a factor of |G|.

Corollary 1 Let G be a finite group with identity e and order n. Then a^{n} = e for all a ∈ G.

From now on G will denote a cyclic group of order n with generator a. Recall that that means that

G = {e, a, a^{2}, a^{3}, …, a^{n−1}}

and that a^{n} = e. Let H be a subgroup of G. By Lagrange’s theorem, |H| is a factor of n.

Theorem 2 Let d be a factor of n. Then G has a unique subgroup H of order d. Indeed

H = ⟨a^{n/d}⟩ = {e, a^{n/d}, a^{2n/d}, …, a^{(d−1)n/d}}

is cyclic.

Proof First of all we will show that the element a^{n/d} has order d. Let b = a^{n/d}. Then b^{d} = (a^{n/d})^{d} = a^{n} = e and if 0 < r < d then b^{r} = (a^{n/d})^{r} = a^{nr/d} ≠ e as 0 < nr/d < n. Hence b has order d and so

⟨a^{n/d}⟩ = ⟨b⟩ = {e, b, b^{2}, …, b^{d−1}} = {e, a^{n/d}, a^{2n/d}, …, a^{(d−1)n/d}}

is a cyclic subgroup of order d.

We have shown that G does have a subgroup of order d, but we need to show that the one we have is the only one. To that end, let us suppose that H is any order d subgroup of G. By the corollary to Lagrange’s theorem, c^{d} = e for each c ∈ H. We may write such a c as a^{j} for 0 ≤ j < n. Then

e = c^{d} = (a^{j})^{d} = a^{jd}

This is only possible if jd is a multiple of n, that is jd = kn where k is an integer. Thus j = k(n/d) is a multiple of n/d. Hence

c = a^{k(n/d)} = (a^{n/d})^{k} ∈ ⟨a^{n/d}⟩.

Consequently H ⊆ ⟨a^{n/d}⟩. But both the sets H and ⟨a^{n/d}⟩ have d elements. It follows that they are equal, and that the only subgroup with order d is ⟨a^{n/d}⟩. The proof is complete. □

From this theorem we can now characterize the generators of G.

Theorem 3 Let b = a^{r} ∈ G, where 0 ≤ r < n. Let g denote the highest common factor of r and n. Then G = ⟨b⟩ if and only if g = 1.

Proof We divide the proof into two parts. First we will show that if g > 1 then G ≠ ⟨b⟩, then we will show that if g = 1 then G = ⟨b⟩.

Suppose first that g > 1. Then b = a^{gs} for some integer s. If j is any integer, then

b^{j} = (a^{gs})^{j} = a^{gsj} = (a^{g})^{js}.

Hence b^{j} ∈ ⟨a^{g}⟩, and so ⟨b⟩ ⊆ ⟨a^{g}⟩. As g is a factor of n then g = n/d where d is also a factor of n; as g > 1 then d < n. Then ⟨a^{g}⟩ = ⟨a^{n/d}⟩ is a group of d elements; as d < n then ⟨a^{g}⟩ ≠ G. As ⟨b⟩ ⊆ ⟨a^{g}⟩ it follows that ⟨b⟩ ≠ G also.

Now suppose that g = 1. Let d be a factor of n, but d ≠ n. Then n/d is a factor of n and n/d > 1. As the highest common factor of r and n is 1, then n/d is not a factor of r. Hence b = a^{r} ∉ ⟨a^{n/d}⟩, the order d subgroup of G. As b ∈ ⟨b⟩ then ⟨b⟩ ≠ ⟨a^{n/d}⟩. Hence by Theorem 2, ⟨b⟩ cannot have order d. The only order ⟨b⟩ can have is thus n; that is ⟨b⟩ = G. □

As a corollary to this we have a very important result in modular arithmetic.

Corollary 2 Let r be an integer with 0 ≤ r < n. Then the congruence

rs ≡ 1 (mod n)  (∗)

is soluble for s ∈ Z if and only if the highest common factor of r and n equals 1.

Proof Let us continue to let G = ⟨a⟩ denote a cyclic group of order n. Note that rs ≡ 1 (mod n) if and only if rs − 1 is a multiple of n; this is true if and only if a^{rs−1} = e which is equivalent to a^{rs} = a. Thus (∗) is soluble if and only if there is an integer s with (a^{r})^{s} = a, that is (∗) is soluble if and only if a ∈ ⟨a^{r}⟩. If the highest common factor of r and n is 1, then ⟨a^{r}⟩ = G by Theorem 3. Thus a ∈ ⟨a^{r}⟩ and (∗) is soluble. On the other hand if the highest common factor of r and n is not 1 then G ≠ ⟨a^{r}⟩. We cannot have a ∈ ⟨a^{r}⟩, since otherwise all powers of a would lie in ⟨a^{r}⟩ and so ⟨a^{r}⟩ would equal G. Thus (∗) is insoluble in this case. □

RJC 3/11/2002