Skip to content

Lesson 10 Β· 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