Lagrange's theorem

Theorem

Lagrange's theorem

T-057Home MU-204Threads structure

Statement

Let \(G\) be a finite group and let \(H \subseteq G\) be a subgroup. Then \(|H|\) divides \(|G|\); more precisely, if \(n = [G:H]\) denotes the number of distinct left cosets of \(H\) in \(G\) (the index of \(H\) in \(G\)), then \(|G| = n \cdot |H|\).

Why it matters

Lagrange's theorem is the first structural constraint on finite groups: it converts a question about which subsets can be subgroups into an arithmetic divisibility question. Before even knowing what the subgroups of a group of order \(12\) look like, we know their orders must lie in \(\{1,2,3,4,6,12\}\) — orders \(5\), \(7\), \(8\), \(9\), \(10\), \(11\) are impossible. This single fact underlies Fermat's little theorem, the classification of small groups, the definition of element order, and the entire theory of group actions and the Orbit-Stabiliser theorem.

It is also a paradigm example in mathematics of proving a numerical fact (divisibility of orders) by constructing a combinatorial structure (a partition into equal-sized blocks) rather than by direct counting.

Hypotheses

\(G\) is a group (associativity, identity, inverses hold). Without associativity or inverses the coset argument collapses: in a mere set with a binary operation, "left coset" \(gH\) need not even be well-defined as a bijective translate of \(H\), since translation by \(g\) may fail to be invertible. E.g. in the set \(\{0,1,2\}\) under the operation \(a*b=0\) for all \(a,b\), the "subset" \(\{0\}\) is closed, but translation \(x \mapsto g*x\) is constant, not a bijection, so cosets are not equinumerous with \(H\). \(G\) is finite (\(|G| \lt \infty\)). For infinite \(G\) the statement "\(|H|\) divides \(|G|\)" is not meaningful in the same arithmetic sense (cardinal arithmetic does not have an ordinary divisibility relation compatible with the finite case in the way needed), although the coset-partition argument itself still shows \(|G| = |H|\cdot[G:H]\) as cardinals. The finite hypothesis is what turns the theorem into a genuine divisibility statement about natural numbers. \(H\) is a subgroup, not merely a subset closed under the operation. A sub-semigroup or a subset merely closed under multiplication need not partition \(G\) into equal cosets, because without inverses the relation \(a \sim b \iff a^{-1}b \in H\) used in the proof need not even be symmetric, let alone an equivalence relation. E.g. in \((\mathbb{Z}, +)\), the closed sub-semigroup \(\mathbb{N} = \{0,1,2,\dots\}\) is not a subgroup and the translates \(n + \mathbb{N}\) are not disjoint blocks partitioning \(\mathbb{Z}\) in the required sense (this is a monoid, so finiteness is the natural obstruction, but even restricting to a finite ambient monoid the coset-equivalence argument requires inverses to establish symmetry and transitivity).

Proof

Define a relation on \(G\) by \(a \sim b \iff a^{-1}b \in H\).

This is the standard left-coset relation attached to \(H\); we will show it is an equivalence relation whose classes are exactly the left cosets of \(H\). A

\(\sim\) is reflexive, symmetric and transitive, hence an equivalence relation.

Reflexive: \(a^{-1}a = e \in H\) since \(H\) is a subgroup and contains the identity. Symmetric: if \(a^{-1}b \in H\) then \((a^{-1}b)^{-1} = b^{-1}a \in H\), using closure of \(H\) under inverses. Transitive: if \(a^{-1}b \in H\) and \(b^{-1}c \in H\) then \((a^{-1}b)(b^{-1}c) = a^{-1}c \in H\), using closure of \(H\) under the group operation. All three closure properties are exactly the subgroup axioms. A

The equivalence class of \(a\) under \(\sim\) is \([a] = aH = \{ah : h \in H\}\).

By definition \(b \in [a] \iff a^{-1}b \in H \iff b = ah\) for some \(h \in H\), which is precisely membership in the left coset \(aH\). A

The map \(\varphi_a : H \to aH\), \(\varphi_a(h) = ah\), is a bijection, so \(|aH| = |H|\) for every \(a \in G\).

Injective: if \(ah_1 = ah_2\) then left-multiplying by \(a^{-1}\) (which exists since \(G\) is a group) gives \(h_1 = h_2\). Surjective: every element of \(aH\) is by definition \(ah\) for some \(h \in H\), so it is hit. This uses only that \(G\) is a group (cancellation via inverses); it does not use that \(H\) is finite, only that \(G\) is, to make "\(|H|\)" a finite cardinal. C

The distinct left cosets of \(H\) partition \(G\) into blocks of equal size \(|H|\).

By Step 2, \(\sim\) is an equivalence relation on \(G\); by the standard Equivalence Relation Partition Lemma, its equivalence classes (the left cosets, by Step 3) partition \(G\) into pairwise disjoint, non-empty subsets whose union is \(G\). By Step 4, each such class has exactly \(|H|\) elements. B

Let \(n\) be the number of distinct left cosets (a finite number since \(G\) is finite and the cosets are disjoint non-empty subsets of \(G\)). Then \[ |G| = \sum_{i=1}^{n} |a_iH| = \sum_{i=1}^n |H| = n\,|H|. \]

Since \(G\) is the disjoint union of the \(n\) cosets \(a_1H,\dots,a_nH\) (Step 5), and finite disjoint unions add cardinalities, \(|G|\) equals the sum of the coset sizes; each coset has size \(|H|\) (Step 4). B

Hence \(|H|\) divides \(|G|\), with quotient \(n = [G:H] = |G|/|H|\).

Immediate from \(|G| = n|H|\) in Step 6: \(n\) is a positive integer (a count of cosets) satisfying \(|G| = n \cdot |H|\), which is exactly the definition of \(|H| \mid |G|\). A

Result

H \leq G,\ G \text{ finite} \ \Longrightarrow\ |G| = [G:H]\cdot|H|,\ \text{so } |H| \mid |G|

Reading. Cut a finite group into same-sized pieces (the left cosets of a subgroup); the number of pieces times the piece size gives back the whole group, so the piece size must divide the total.

Scope. Applies to any subgroup \(H\) of any finite group \(G\), including \(H = \{e\}\) and \(H = G\). It also gives, as a byproduct, that the order of any element \(g \in G\) (the size of the cyclic subgroup \(\langle g \rangle\)) divides \(|G|\). It does not assert a converse: not every divisor of \(|G|\) need occur as a subgroup order (see Converse below).

Corollaries & converses

Element orders divide \(|G|\): for \(g \in G\), \(\operatorname{ord}(g) = |\langle g\rangle|\) divides \(|G|\), applying the theorem to \(H = \langle g \rangle\).
\(g^{|G|} = e\) for all \(g \in G\): since \(\operatorname{ord}(g) \mid |G|\), write \(|G| = k\cdot\operatorname{ord}(g)\), so \(g^{|G|} = (g^{\operatorname{ord}(g)})^k = e^k = e\).
Fermat's little theorem is the special case \(G = (\mathbb{Z}/p\mathbb{Z})^\times\) for prime \(p\): \(a^{p-1}\equiv 1 \pmod p\) for \(\gcd(a,p)=1\).
Groups of prime order are cyclic: if \(|G| = p\) is prime, the only divisors of \(p\) are \(1\) and \(p\), so any non-identity element generates all of \(G\).
Converse is FALSE in general: a group of order \(n\) need not have a subgroup of every divisor of \(n\). The smallest counterexample is \(A_4\) (order \(12\)), which has no subgroup of order \(6\), despite \(6 \mid 12\).
Partial converses do hold under extra hypotheses: Cauchy's theorem (a subgroup of prime order \(p\) exists whenever \(p \mid |G|\)), and the Sylow theorems (a subgroup of order \(p^k\) exists whenever \(p^k\) is the full power of prime \(p\) dividing \(|G|\)).

Fails without

Drop finiteness of \(G\): in \(G=(\mathbb{Z},+)\), the subgroup \(H = 2\mathbb{Z}\) has index \(2\) but both \(G\) and \(H\) are countably infinite, so "\(|H|\) divides \(|G|\)" as an ordinary integer-divisibility statement is not even the right kind of claim — the clean numerical corollary (element orders divide group order, \(g^{|G|}=e\)) fails outright, since e.g. \(1 \in \mathbb{Z}\) has infinite order under \(+\).
Drop the subgroup property (only require a submonoid or non-subgroup subset closed under the operation): in the multiplicative monoid \(G=(\mathbb{Z}/6\mathbb{Z}, \times)\) — not a group, since e.g. \(2\) has no inverse — the closed subset \(H=\{0,2,4\}\) has \(|H|=3\), while \(|G|=6\), and \(3\mid 6\) coincidentally holds here, but the coset-partition argument itself breaks: right-translating by a non-invertible element like \(3\) is not injective, so "cosets" of \(H\) are not all size \(|H|\), and in general such closed subsets of finite monoids can have sizes that do not divide the monoid's order at all (e.g. in a monoid formed by a non-invertible idempotent semigroup one can construct closed subsets of size 2 inside a semigroup of order 3).
Assume the converse (every divisor gives a subgroup): \(A_4\), the alternating group on \(4\) letters, has order \(12\), yet possesses no subgroup of order \(6\). One shows this by checking that any subgroup of index \(2\) would be normal and would have to contain every square in \(A_4\); since every element of \(A_4\) is a product of two transpositions (a square of a 3-cycle or itself a square), the subgroup would have to be all of \(A_4\), a contradiction. This shows Lagrange's theorem gives only a necessary, not sufficient, condition on subgroup orders.

Common errors

Believing the converse holds — asserting that a group of order \(n\) must have a subgroup for every divisor of \(n\) (false; see \(A_4\)).
Applying the theorem to infinite groups and concluding numerical facts like "index times order equals order" without checking finiteness makes the statement meaningful.
Confusing "index" \([G:H]\) with "order of \(H\)" — writing \(|G|=|H|^2\) type errors instead of \(|G| = [G:H]\cdot|H|\).
Forgetting that left and right cosets, while generally different as sets, have the same cardinality and same count \(n\); students sometimes think the proof needs \(H\) normal, but normality is irrelevant to Lagrange's theorem itself (it only matters if one wants the coset space \(G/H\) to inherit a group structure).
Trying to prove \(|H|\) divides \(|G|\) by strong induction on \(|G|\) using subgroups of subgroups, missing that the direct coset-counting proof is both simpler and fully general (unnecessary complication, not incorrect, but often leads to gaps at the base case).
Misapplying the corollary \(g^{|G|}=e\) to non-group structures (rings, monoids) where no analogous order argument is available.

Discussion

Lagrange's theorem is named after Joseph-Louis Lagrange, though he proved a special case (concerning permutations of roots of polynomials, in the context of what would become Galois theory) decades before the abstract notion of a group was formalised by Cauchy, Galois, and Cayley in the 19th century. The modern coset-based proof given above is due to the later abstract formulation of group theory; Lagrange's original argument was combinatorial, about counting values a rational function takes under permutation of variables.

The theorem exemplifies a recurring technique in algebra: whenever a set can be partitioned into equal-sized classes by an equivalence relation, the class size divides the set size. The same idea reappears, generalised, as the Orbit-Stabiliser theorem: if a finite group \(G\) acts on a set \(X\) and \(x\in X\), then \(|G| = |\mathrm{Orb}(x)|\cdot|\mathrm{Stab}(x)|\); Lagrange's theorem is the special case of \(G\) acting on itself (or on \(G/H\)) by left multiplication.

A subtler point often glossed over: the proof shows \(|H|\) divides \(|G|\) by exhibiting cosets as equal-sized blocks, but it says nothing about which divisors actually occur, nor does the map \(a \mapsto aH\) endow the coset set \(G/H\) with a group structure unless \(H\) is normal in \(G\) (i.e. \(gHg^{-1}=H\) for all \(g\)). When \(H\) is normal, \(G/H\) becomes the quotient group, and \(|G/H|=[G:H]=|G|/|H|\) is literally the order of a group — a strictly stronger statement than mere divisibility, and this is where the First Isomorphism Theorem enters.

Common misconception: that Lagrange's theorem is "obviously true because subgroups are smaller subsets, and smaller numbers tend to divide bigger ones" — this conflates the correct divisibility conclusion with faulty intuition, since arbitrary closed substructures (submonoids, subsemigroups) of finite algebraic objects do not in general have orders dividing the whole; it is specifically the group axioms (universal invertibility) that force the coset partition into perfectly equal blocks.

Worked examples

Let \(G = S_4\), the symmetric group on \(4\) letters, \(|G| = 24\). Can \(S_4\) have a subgroup of order \(5\)?

Set up: apply Lagrange's theorem, which requires \(|H|\) divides \(|G|=24\) for any subgroup \(H \leq S_4\).

Check divisibility: does \(5 \mid 24\)? \(24 = 4\times 5 + 4\), so \(5 \nmid 24\).

Direct arithmetic check of the necessary condition given by the theorem.

By the contrapositive of Lagrange's theorem, no subgroup of order \(5\) can exist in \(S_4\).

If such \(H\) existed with \(|H|=5\), the theorem would force \(5 \mid 24\), which is false; hence no such \(H\) exists.

S_4 \text{ has no subgroup of order } 5

Let \(G\) be a group with \(|G| = 15\). Show every element \(g \in G\) satisfies \(g^{15} = e\), and show \(G\) has no subgroup of order \(4\).

Set up: apply the corollary \(g^{|G|}=e\) and the divisibility statement from Lagrange's theorem.

For any \(g \in G\), \(\operatorname{ord}(g) = |\langle g \rangle|\) divides \(|G| = 15\) by Lagrange's theorem applied to \(H = \langle g \rangle\).

Cyclic subgroup generated by \(g\) is a genuine subgroup, so Lagrange applies directly.

Since \(\operatorname{ord}(g) \mid 15\), write \(15 = \operatorname{ord}(g)\cdot m\) for integer \(m\); then \(g^{15} = (g^{\operatorname{ord}(g)})^m = e^m = e\).

Uses the definition of element order and the divisibility just established.

The divisors of \(15\) are \(1,3,5,15\); since \(4\) is not among them, \(4 \nmid 15\).

Direct factorisation: \(15 = 3\times 5\).

By Lagrange's theorem, any subgroup \(H \leq G\) has \(|H|\) dividing \(15\); since \(4\) does not divide \(15\), no subgroup of order \(4\) exists.

Contrapositive application of the theorem, as in Example 1.

|G|=15 \implies \forall g\in G,\ g^{15}=e,\ \text{and } G \text{ has no subgroup of order } 4

Problems

Let \(G\) be a group with \(|G| = 21\). List all possible orders of subgroups of \(G\).
Solution
The divisors of \(21 = 3 \times 7\) are \(1, 3, 7, 21\). By Lagrange's theorem, any subgroup of \(G\) must have order in \(\{1,3,7,21\}\); no other order is possible. (Whether subgroups of each of these orders actually exist is a separate question — Cauchy's theorem guarantees subgroups of order \(3\) and \(7\) since these are prime divisors of \(21\).)
Prove that if \(|G| = p\) for a prime \(p\), then \(G\) is cyclic.
Solution
Take any \(g \in G\) with \(g \neq e\) (such \(g\) exists since \(p \geq 2\)). Let \(H = \langle g \rangle\); by Lagrange's theorem \(|H|\) divides \(p\), so \(|H| \in \{1,p\}\). Since \(g \neq e\), \(H \neq \{e\}\), so \(|H| \neq 1\), forcing \(|H| = p = |G|\). As \(H \subseteq G\) and \(|H|=|G|\) with \(G\) finite, \(H = G\). Hence \(G = \langle g \rangle\) is cyclic.
Give an explicit example showing the converse of Lagrange's theorem is false (a group order \(n\) and a divisor \(d\) of \(n\) such that no subgroup of order \(d\) exists), and briefly justify the non-existence.
Solution
Take \(G = A_4\), \(|G| = 12\), and \(d = 6\); \(6 \mid 12\) but \(A_4\) has no subgroup of order \(6\). Justification sketch: a subgroup \(H\) of order \(6\) would have index \(2\) in \(A_4\), and any index-\(2\) subgroup is automatically normal (since its two cosets, left and right, must coincide as the complement of \(H\)). A normal subgroup of index \(2\) contains every square \(g^2\) for \(g \in G\) (because \(G/H\) has order \(2\), so \((gH)^2 = H\), i.e. \(g^2 \in H\), for every \(g\)). But every element of \(A_4\) is a square: the identity, the 3-cycles (each 3-cycle is the square of its inverse, also a 3-cycle), and each product of two disjoint transpositions (which squares to the identity but is also itself the square of a 3-cycle acting appropriately) — a direct check shows all \(12\) elements arise as squares, forcing \(H = A_4\), contradicting \(|H|=6\).
Let \(G\) be a finite group and \(H, K\) two subgroups with \(H \leq K \leq G\). Prove the multiplicative tower formula \([G:H] = [G:K]\cdot[K:H]\), using Lagrange's theorem.
Solution
By Lagrange's theorem applied three times: \(|G| = [G:H]\cdot|H|\), \(|G| = [G:K]\cdot|K|\), and \(|K| = [K:H]\cdot|H|\) (the last since \(H \leq K\) and \(K\) is itself a finite group). Substitute the third into the second: \(|G| = [G:K]\cdot([K:H]\cdot|H|) = ([G:K]\cdot[K:H])\cdot|H|\). Comparing with \(|G| = [G:H]\cdot|H|\) and cancelling the positive integer \(|H|\) (valid since \(|H| \neq 0\)) gives \([G:H] = [G:K]\cdot[K:H]\).
A group \(G\) has order \(30\). Suppose \(G\) has a subgroup \(H\) of order \(15\). Prove \(H\) is normal in \(G\) (you may use, without proof, that a subgroup of index \(2\) is always normal).
Solution
By Lagrange's theorem, \(|G| = [G:H]\cdot |H|\), so \(30 = [G:H]\cdot 15\), giving \([G:H] = 2\). Since \(H\) has index \(2\) in \(G\), by the cited fact \(H\) is normal in \(G\). (Sketch of why index 2 implies normal, for completeness: the two left cosets are \(H\) and \(G\setminus H\); the two right cosets are also \(H\) and \(G\setminus H\), since both partition \(G\) into \(H\) and its complement. As left and right cosets of \(H\) coincide for every element, \(gH = Hg\) for all \(g \in G\), which is the definition of normality.)