Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 · Cyclic and Permutation Groups

Cyclic Groups

Learn what a cyclic group is, find generators of Z_n, discover primitive roots in groups of units, and see why every cyclic group is abelian.

The simplest groups are those generated by a single element. If you start at a and keep applying the operation, you walk through the whole group. Such groups are called cyclic, and understanding them completely is one of the first big successes of the theory.

Definition

A group G is cyclic if there is an element g ∈ G with G = ⟨g⟩ = {gᵏ : k ∈ ℤ}. The element g is a generator. In additive notation, G = {k·g : k ∈ ℤ}.

  • (ℤ, +) is cyclic, generated by 1 (or by -1). It is infinite.
  • (ℤ_n, + mod n) is cyclic of order n, generated by 1.
  • The rotations of a regular n-gon form a cyclic group generated by one rotation of 360°/n.

Every cyclic group is abelian: gᵃgᵇ = gᵃ⁺ᵇ = gᵇgᵃ.

Generators of ℤ_n

An element k ∈ ℤ_n generates the whole group exactly when gcd(k, n) = 1. If the gcd is d > 1, every multiple of k is a multiple of d, so the multiples never reach 1. If the gcd is 1, Bézout gives kx ≡ 1 (mod n), so 1 is a multiple of k and hence all of ℤ_n is.

Python Which elements generate ℤ_n?

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 generators of ℤ₁₂ are 1, 5, 7, 11, so there are φ(12) = 4 of them. In general ℤ_n has φ(n) generators.

Cyclic groups in multiplication: primitive roots

The group of units U(n) is sometimes cyclic. When U(n) is cyclic, a generator is called a primitive root mod n. For a prime p, U(p) (all of 1, ..., p-1) is always cyclic (a theorem proved later with fields). For example 3 generates U(7): its powers are 3, 2, 6, 4, 5, 1.

Python Find the primitive roots of U(n)

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.

U(8) and U(12) have no primitive roots: they are the Klein-like groups where every element squares to 1. The groups U(n) are cyclic exactly for n = 1, 2, 4, pᵏ, 2pᵏ with p an odd prime. That gives the empty lists above for 8, 12 and 15.

Cyclic versus non-cyclic

A group of order n is cyclic if and only if it has an element of order n. The Klein four-group is not cyclic: its elements have order 1 or 2, but the group has order 4. Subgroups of cyclic groups are cyclic, a fact proved in the next lesson.

flowchart LR
    A["g"] --> B["g²"] --> C["g³"] --> D["..."] --> E["gⁿ = e"] --> A

Repeated multiplication by a generator cycles through every element.

The word "cyclic" comes from the picture above: the powers of g go around a circle. This is why the integers mod n look like a clock.

A quick plot

The cyclic group ℤ_n can be pictured as n points on a circle; adding a generator k jumps k points forward. Here is the "star" traced by a generator.

Python Orbit of a generator on a circle

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.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which elements of ℤ₁₀ are generators?

    Generators are the k with gcd(k, 10) = 1: 1, 3, 7, 9.
  2. 2. Is every cyclic group abelian?

    All elements are powers of one generator, and powers of g commute.
  3. 3. A primitive root mod p is:

    It is an element whose powers produce every nonzero residue mod p.
  4. 4. How many generators does ℤ₁₂ have?

    φ(12) = 4: the generators are 1, 5, 7 and 11.

Summary

  • A cyclic group is generated by a single element; it is always abelian.
  • k generates ℤ_n exactly when gcd(k, n) = 1, so there are φ(n) generators.
  • Generators of U(n) are primitive roots; they exist only for certain n.
  • A group of order n is cyclic exactly when it has an element of order n.

Next: Subgroups and Orders in Cyclic Groups