Lagrange's theorem
The cosets of a subgroup cut a finite group into blocks of one size. What does counting those blocks say about which subgroups, and which element orders, a group can have?
Where you are 4 in Cosets and quotients
Why this exists
Cosets showed that a subgroup H of a group G cuts G into left cosets that do not overlap and all have the size of H. When G is finite, counting gives a strong restriction at once: the size of H divides the size of G. A group of order 12 has no subgroup of order 5, no element of order 8, and a group of prime order has no subgroups at all except the obvious two. The same count proves Fermat’s and Euler’s theorems in two lines, and it is the first tool for asking what a group of a given order can look like.
Definition
The order of a finite group G is its number of elements, |G|. For H \le G, the index [G : H] is the number of left cosets of H in G; it also counts the right cosets (Cosets, Theorem 5). The order \operatorname{ord}(g) of an element is the least positive integer n with g^n = e, or infinite if there is none (Cyclic groups), and \operatorname{ord}(g) = |\langle g \rangle| (Theorem 4 there). Lagrange’s theorem connects these three numbers.
Intuition
Picture G as a row of |G| objects sorted into boxes, one box per left coset of H. Every box holds exactly |H| objects and every object is in exactly one box. Then |G| is the number of boxes times |H|, and there is no room for a remainder. Nothing about the operation is used beyond the two facts that make the boxes: they partition G, and they have one size.
Results
Theorem 1 (Lagrange’s theorem). Let G be a finite group and H \le G. Then
In particular |H| divides |G|, and [G : H] = |G|/|H|.
Corollary 2 (orders of elements). If G is a finite group and g \in G, then \operatorname{ord}(g) divides |G|, and g^{|G|} = e.
Corollary 3 (prime order). If |G| = p for a prime p, then G is cyclic, every g \ne e generates G, and the only subgroups of G are \{e\} and G.
Theorem 4 (the index multiplies). Let K \le H \le G, where G may be infinite, and suppose [G : H] = m and [H : K] = n are finite. If g_1H, \dots, g_mH are the left cosets of H in G and h_1K, \dots, h_nK those of K in H, then the mn sets g_ih_jK are distinct and are all the left cosets of K in G. So [G : K] = [G : H]\,[H : K].
Corollary 5 (Euler and Fermat). If n \ge 1 and \gcd(a, n) = 1, then a^{\varphi(n)} \equiv 1 \pmod{n}. In particular, if p is prime and p \nmid a, then a^{p-1} \equiv 1 \pmod{p}.
Why it is true
Proof of Theorem 1. The left cosets of H partition G (Cosets, Theorem 1), and since G is finite there are finitely many, say gH for g in a set of [G : H] representatives. Each has |H| elements (Theorem 4 there). Adding the sizes of disjoint sets that cover G gives |G| = [G : H]\,|H|. \square
Proof of Corollary 2. \langle g \rangle is a subgroup of G (Cyclic groups, Theorem 2) of order \operatorname{ord}(g) (Theorem 4 there), so \operatorname{ord}(g) divides |G| by Theorem 1. Writing |G| = k \operatorname{ord}(g), the laws of exponents (Lemma 1 there) give g^{|G|} = (g^{\operatorname{ord}(g)})^k = e^k = e. \square
Proof of Corollary 3. Let g \ne e. The order of \langle g \rangle divides p and is at least 2, since \langle g \rangle contains e and g. So |\langle g \rangle| = p = |G| and \langle g \rangle = G. Any subgroup has order 1 or p by Theorem 1, so it is \{e\} or G. \square
Proof of Theorem 4. First, the sets cover G. Let x \in G. Then x \in g_iH for some i, so x = g_ih with h \in H; and h \in h_jK for some j, so h = h_jk with k \in K. Hence x = g_ih_jk \in g_ih_jK.
Next, they are distinct. Suppose g_ih_jK = g_{i'}h_{j'}K. The element g_ih_j lies in the left side, so g_ih_j = g_{i'}h_{j'}k for some k \in K. Since h_j \in H and h_{j'}k \in H, this element lies in both g_iH and g_{i'}H; these cosets meet, so they are equal (Cosets, Lemma 2), and i = i'. Multiplying every element of g_ih_jK = g_ih_{j'}K on the left by g_i^{-1} gives h_jK = h_{j'}K, so j = j'.
Each g_ih_jK is a left coset of K in G, and every left coset of K in G is one of them: it contains some x, which lies in some g_ih_jK, and two left cosets that meet are equal. So there are exactly mn left cosets of K in G. \square
When G is finite, Theorem 4 also follows from Theorem 1: \displaystyle [G : K] = \frac{|G|}{|K|} = \frac{|G|}{|H|} \cdot \frac{|H|}{|K|}.
Proof of Corollary 5. Since \gcd(a, n) = 1, the class [a]_n lies in \mathbb{Z}_n^\times, an abelian group of order \varphi(n) (Integers mod n, symmetries and matrices as groups, Theorem 2). By Corollary 2, [a]^{\varphi(n)} = [1], which says a^{\varphi(n)} \equiv 1 \pmod{n}. For a prime p, \varphi(p) = p - 1, and \gcd(a, p) = 1 exactly when p \nmid a. \square
This is the group-theoretic proof of Theorems 1 and 7 of Fermat's little theorem, which that lesson proves by counting residues.
Worked examples
Orders in the units mod 28
Find the order of every element of \mathbb{Z}_{28}^\times (writing k for [k]) and check Corollary 2. Does \mathbb{Z}_{28}^\times have an element of order 4? A subgroup of order 4? Use the orders to find 3^{100} \bmod 28.
SolutionThe units are the classes coprime to 28 = 2^2 \cdot 7, namely 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, so |\mathbb{Z}_{28}^\times| = \varphi(28) = 12. By Corollary 2 every order lies in \{1, 2, 3, 4, 6, 12\}. Squares and cubes mod 28:
| a | a^2 | a^3 | \operatorname{ord}(a) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 3 | 9 | 27 | 6 |
| 5 | 25 | 13 | 6 |
| 9 | 25 | 1 | 3 |
| 11 | 9 | 15 | 6 |
| 13 | 1 | 13 | 2 |
| 15 | 1 | 15 | 2 |
| 17 | 9 | 13 | 6 |
| 19 | 25 | 27 | 6 |
| 23 | 25 | 15 | 6 |
| 25 | 9 | 1 | 3 |
| 27 | 1 | 27 | 2 |
Every cube lies in \{1, 13, 15, 27\}, and each of these squares to 1: 13^2 = 169 = 6 \cdot 28 + 1, 15^2 = 225 = 8 \cdot 28 + 1, and 27 \equiv -1. So a^6 = (a^3)^2 = 1 for every a, and \operatorname{ord}(a) divides 6 (Cyclic groups, Theorem 4). The order is then read from the table: 2 if a^2 = 1, 3 if a^3 = 1, and otherwise 6. All twelve orders divide 12.
No element has order 4 (or 12, so the group is not cyclic). Yet V = \{1, 13, 15, 27\} is a subgroup of order 4: each element squares to 1, and 13 \cdot 15 = 195 \equiv 27, 13 \cdot 27 \equiv -13 \equiv 15, 15 \cdot 27 \equiv -15 \equiv 13, so V is closed and the finite test applies (Subgroups, Theorem 5). A divisor of |G| can be the order of a subgroup without being the order of an element. Listing every subgroup (a finite search) gives the ten below; each order divides 12, as Theorem 1 requires.
Since a^6 \equiv 1 \pmod{28} for every a coprime to 28, exponents may be reduced mod 6, not just mod \varphi(28) = 12 as Corollary 5 allows. As 100 = 6 \cdot 16 + 4,
Counting matrices by determinant
Let G = \operatorname{GL}_2(\mathbb{Z}_5) and let H be the set of A \in G with \det A = \pm 1, that is, \det A \in \{1, 4\}. Show that H \le G and find |H| without listing its elements.
SolutionG has order (5^2 - 1)(5^2 - 5) = 24 \cdot 20 = 480 (Integers mod n, symmetries and matrices as groups, Theorem 7). The rule \det(AB) = \det A \det B is a polynomial identity in the eight entries (Properties of determinants: row operations, products, transposes), so it holds mod 5. The set D = \{1, 4\} is a subgroup of \mathbb{Z}_5^\times, since 4 \cdot 4 = 16 \equiv 1. So I_2 \in H, and if \det A, \det B \in D then \det(AB) \in D: H is finite, nonempty and closed, hence a subgroup (Subgroups, Theorem 5).
By Cosets Lemma 2, AH = BH exactly when A^{-1}B \in H, that is, when (\det A)^{-1} \det B \in D, or \det B = \pm \det A. Every c \in \{1, 2, 3, 4\} is a determinant, as \det \begin{pmatrix} c & 0 \\ 0 & 1 \end{pmatrix} = c. So there are exactly two left cosets: the matrices with determinant in \{1, 4\} and those with determinant in \{2, 3\}. Thus [G : H] = 2 and, by Theorem 1, |H| = 480/2 = 240.
With D = \{1\} the same argument gives one coset per determinant, four in all, so |\operatorname{SL}_2(\mathbb{Z}_5)| = 480/4 = 120: the case p = 5 of the count p(p^2 - 1) in Integers mod n, symmetries and matrices as groups Exercise 15, which matched the determinant classes by hand. Theorem 4 ties the two subgroups together: \operatorname{SL}_2(\mathbb{Z}_5) \le H \le G, and 4 = [G : H]\,[H : \operatorname{SL}_2(\mathbb{Z}_5)] = 2 \cdot 2.
An index in an infinite group
In \mathbb{Z}, take K = 12\mathbb{Z} \le H = 4\mathbb{Z} \le G = \mathbb{Z}. Find [G : H], [H : K] and [G : K], and the representatives that the proof of Theorem 4 produces.
SolutionHere |G|/|H| means nothing, since both are infinite, so Theorem 1 does not apply, but Theorem 4 does. The cosets of 4\mathbb{Z} in \mathbb{Z} are g + 4\mathbb{Z} for g = 0, 1, 2, 3, so [G : H] = 4. A multiple 4k has remainder 0, 4 or 8 on division by 12, so the cosets of 12\mathbb{Z} in 4\mathbb{Z} are h + 12\mathbb{Z} for h = 0, 4, 8, and [H : K] = 3. Written additively, Theorem 4’s cosets are g + h + 12\mathbb{Z}, and the twelve sums
are the twelve remainders mod 12, each once. So [G : K] = 12 = 4 \cdot 3, and each coset of 4\mathbb{Z} splits into three cosets of 12\mathbb{Z}, for instance 1 + 4\mathbb{Z} = (1 + 12\mathbb{Z}) \cup (5 + 12\mathbb{Z}) \cup (9 + 12\mathbb{Z}).
Elements of prime order
Let p be prime. Prove: (a) in any group, two distinct subgroups of order p meet only in e; (b) in a finite group, the number of elements of order p is p - 1 times the number of subgroups of order p.
SolutionProof. (a) Let P \ne P' have order p. Then P \cap P' is a subgroup of P (Subgroups, Theorem 6), so its order divides p by Theorem 1. If it were p, then P \cap P' = P, so P \subseteq P', and two sets of the same finite size with one inside the other are equal: P = P', which is false. So P \cap P' = \{e\}.
(b) Each subgroup P of order p is cyclic, and its p - 1 elements other than e all have order p (Corollary 3). Conversely, an element g of order p lies in the subgroup \langle g \rangle of order p, and by (a) in no other one. So the elements of order p are split into disjoint sets of size p - 1, one for each subgroup of order p. \square
In \mathbb{Z}_{28}^\times (Example 1) there are three elements of order 2 and two of order 3, so three subgroups of order 2 and one of order 3, as the figure shows.
The smallest groups are abelian
Prove that every group of order at most 5 is abelian, and conclude that the least order of a group that is not abelian is 6.
SolutionProof. Order 1 is clear. Orders 2, 3 and 5 are prime, so the group is cyclic (Corollary 3) and hence abelian (Cyclic groups, Theorem 3). Let |G| = 4. If some element has order 4, it generates G, and G is cyclic. Otherwise every order divides 4 (Corollary 2) and is not 4, so x^2 = e, that is x^{-1} = x, for every x \in G. Then for all a, b \in G,
using the inverse of a product (Binary operations and the group axioms, Theorem 3). \square
The group \operatorname{GL}_2(\mathbb{Z}_2) has order (4 - 1)(4 - 2) = 6 and is not abelian: with X and Y as in Cosets Example 4, XY \ne YX. So 6 is the least such order.
No subgroup of order six
Let T be the group of rotations of a regular tetrahedron. It has 12 elements: the identity; for each of the four vertices, the rotations by 120^\circ and 240^\circ about the axis through that vertex and the center of the opposite face, eight rotations of order 3; and for each of the three pairs of opposite edges, the half-turn about the line through their midpoints, three rotations of order 2. (That there are no others is taken from geometry here; the orbit-stabilizer count of Group actions, orbits and stabilizers confirms it, as 4 \cdot 3 = 12.) Prove that T has no subgroup of order 6, although 6 divides 12.
SolutionProof. Suppose H \le T and |H| = 6. By Theorem 1, [T : H] = 2, so the left cosets are H and one other, which must be T \setminus H.
We show g^2 \in H for every g \in T. If g \in H, this is closure. If g \notin H, then gH = T \setminus H. Were g^2 \notin H too, we would have g^2H = T \setminus H = gH, so g^{-1}g^2 = g \in H by Cosets Lemma 2, a contradiction.
Now let x be any of the eight rotations of order 3. Since x^3 = e, we get x = x^4 = (x^2)^2, a square, so x \in H. Then H contains these eight elements and e, nine in all, more than 6. This contradiction shows there is no such H. \square
By Example 4, T has 8/2 = 4 subgroups of order 3, and Exercise 10 finds subgroups of orders 2 and 4. So 6 is the one divisor of 12 that is not the order of a subgroup of T.
Boundaries
- The converse fails. A divisor of |G| need not be the order of a subgroup (Example 6). It is for cyclic groups (Cyclic groups, Theorem 10), and for prime powers in every finite group (The Sylow theorems, where this is proved).
- A divisor need not be an element order. In Example 1, 4 and 12 divide 12, but no element has either order. For a prime divisor there is always an element of that order (Cauchy’s theorem, proved in The Sylow theorems).
- Size is not structure. A subset whose size divides |G| need not be a subgroup: \{1, 3\} \subseteq \mathbb{Z}_{28}^\times has two elements, but 3^2 = 9 is not in it.
- Infinite groups. Theorem 1 and Corollary 2 need G finite. In \mathbb{C}^\times the root of unity e^{2\pi i/n} has order n for every n \ge 1 (Roots of a complex number and roots of unity), so no single number bounds the element orders. Theorem 4 survives whenever the indices are finite (Example 3).
Where this goes next
A subgroup of index 2 has equal left and right cosets (Cosets, Exercise 13); such subgroups are the first examples of Normal subgroups. For a normal subgroup N of a finite group, the cosets form the group G/N of Quotient groups, of order [G : N] = |G|/|N|. In a group action, the orbit of a point matches the cosets of its stabilizer, so Theorem 1 becomes the orbit-stabilizer count. The The Sylow theorems give the strongest partial converse, and Isomorphisms shows that all groups of prime order p have the same structure as \mathbb{Z}_p.
Exercises
Orders and divisors
- List the order of each element of \mathbb{Z}_{15}^\times = \{1, 2, 4, 7, 8, 11, 13, 14\} and check that each divides |\mathbb{Z}_{15}^\times|. Is the group cyclic?
- Which of 4, 5, 6, 15, 20 can be the order of a subgroup of a group of order 30?
- A finite group has an element of order 6 and an element of order 10. What is the least its order can be?
- Using Exercise 1, find 2^{100} \bmod 15 and 7^{50} \bmod 15, and show that a^4 \equiv 1 \pmod{15} whenever \gcd(a, 15) = 1.
- A group of order 55 is not cyclic. What orders can its elements other than e have?
Counting with the index
- In G = \operatorname{GL}_2(\mathbb{Z}_7), let H be the set of matrices of determinant \pm 1. Show that H \le G, and find [G : H] and |H|.
- In G = \operatorname{GL}_2(\mathbb{Z}_3), let H be the set of invertible matrices \begin{pmatrix} a & b \\ 0 & d \end{pmatrix}. Show that H \le G, and find |H| and [G : H].
- Let K \le H \le G with |G| = 72, [G : H] = 4 and |K| = 6. Find |H|, [H : K] and [G : K].
- At a carillon, Hiro rings four bells in some order, and a change rearranges that order. The 24 rearrangements form a group under composition (Arrangements and factorials, Binary operations and the group axioms). Leah applies one change over and over. Show: (a) after 24 changes the bells are back in their starting order, whatever the change; (b) no change other than the identity restores the order after exactly 5 applications; (c) if 9 applications restore the order, then 3 already do.
- For the tetrahedral group T of Example 6: (a) how many subgroups of order 2 and of order 3 does it have? (b) Show that e and the three half-turns form a subgroup. (c) Which element orders occur, and is T cyclic?
Proofs
- Let H, K \le G be finite with \gcd(|H|, |K|) = 1. Prove that H \cap K = \{e\}.
- Let p be prime and |G| = p^2. Prove that if G is not cyclic, it has exactly p + 1 subgroups of order p.
- Let G be finite and \gcd(m, |G|) = 1. Prove that x \mapsto x^m is a bijection from G to G.
- Let H \le K \le G with [G : H] = p prime. Prove that K = H or K = G.
- Let H, K be finite subgroups of G and HK = \{hk : h \in H, k \in K\}. Prove that |HK| = |H|\,|K| / |H \cap K|.
- Let [G : H] = 2. Prove that every element of G of odd order lies in H.
- Prove that a group of order 6 that is not cyclic has an element of order 2 and an element of order 3.
Answers
- |\mathbb{Z}_{15}^\times| = 8. Squares: 4^2 = 16 \equiv 1, 11^2 = 121 \equiv 1, 14^2 = 196 \equiv 1, so 4, 11, 14 have order 2; 2^2 = 4, 7^2 = 49 \equiv 4, 8^2 = 64 \equiv 4, 13^2 = 169 \equiv 4, and 4^2 \equiv 1, so 2, 7, 8, 13 have order 4; 1 has order 1. All divide 8. No element has order 8, so the group is not cyclic.
- Only 5, 6 and 15: by Theorem 1 a subgroup order divides 30, which rules out 4 and 20. All three occur, in \mathbb{Z}_{30} for instance (Cyclic groups, Theorem 10).
- 30. Both 6 and 10 divide |G| (Corollary 2), so \operatorname{lcm}(6, 10) = 30 does; and \mathbb{Z}_{30} has 5 of order 6 and 3 of order 10.
- \operatorname{ord}(2) = 4 and 100 = 4 \cdot 25, so 2^{100} \equiv 1. \operatorname{ord}(7) = 4 and 50 = 4 \cdot 12 + 2, so 7^{50} \equiv 7^2 = 49 \equiv 4. Every order in Exercise 1 divides 4, so a^4 \equiv 1 for every unit.
- By Corollary 2 the orders divide 55 = 5 \cdot 11, so they lie in \{1, 5, 11, 55\}. An element of order 55 would generate the group, which is not cyclic, and only e has order 1. So each has order 5 or 11.
- |G| = (49 - 1)(49 - 7) = 2016. The set \{1, 6\} is a subgroup of \mathbb{Z}_7^\times, as 6 \cdot 6 = 36 \equiv 1, so by the product rule H is closed, contains I_2, and is a subgroup by the finite test. As in Example 2, AH = BH exactly when \det B = \pm \det A; every class in \mathbb{Z}_7^\times is a determinant, and they pair as \{1, 6\}, \{2, 5\}, \{3, 4\}. So [G : H] = 3 and |H| = 2016/3 = 672.
- \begin{pmatrix} a & b \\ 0 & d \end{pmatrix}\begin{pmatrix} a' & b' \\ 0 & d' \end{pmatrix} = \begin{pmatrix} aa' & ab' + bd' \\ 0 & dd' \end{pmatrix} is again in H, since aa'dd' \ne 0 in the field \mathbb{Z}_3, and I_2 \in H, so H is a subgroup by the finite test. Invertible means ad \ne 0, so a, d \in \{1, 2\} and b \in \{0, 1, 2\}: |H| = 12. With |G| = (9 - 1)(9 - 3) = 48, [G : H] = 48/12 = 4.
- |H| = 72/4 = 18, [H : K] = 18/6 = 3, and [G : K] = 72/6 = 12 = 4 \cdot 3, as Theorem 4 requires.
- Let g be the change. (a) g^{24} = e by Corollary 2. (b) If g^5 = e, then \operatorname{ord}(g) divides 5 and 24, hence \gcd(5, 24) = 1, so g = e. (c) If g^9 = e, then \operatorname{ord}(g) divides \gcd(9, 24) = 3, so g^3 = e.
- (a) By Example 4: three elements of order 2 give 3 subgroups of order 2, and eight of order 3 give 8/2 = 4 subgroups of order 3. (b) Number the vertices 1 to 4; a rotation is fixed by where it sends them. The half-turns u, v, w swap 1 \leftrightarrow 2 and 3 \leftrightarrow 4; 1 \leftrightarrow 3 and 2 \leftrightarrow 4; 1 \leftrightarrow 4 and 2 \leftrightarrow 3. Doing v then u sends 1 \to 3 \to 4, 2 \to 4 \to 3, 3 \to 1 \to 2, 4 \to 2 \to 1, so uv = w; in the same way the product of any two of them is the third, and each squares to e. The set is closed, so it is a subgroup of order 4. (c) Orders 1, 2, 3 only; there is no element of order 12, so T is not cyclic.
- Proof. H \cap K is a subgroup of H and of K (Subgroups, Theorem 6), so by Theorem 1 its order divides |H| and |K|, hence divides \gcd(|H|, |K|) = 1. So H \cap K = \{e\}. \square
- Proof. Element orders divide p^2 (Corollary 2), so they are 1, p or p^2. An element of order p^2 would generate G, which is not cyclic. So all p^2 - 1 elements other than e have order p, and by Example 4(b) there are (p^2 - 1)/(p - 1) = p + 1 subgroups of order p. \square
- Proof. Let n = |G| and choose integers u, v with um + vn = 1 (Bezout's identity and the extended Euclidean algorithm). By Corollary 2, x^n = e for all x, so x = x^{um + vn} = (x^m)^u (x^n)^v = (x^m)^u. One to one: if x^m = y^m, then x = (x^m)^u = (y^m)^u = y. Onto: given y, the element x = y^u has x^m = y^{um} = y^{1 - vn} = y\,(y^n)^{-v} = y. \square
- Proof. Each left coset of K is a union of left cosets of H (Cosets, Exercise 15), and distinct cosets of K are disjoint, so [G : K] \le [G : H]; the left cosets of H in K are left cosets of H in G, so [K : H] \le [G : H]. Both are finite, and Theorem 4 gives p = [G : K]\,[K : H]. As p is prime, one factor is 1. If [K : H] = 1, then H is the only coset of H in K, and K, the union of those cosets, equals H. If [G : K] = 1, then likewise G = K. \square
- Proof. HK = \bigcup_{h \in H} hK, a union of left cosets of K. For h, h' \in H, hK = h'K exactly when h^{-1}h' \in K (Cosets, Lemma 2); since h^{-1}h' \in H always, this means h^{-1}h' \in H \cap K, that is, h(H \cap K) = h'(H \cap K). So the distinct sets hK match the left cosets of H \cap K in H, of which there are |H|/|H \cap K| by Theorem 1. They are disjoint and each has |K| elements, so |HK| = |H|\,|K|/|H \cap K|. \square
- Proof. As in Example 6, g^2 \in H for every g \in G: if g \notin H and g^2 \notin H, then g^2H = G \setminus H = gH, forcing g \in H. If \operatorname{ord}(g) = 2k + 1, then g = g^{2k + 2} = (g^2)^{k + 1}, a power of an element of H, so g \in H. \square
- Proof. Element orders divide 6 (Corollary 2), and none is 6, so each x \ne e has order 2 or 3. Suppose none has order 3. Then x^2 = e for all x, so G is abelian, as in Example 5. Take a \ne b, both not e. Then ab \ne e (else b = a^{-1} = a), ab \ne a, ab \ne b by cancellation, and \{e, a, b, ab\} is closed, as a \cdot ab = b, ab \cdot b = a and (ab)^2 = a^2b^2 = e. It is a subgroup of order 4, but 4 \nmid 6, contradicting Theorem 1. Now suppose none has order 2. Then all five elements other than e have order 3, but by Example 4(b) their number is a multiple of 2. So both orders occur. \square