Lagrange's theorem and generators

Lagrange's theorem and generators

Spec DG10–DG11 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Lagrange's theorem: the order of a subgroup divides the order of the group.
  • The order of every element divides ∣G∣|G|.
  • A group of prime order is cyclic and has only the trivial subgroups.
  • A generator has order ∣G∣|G|; in a cyclic group of order nn, aka^k is a generator exactly when gcd⁡(k,n)=1\gcd(k,n)=1.
  • The order of aka^k in a cyclic group of order nn is ngcd⁡(k,n)\dfrac{n}{\gcd(k,n)}.

Lagrange's theorem

The order of any subgroup of a finite group divides the order of the group, so it rules out some subgroup orders.

Lagrange's theorem: if HH is a subgroup of a finite group GG, then ∣H∣|H| divides ∣G∣|G|.

Use it to rule out subgroups. A group of order 1212 can have subgroups of order 1,2,3,4,6,121,2,3,4,6,12 but never of order 55, 88 or 99.

It does not guarantee that a subgroup exists for each divisor. If KK contains a subgroup HH then ∣H∣|H| divides ∣K∣|K| and ∣K∣|K| divides ∣G∣|G|: in a group of order 1212, if KK contains a subgroup of order 66, then ∣K∣|K| is 66 or 1212.

01234567891011121312345689
Possible subgroup orders in a group of order 12. Lagrange allows only divisors of 12 (filled); 5, 8 and 9 (open) are ruled out.
  • Lagrange's theorem∣H∣|H| divides ∣G∣|G|

Allowed in order 12

  • 1, 2, 3, 4, 6, 12

Impossible in order 12

  • 5, 8, 9

A group has order 1515. Which subgroup order is impossible?

Orders of elements and prime-order groups

Every element's order divides ∣G∣|G|, and a group of prime order is cyclic.

The order of an element aa equals the order of the subgroup ⟨a⟩={e,a,a2,… }\langle a\rangle=\{e,a,a^2,\dots\} it generates. So by Lagrange the order of every element divides ∣G∣|G|: in a group of order 1212, no element has order 55 or 88.

If ∣G∣=p|G|=p, a prime order, the only divisors are 11 and pp, so the only subgroups are {e}\{e\} and GG. Any non-identity element has order pp and generates GG, so the group is cyclic. A group of order 77 has 66 elements of order 77 and one of order 11.

0123456Order 1Order 7Element orderNumber of elements
A group of order 7 (prime): the identity has order 1 and the other 6 elements all have order 7, so each generates the group.
  • Order of any elementdivides ∣G∣|G|
  • Group of prime order ppcyclic, only trivial subgroups

A group has order 1313. What is the order of a non-identity element?

Generators

An element is a generator if its powers give every element, which happens exactly when its order equals ∣G∣|G|.

An element gg is a generator of GG if ⟨g⟩=G\langle g\rangle=G: every element is a power of gg. Equivalently, gg has order ∣G∣|G|. A group with a generator is cyclic.

To show gg generates GG, list its powers and show you reach every element, or show that its order equals ∣G∣|G|.

  1. 1

    g

  2. 2

    g²

  3. 3

    g³

  4. 4

    g⁴

  5. 5

    g⁵

  6. 6

    g⁶ = e

    back to the identity

Then back to step 1

A generator g of a cyclic group of order 6: its powers reach every element.
  • gg generates GGorder of gg =∣G∣=|G|

Worked example

Show that 22 generates {1,2,…,10}\{1,2,\dots,10\} under multiplication modulo 1111.

In multiplication modulo 1111, is 33 a generator?

All the generators of a cyclic group

In a cyclic group of order nn generated by aa, the element aka^k is a generator exactly when gcd⁡(k,n)=1\gcd(k,n)=1.

If G=⟨a⟩G=\langle a\rangle has order nn, then aka^k has order ngcd⁡(k,n)\frac{n}{\gcd(k,n)}. For n=18n=18 the generators are a,a5,a7,a11,a13,a17a,a^5,a^7,a^{11},a^{13},a^{17}.

Once one generator gg is known, the others are the powers gkg^k with gcd⁡(k,n)=1\gcd(k,n)=1. In the modulo 1111 group (order 1010), 22 generates, so the generators are 21,23,27,29=2,8,7,62^1,2^3,2^7,2^9=2,8,7,6.

The subgroup ⟨ak⟩\langle a^k\rangle has order ngcd⁡(k,n)\frac{n}{\gcd(k,n)}. In a cyclic group of order 1818, ⟨a3⟩\langle a^3\rangle has order 66, and there is exactly one subgroup for each divisor of 1818.

05101512345678910111213141516kOrder of a^k
Order of a^k in a cyclic group of order 18 is 18 ÷ gcd(k, 18). It is 18 (a generator) for k = 1, 5, 7, 11, 13 (and 17).
  • Order of aka^kngcd⁡(k,n)\dfrac{n}{\gcd(k,n)}
  • aka^k is a generatorgcd⁡(k,n)=1\gcd(k,n)=1

aa

gcd⁡(k,18)\gcd(k,18):
1
Order:
18

a2a^2

gcd⁡(k,18)\gcd(k,18):
2
Order:
9

a3a^3

gcd⁡(k,18)\gcd(k,18):
3
Order:
6

a5a^5

gcd⁡(k,18)\gcd(k,18):
1
Order:
18

In a cyclic group of order 1212 generated by aa, which element is also a generator?

Subgroups of a group of order 10

Use Lagrange to list the possible orders, then take powers of suitable elements.

G={1,…,10}G=\{1,\dots,10\} under multiplication modulo 1111 has order 1010, generated by 22. By Lagrange, subgroup orders are 1,2,5,101,2,5,10.

In an exam, state Lagrange's theorem in words, say which orders it allows, then find the subgroups by taking powers of suitable elements.

  1. 1

    Lagrange allows orders 1, 2, 5, 10

  2. 2

    Order 1: {1}

    trivial subgroup

  3. 3

    Order 2: {1, 10}

    generated by 10

  4. 4

    Order 5: {1, 3, 4, 5, 9}

    generated by 4

  5. 5

    Order 10: the whole group

    generated by 2

Subgroups of the group of order 10 (multiplication mod 11).

Order 5

  • {1,3,4,5,9}\{1,3,4,5,9\}
  • Generated by 44

Order 2

  • {1,10}\{1,10\}
  • Generated by 1010

Orders 1 and 10

  • {1}\{1\} and GG
  • Trivial subgroups

Worked example

Find the proper non-trivial subgroups of G={1,…,10}G=\{1,\dots,10\} under multiplication modulo 1111.

Why can a group of order 1010 have no subgroup of order 44?

Try an exam question

A group GG has order 1818. State, with reasons, which of the orders 44, 66 and 99 are possible for a subgroup of GG.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which of the following could be the order of a subgroup of GG?

1 mark, marked against the mark scheme

Revision notes