Lagrange's theorem for groups

Statement

Let \(G\) be a finite group and let \(H \le G\) be a subgroup. Then the left cosets of \(H\) partition \(G\) into pairwise disjoint blocks, each of which has exactly \(|H|\) elements; consequently \(|G| = [G:H]\cdot|H|\), where the index \([G:H]\) is the number of distinct left cosets, and in particular \(|H|\) divides \(|G|\).

Why it matters

Lagrange's theorem is the first genuine constraint that finite group theory imposes on itself, and it converts a hard structural question — which subsets of \(G\) can carry the group operation? — into an arithmetic one that a child can check. Before knowing anything at all about a group of order \(20\), we know its subgroups have order \(1, 2, 4, 5, 10\) or \(20\), and that orders \(3, 6, 7, 8, 9\) are flatly impossible. Nothing about the multiplication table was used: only that the table has no repeated entry in any row.

Every counting theorem downstream is either an application or a refinement of it. The order of an element divides the order of the group, hence \(g^{|G|} = e\); specialised to \(G = (\mathbb{Z}/n\mathbb{Z})^{\times}\) that identity is Euler's theorem, and for prime \(n\) it is Fermat's little theorem — two of the load-bearing results of elementary number theory, proved in one line from a statement about cosets. The orbit–stabiliser theorem, the class equation, the Sylow theorems and the whole theory of group actions are built on the same partition-into-equal-blocks idea, applied to a set the group acts on rather than to the group itself.

It is equally important for what it does not say. The converse is false, and the precise extent to which it fails — Cauchy's theorem rescues prime divisors, Sylow's theorems rescue maximal prime powers, Hall's theorem rescues coprime divisors in soluble groups — is the organising question of finite group theory.

Hypotheses

Proof

We construct the partition rather than count directly. Fix \(H \le G\) and define a relation on \(G\); the strategy is to show it is an equivalence relation, identify its classes as the left cosets, prove all classes have the same size, and then add up.

Result

Corollaries & converses

• Element orders divide the group order. For \(g \in G\), \(\operatorname{ord}(g) = |\langle g \rangle|\) divides \(|G|\) — apply the theorem to the cyclic subgroup \(H = \langle g \rangle\).
• The exponent bound. \(g^{|G|} = e\) for every \(g \in G\): write \(|G| = k\cdot\operatorname{ord}(g)\), then \(g^{|G|} = \big(g^{\operatorname{ord}(g)}\big)^{k} = e^{k} = e\).
• Euler's theorem. Taking \(G = (\mathbb{Z}/n\mathbb{Z})^{\times}\), of order \(\varphi(n)\), gives \(a^{\varphi(n)} \equiv 1 \pmod n\) whenever \(\gcd(a,n) = 1\); for \(n = p\) prime this is Fermat's little theorem \(a^{p-1} \equiv 1 \pmod p\).
• Groups of prime order are cyclic and simple. If \(|G| = p\) is prime the only possible subgroup orders are \(1\) and \(p\), so any \(g \ne e\) generates \(G\), and \(G\) has no proper non-trivial subgroup at all — normal or otherwise.
• Multiplicativity of the index (the tower law). If \(K \le H \le G\) with \(G\) finite then \([G:K] = [G:H]\,[H:K]\), immediately from \(|G|/|K| = (|G|/|H|)(|H|/|K|)\). It also holds for infinite \(G\) whenever the indices are finite, proved by showing \(\{a_ib_j K\}\) is a transversal.
• Intersections. For \(H, K \le G\) finite, \(|H \cap K|\) divides \(\gcd(|H|,|K|)\), so subgroups of coprime order meet trivially; and \(|HK| = |H|\,|K| / |H \cap K|\) for the (not necessarily subgroup) product set \(HK\).
• Index two forces normality. If \([G:H] = 2\) then \(H \trianglelefteq G\), because the two left cosets are \(H\) and \(G \setminus H\), as are the two right cosets, so \(gH = Hg\) for every \(g\).
• The converse is false. A divisor of \(|G|\) need not be the order of any subgroup: \(A_4\) has order \(12\) but no subgroup of order \(6\). This is the smallest counterexample.
• The converse does hold for cyclic groups. If \(G = \langle g \rangle\) has order \(n\) then for every \(d \mid n\) the subgroup \(\langle g^{n/d} \rangle\) has order exactly \(d\), and it is the unique subgroup of that order.
• Partial converses in general. Cauchy's theorem returns a subgroup of order \(p\) for every prime \(p \mid |G|\); Sylow's first theorem returns one of order \(p^{k}\) for every prime power \(p^{k} \mid |G|\); Hall's theorem returns one of order \(d\) for every \(d\) with \(\gcd(d, |G|/d) = 1\), but only when \(G\) is soluble.

Fails without

Common errors

• “Every divisor of \(|G|\) is the order of some subgroup.” False; \(A_4\) has order \(12\) and no subgroup of order \(6\). The theorem is one-directional, and reversing it is the single most common misuse.
• “The proof needs \(H\) normal.” It does not. Normality is what makes the set of cosets into a group; the counting argument only needs them to be a partition into equal blocks, which holds for every subgroup.
• “Left and right cosets are the same sets.” They coincide as families exactly when \(H\) is normal. In \(D_4\) with \(K = \langle s \rangle\), \(rK = \{r, sr^{3}\}\) while \(Kr = \{r, sr\}\), so \(rK \ne Kr\) — but there are four of each, which is all the theorem claims.
• “\(|G| = |H|^{2}\)” and similar index/order confusions. The identity is \(|G| = [G:H]\cdot|H|\); the index is a count of cosets, not the order of a subgroup (though it is the order of \(G/H\) when \(H\) is normal).
• “A finite subset closed under the operation need not be a subgroup, so Lagrange does not apply.” Backwards: in a finite group a non-empty subset closed under the operation is automatically a subgroup, because \(x, x^{2}, x^{3}, \ldots\) must repeat, giving \(x^{m} = x^{m+k}\) and hence \(x^{k} = e\) and \(x^{-1} = x^{k-1}\). The closure-only counterexamples above live in monoids, not groups.
• Applying \(g^{|G|} = e\) outside groups. In the ring \(\mathbb{Z}/6\mathbb{Z}\) the element \(2\) satisfies no such identity under multiplication (\(2^{k} \in \{2,4\}\) forever, never \(1\)); the corollary applies to the unit group \((\mathbb{Z}/6\mathbb{Z})^{\times} = \{1,5\}\), of order \(2\), not to the whole ring.
• Reading \(a \sim b \iff a^{-1}b \in H\) as \(ab^{-1} \in H\) mid-proof. Both are equivalence relations, but the first has left cosets \(aH\) as classes and the second has right cosets \(Ha\); mixing them produces a “proof” whose classes are not the sets being counted.

Discussion

The result carries Lagrange's name for a reason that has almost nothing to do with its modern statement. In his memoirs on the algebraic solution of equations (1770–71) Lagrange studied how many distinct values a rational function of \(n\) variables can take as the variables are permuted, and showed that this number divides \(n!\). In today's language he was computing the index of the stabiliser of a function inside the symmetric group \(S_n\) — an instance of the orbit–stabiliser theorem — but no abstract group existed to state it in. The general theorem for abstract finite groups had to wait for the group concept itself to be isolated, through Galois, Cauchy, Jordan and Cayley over the following century.

The technique is more valuable than the theorem. Any equivalence relation on a finite set whose classes can be shown to be equinumerous immediately gives a divisibility statement, and the trick of proving equinumerosity by exhibiting an explicit bijection — here, left translation — recurs everywhere in algebra. Run the same argument with \(G\) acting on a set \(X\) instead of on itself and the classes are orbits, the block-size argument becomes \(|\operatorname{Orb}(x)| = [G : \operatorname{Stab}(x)]\), and Lagrange's theorem is recovered as the case \(X = G/H\). Run it with the conjugation action and the class equation appears, from which Cauchy's theorem and the Sylow theorems follow.

The most instructive thing about the theorem is the exact shape of its failure to reverse. Lagrange's condition is necessary and never sufficient, and the search for the strongest true converse organised a century of finite group theory: Cauchy (1845) for prime divisors, Sylow (1872) for maximal prime powers, Hall (1928) for coprime divisors of soluble groups — each buying back a fragment of the false converse at the cost of a hypothesis. The \(A_4\) counterexample is not an accident either: a subgroup of index \(2\) is normal with quotient \(\mathbb{Z}/2\mathbb{Z}\), so it would give a surjection \(A_4 \to \mathbb{Z}/2\mathbb{Z}\); but every such surjection factors through the abelianisation, and \(A_4\) has commutator subgroup \(V_4 = \{e,(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\}\) with \(A_4/V_4 \cong \mathbb{Z}/3\mathbb{Z}\), a group of odd order that admits no surjection onto \(\mathbb{Z}/2\mathbb{Z}\) at all. The missing subgroup of order \(6\) is visible in the abelianisation, one level up.

For infinite groups the correct generalisation is about indices rather than orders. The coset decomposition \(G = \bigsqcup_i a_iH\) is valid for any group, so \([G:H]\) is always defined as a cardinal, the tower law \([G:K] = [G:H][H:K]\) holds whenever the right-hand factors are finite, and Poincaré's lemma — \([G : H\cap K] \le [G:H]\,[G:K]\), via the injection \(g(H \cap K) \mapsto (gH, gK)\) — shows finite-index subgroups are closed under finite intersection. What is lost is the passage from index to order: an infinite group can have a proper subgroup of the same cardinality as itself, so that the ratio of orders is \(1\) while the index is not (\(2\mathbb{Z} \le \mathbb{Z}\) has index \(2\) yet \(|2\mathbb{Z}| = |\mathbb{Z}|\)), and the divisibility conclusion has no infinite analogue. The subgroup-index language survives; the subgroup-order language does not.

Common misconceptions. The theorem is often absorbed as “subgroups are small, and small numbers divide big ones”, which is not an argument at all — \(3\) is smaller than \(4\) and does not divide it, and the monoid \(N = \{0,1,2\} \le (\mathbb{Z}/4\mathbb{Z},\times)\) above realises exactly that failure inside an algebraic structure that satisfies every group axiom except invertibility. A second misconception is that Lagrange's theorem is about numbers. It is about a partition; the divisibility is a corollary of the partition, and it is the partition — \(G\) as a disjoint union of translates of \(H\) — that generalises to quotient groups, fibre bundles of covering spaces, and the index theory of lattices in Lie groups.

Worked examples

Example 1. Compute \(7^{2026} \bmod 15\) using nothing but Lagrange's theorem and one multiplication table entry.

Example 2. Let \(D_4\) be the symmetry group of a square: \(D_4 = \{\,e, r, r^{2}, r^{3}, s, sr, sr^{2}, sr^{3}\,\}\) with \(r\) the rotation by \(90^{\circ}\), \(s\) a reflection, and relations \(r^{4} = s^{2} = e\), \(srs^{-1} = r^{-1}\). Find the possible subgroup orders, and exhibit the coset partitions for the rotation subgroup and for a reflection subgroup.

Problems

1. A group \(G\) has \(|G| = 77\). List the possible orders of its elements, show \(g^{77} = e\) for every \(g \in G\), and decide whether \(G\) can have a subgroup of order \(7\), of order \(11\), or of order \(14\).
   Solution

   By Lagrange applied to \(\langle g \rangle\), \(\operatorname{ord}(g)\) divides \(|G| = 77 = 7 \cdot 11\), so \(\operatorname{ord}(g) \in \{1, 7, 11, 77\}\); only \(g = e\) has order \(1\).

   Writing \(77 = k\cdot\operatorname{ord}(g)\) for a positive integer \(k\), we get \(g^{77} = \big(g^{\operatorname{ord}(g)}\big)^{k} = e^{k} = e\) for every \(g\).

   Subgroup orders must also divide \(77\), so \(14\) is impossible: \(77 = 5\cdot 14 + 7\), i.e. \(14 \nmid 77\). Orders \(7\) and \(11\) are permitted by Lagrange, and in fact both occur — Cauchy's theorem gives an element of order \(7\) and one of order \(11\) since both primes divide \(77\), and these generate subgroups of those orders. (Lagrange alone would only say “not forbidden”; producing the subgroups needs the partial converse.)

2. Compute \(3^{1000} \bmod 14\).
   Solution

   Work in \(G = (\mathbb{Z}/14\mathbb{Z})^{\times}\). Since \(14 = 2 \cdot 7\), \(|G| = \varphi(14) = \varphi(2)\varphi(7) = 1 \cdot 6 = 6\), and \(\gcd(3,14) = 1\) so \(3 \in G\). By Lagrange, \(\operatorname{ord}(3)\) divides \(6\), hence lies in \(\{1,2,3,6\}\).

   Test the divisors: \(3^{1} = 3 \ne 1\); \(3^{2} = 9 \ne 1\); \(3^{3} = 27 = 14 + 13 \equiv 13 \equiv -1 \pmod{14}\), so not \(1\). Therefore \(\operatorname{ord}(3) = 6\), and indeed \(3^{6} \equiv (-1)^{2} = 1\).

   Reduce the exponent modulo \(6\): \(1000 = 6\cdot 166 + 4\), since \(6 \cdot 166 = 996\). Hence \(3^{1000} = (3^{6})^{166}\cdot 3^{4} \equiv 3^{4} \pmod{14}\).

   Finally \(3^{4} = 81 = 5\cdot 14 + 11 \equiv 11\). So \(3^{1000} \equiv 11 \pmod{14}\). (Sanity check by the other route: \(3^{4} = 3^{3}\cdot 3 \equiv (-1)\cdot 3 = -3 \equiv 11\).)

3. Let \(G\) be a group (not necessarily finite) and \(H \le G\) with \([G:H] = 2\). Prove \(H \trianglelefteq G\), and deduce that \(G/H \cong \mathbb{Z}/2\mathbb{Z}\).
   Solution

   There are exactly two left cosets. One of them is \(H = eH\), and since the left cosets partition \(G\), the other must be \(G \setminus H\). The same argument applied to right cosets gives right cosets \(H\) and \(G \setminus H\).

   Now take any \(g \in G\). If \(g \in H\) then \(gH = H = Hg\), since \(H\) absorbs its own elements on either side. If \(g \notin H\) then \(gH \ne H\) (else \(g = g e \in H\)), so \(gH\) must be the other left coset, \(gH = G \setminus H\); identically \(Hg \ne H\) forces \(Hg = G\setminus H\). Either way \(gH = Hg\) for all \(g\), which is the definition of normality: \(gHg^{-1} = H\).

   Hence \(G/H\) is a group, and it has \([G:H] = 2\) elements. Any group of order \(2\) is cyclic (its non-identity element must have order dividing \(2\) and not equal to \(1\)), so \(G/H \cong \mathbb{Z}/2\mathbb{Z}\).

   Note that finiteness of \(G\) was never used — only finiteness of the index. Example: \(2\mathbb{Z} \trianglelefteq \mathbb{Z}\) with quotient \(\mathbb{Z}/2\mathbb{Z}\), and \(A_n \trianglelefteq S_n\) for \(n \ge 2\).

4. Show that \(A_4\), the alternating group on four letters, has no subgroup of order \(6\), even though \(6\) divides \(|A_4| = 12\). Identify precisely which of Lagrange's conclusions this does and does not contradict.
   Solution

   First the element census. \(|A_4| = 4!/2 = 12\), consisting of the identity, the eight \(3\)-cycles such as \((1\,2\,3)\), and the three double transpositions \((1\,2)(3\,4)\), \((1\,3)(2\,4)\), \((1\,4)(2\,3)\). Total: \(1 + 8 + 3 = 12\).

   Suppose \(H \le A_4\) with \(|H| = 6\). Then \([A_4 : H] = 12/6 = 2\), so by Problem 3 \(H\) is normal and \(A_4/H\) has order \(2\). Let \(\pi : A_4 \to A_4/H\) be the quotient map. For any \(\sigma \in A_4\), the element \(\pi(\sigma)\) lies in a group of order \(2\), so \(\pi(\sigma)^{2}\) is the identity, i.e. \(\pi(\sigma^{2}) = e\), i.e. \(\sigma^{2} \in H\) for every \(\sigma \in A_4\).

   Now let \(\sigma\) be any \(3\)-cycle. Then \(\sigma^{3} = e\), so \(\sigma = \sigma^{4} = (\sigma^{2})^{2}\), which is the square of the element \(\sigma^{2} \in A_4\). By the previous paragraph every square lies in \(H\), so \(\sigma \in H\). This holds for all eight \(3\)-cycles, giving \(|H| \ge 8 + 1 = 9\) (the eight \(3\)-cycles plus the identity), contradicting \(|H| = 6\). Hence no such \(H\) exists.

   What this contradicts. Nothing in Lagrange's theorem. Lagrange asserts only the implication “\(H \le G \Rightarrow |H| \mid |G|\)”; here there is no \(H\), so the implication is vacuously respected. What fails is the converse, “\(d \mid |G| \Rightarrow\) some \(H\) has \(|H| = d\)”, which was never a theorem. \(A_4\) is the smallest group witnessing this: every group of order less than \(12\) does have a subgroup of every divisor order.

5. Prove the product formula \(|HK| = \dfrac{|H|\,|K|}{|H \cap K|}\) for subgroups \(H, K\) of a finite group \(G\), where \(HK = \{hk : h \in H,\ k \in K\}\) is a subset of \(G\) (not necessarily a subgroup). Then let \(|G| = 105\) and suppose \(H, K \le G\) with \(|H| = 21\) and \(|K| = 35\); determine \(|H \cap K|\) exactly.
   Solution

   The formula. Note first that \(D := H \cap K\) is a subgroup of \(K\): it is non-empty (\(e \in D\)) and closed under products and inverses because \(H\) and \(K\) both are. Consider the map \(\mu : H \times K \to HK\), \(\mu(h,k) = hk\), which is surjective by definition of \(HK\). We count its fibres. Fix \(h_0 k_0 \in HK\). Then \(hk = h_0k_0\) if and only if \(h_0^{-1}h = k_0k^{-1} =: d\); the left side lies in \(H\) and the right side in \(K\), so \(d \in D\), and conversely each \(d \in D\) gives the pair \((h,k) = (h_0 d,\ d^{-1}k_0)\), which lies in \(H \times K\) and satisfies \(hk = h_0 d d^{-1} k_0 = h_0k_0\). Distinct \(d\) give distinct pairs. So every fibre of \(\mu\) has exactly \(|D|\) elements, and therefore \(|H|\,|K| = |H \times K| = |HK|\cdot|D|\), which rearranges to \(|HK| = |H||K|/|H\cap K|\).

   The numerical case. Take \(|G| = 105 = 3 \cdot 5 \cdot 7\), \(|H| = 21 = 3\cdot 7\), \(|K| = 35 = 5 \cdot 7\). Since \(H \cap K\) is a subgroup of both \(H\) and \(K\), Lagrange gives \(|H\cap K| \mid 21\) and \(|H \cap K| \mid 35\), hence \(|H \cap K| \mid \gcd(21,35) = 7\), so \(|H\cap K| \in \{1, 7\}\).

   Now use the formula together with \(HK \subseteq G\), so \(|HK| \le |G| = 105\):

   \[ |HK| = \frac{21 \cdot 35}{|H\cap K|} = \frac{735}{|H \cap K|} \le 105 \quad\Longrightarrow\quad |H\cap K| \ge \frac{735}{105} = 7. \]

   Combining, \(|H \cap K| = 7\) exactly, and then \(|HK| = 735/7 = 105 = |G|\), so in fact \(HK = G\) as a set. Note that \(|H\cap K| = 1\) is excluded purely by counting: it would force \(|HK| = 735 \gt 105\) elements inside a group with only \(105\).