Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 Ā· Cyclic and Permutation Groups

Subgroups and Orders in Cyclic Groups

Prove that subgroups of cyclic groups are cyclic, that Z_n has exactly one subgroup for each divisor of n, and count elements of each order with the totient.

Cyclic groups are completely understood. Every subgroup is cyclic, the subgroups are in one-to-one correspondence with the divisors of the order, and we can say exactly how many elements have each order. This lesson proves and tests those results.

Subgroups of cyclic groups are cyclic

Theorem. Every subgroup of a cyclic group is cyclic.

Proof idea. Let G = ⟨g⟩ and H ≤ G, H ≠ {e}. Choose the smallest positive m with gᵐ ∈ H. If gįµ ∈ H, divide: k = qm + r with 0 ≤ r < m. Then gʳ = gįµ(gᵐ)⁻ᵠ ∈ H, and minimality of m forces r = 0. So every element of H is a power of gᵐ, i.e. H = ⟨gᵐ⟩. āˆŽ

For infinite ℤ, the subgroups are exactly nℤ = ⟨n⟩ for n = 0, 1, 2, ....

The order of a power

In a cyclic group ⟨g⟩ of order n, the element gįµ has order

|gįµ| = n / gcd(n, k).

For example in ℤ₁₂ (additive, so gįµ is k), element 8 has order 12 / gcd(12, 8) = 12 / 4 = 3: indeed 8, 16 ≔ 4, 24 ≔ 0 after three steps.

Python Check the order formula

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

One subgroup for each divisor

Theorem. If G = ⟨g⟩ has order n, then for each positive divisor d of n there is exactly one subgroup of order d, namely ⟨g^(n/d)⟩. There are no other subgroups.

So the number of subgroups of ℤ_n equals the number of divisors of n. For n = 12 that is 6, matching our brute-force search earlier.

Python List the subgroup for each divisor

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting elements of each order

How many elements of ℤ_n have order exactly d? They are the generators of the unique subgroup of order d, which is a cyclic group of order d, and there are φ(d) of them. This gives a beautiful identity, since every element has some order dividing n:

Ī£ over d | n of φ(d) = n.

Python Elements of each order and the totient sum

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The identity Ī£ φ(d) = n is a neat way to remember that ℤ_n splits into groups of elements of each order, with φ(d) elements of order d.

Consequence: cyclic groups of composite order

If gcd(m, k) = 1, then ℤ_m Ɨ ℤ_k ≅ ℤ_(mk), the Chinese remainder theorem seen as a group fact. For example ℤ₂ Ɨ ā„¤ā‚ƒ has an element (1, 1) of order 6 and so is cyclic, while ℤ₂ Ɨ ℤ₂ is not cyclic (all elements have order 1 or 2, group order 4). This is the first time you see a direct product; the full treatment is in a later chapter.

flowchart TB
    G["ℤ₁₂"] --> A["order 12: φ(12) = 4 elements"]
    G --> B["order 6: φ(6) = 2"]
    G --> C["order 4: φ(4) = 2"]
    G --> D["order 3: φ(3) = 2"]
    G --> E["order 2: φ(2) = 1"]
    G --> F["order 1: φ(1) = 1"]

The element counts 4 + 2 + 2 + 2 + 1 + 1 add up to 12.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. What is the order of 8 in ℤ₁₂?

    n / gcd(n, k) = 12 / gcd(12, 8) = 12 / 4 = 3.
  2. 2. How many subgroups does ā„¤ā‚ā‚ˆ have?

    One per divisor of 18: 1, 2, 3, 6, 9, 18.
  3. 3. How many elements of order 6 are in ā„¤ā‚ƒā‚†?

    6 divides 36, and there are φ(6) = 2 elements of order 6.
  4. 4. Which statement is true of subgroups of a cyclic group?

    The division argument shows any subgroup is generated by one power of the generator.

Summary

  • Every subgroup of a cyclic group is cyclic.
  • In a cyclic group of order n, the element gįµ has order n / gcd(n, k).
  • There is exactly one subgroup of each order d | n.
  • It contains φ(d) generators, so Ī£ φ(d) = n over the divisors.

Next: Permutations and Cycle Notation