Lagrange's theorem and generators
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 .
- A group of prime order is cyclic and has only the trivial subgroups.
- A generator has order ; in a cyclic group of order , is a generator exactly when .
- The order of in a cyclic group of order is .
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 is a subgroup of a finite group , then divides .
Use it to rule out subgroups. A group of order can have subgroups of order but never of order , or .
It does not guarantee that a subgroup exists for each divisor. If contains a subgroup then divides and divides : in a group of order , if contains a subgroup of order , then is or .
- Lagrange's theorem divides
Allowed in order 12
- 1, 2, 3, 4, 6, 12
Impossible in order 12
- 5, 8, 9
A group has order . Which subgroup order is impossible?
Orders of elements and prime-order groups
Every element's order divides , and a group of prime order is cyclic.
The order of an element equals the order of the subgroup it generates. So by Lagrange the order of every element divides : in a group of order , no element has order or .
If , a prime order, the only divisors are and , so the only subgroups are and . Any non-identity element has order and generates , so the group is cyclic. A group of order has elements of order and one of order .
- Order of any elementdivides
- Group of prime order cyclic, only trivial subgroups
A group has order . 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 .
An element is a generator of if : every element is a power of . Equivalently, has order . A group with a generator is cyclic.
To show generates , list its powers and show you reach every element, or show that its order equals .
- 1
g
- 2
g²
- 3
g³
- 4
g⁴
- 5
g⁵
- 6
g⁶ = e
back to the identity
Then back to step 1
- generates order of
Worked example
Show that generates under multiplication modulo .
- 1
List the powers of modulo .
- 2
They are .
- 3
These are all ten elements.
In multiplication modulo , is a generator?
All the generators of a cyclic group
In a cyclic group of order generated by , the element is a generator exactly when .
If has order , then has order . For the generators are .
Once one generator is known, the others are the powers with . In the modulo group (order ), generates, so the generators are .
The subgroup has order . In a cyclic group of order , has order , and there is exactly one subgroup for each divisor of .
- Order of
- is a generator
| 1 | 2 | 3 | 1 | |
| Order | 18 | 9 | 6 | 18 |
- :
- 1
- Order:
- 18
- :
- 2
- Order:
- 9
- :
- 3
- Order:
- 6
- :
- 1
- Order:
- 18
In a cyclic group of order generated by , 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.
under multiplication modulo has order , generated by . By Lagrange, subgroup orders are .
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
Lagrange allows orders 1, 2, 5, 10
- 2
Order 1: {1}
trivial subgroup
- 3
Order 2: {1, 10}
generated by 10
- 4
Order 5: {1, 3, 4, 5, 9}
generated by 4
- 5
Order 10: the whole group
generated by 2
Order 5
- Generated by
Order 2
- Generated by
Orders 1 and 10
- and
- Trivial subgroups
Worked example
Find the proper non-trivial subgroups of under multiplication modulo .
- 1
Order : has order , and its powers give .
- 2
Order : has order , so the subgroup is .
- 3
It is the only one, because gives , so or , since is prime.
Why can a group of order have no subgroup of order ?
Try an exam question
A group has order . State, with reasons, which of the orders , and are possible for a subgroup of .
[3 marks]
- [1]By Lagrange's theorem, the order of a subgroup divides the order of .
- [1] and both divide , so they are possible.
- [1] does not divide , so it is impossible.
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 ?
1 mark, marked against the mark scheme
Which of the following could be the order of a subgroup of ?
1 mark, marked against the mark scheme