Abstract algebra
Groups: orders, generators, and Lagrange’s theorem.
Pen and paper is fine · no calculator needed why?
Opens at level 58. You're level 1. You can read and practice here now.
the idea
A group is a set with an operation that stays in the set, where brackets don’t matter, with a do-nothing element, and that can always be undone. The numbers 0 to n − 1 under addition mod n form ℤₙ, a clock with n hours: in ℤ₁₂, 9 + 5 gives 2.
An element’s order is the fewest times you apply it to return to the start. The group’s order is its size. A permutation is a shuffle: the cycle (1 2 3) sends 1 to 2, 2 to 3, and 3 to 1.
Lagrange’s theorem: a subgroup’s order divides the group’s order.
techniques
Divide n by the gcd
- Find gcd(k, n), the greatest common divisor.
- The order of k is n ÷ gcd(k, n).
- k generates ℤₙ when gcd(k, n) is 1. The count of such k is φ(n).
- For φ(n), multiply n by (1 − 1/p) for each prime p dividing n.
worked example
What is the order of 10 in the group ℤ₂₄ under addition mod 24?
- The gcd of 10 and 24 is 2.
- 24 ÷ 2 = 12, so 10 has order 12.
- Check: 12 × 10 = 120 = 5 × 24.
Answer: 12
LCM of the cycle lengths
- Read off each cycle’s length: (1 2 3) has length 3.
- Each cycle returns to its start after its own length; all return together at the least common multiple.
worked example
What is the order of the permutation (1 2 3 4)(5 6 7 8 9 10) in S₁₀?
- The cycles have lengths 4 and 6.
- The least common multiple of 4 and 6 is 12.
Answer: 12
Subgroup orders divide the order
- Divide the group’s order by each option.
- An exact division means allowed. A remainder means ruled out.
worked example
A group has order 36. Which of these does Lagrange’s theorem rule out as the order of a subgroup: 4, 9, 12 or 8?
- 36 ÷ 4 = 9. 36 ÷ 9 = 4. 36 ÷ 12 = 3.
- 36 ÷ 8 leaves a remainder of 4, so 8 is ruled out.
Answer: 8
watch out for
- Giving the group’s size instead of the element’s order. In ℤ₁₅ the element 6 has order 5, not 15.
- Counting every nonzero element as a generator. Only k with gcd(k, n) = 1 generate ℤₙ.
- Adding or multiplying the cycle lengths. Cycles of lengths 2 and 4 line up again after 4 steps, not 6 or 8.
practice
Order of an element
worked example
What is the order of 8 in the group ℤ₃₀ under addition mod 30?
Answer: 15
- The order of k in ℤₙ is n ÷ gcd(k, n): the number of copies of k it takes to reach a multiple of n.
- gcd(8, 30) = 2, so the order is 30 ÷ 2 = 15.
Generators
worked example
How many generators does the cyclic group ℤ₂₇ (addition mod 27) have?
Answer: 18
- k generates ℤ₂₇ exactly when gcd(k, 27) = 1, so count those: φ(27).
- The only prime dividing 27 is 3, so φ(27) = 27 × (1 − 1/3) = 18.
Order of a permutation
worked example
What is the order of the permutation (1 2 3 4 5)(6 7 8 9 10) in S₁₂?
Answer: 5
- The cycles are disjoint, with lengths 5 and 5.
- Each cycle returns to its start after its own length, so all of them do together after lcm(5, 5) = 5.
Possible subgroup sizes
worked example
A group has order 42. Which of these does Lagrange’s theorem rule out as the order of a subgroup?
- 3
- 7
- 15
- 14
Answer: 15
- By Lagrange’s theorem, a subgroup’s order divides the group’s order.
- 3, 7 and 14 divide 42; 15 doesn’t (42 ÷ 15 leaves remainder 12).