aiwiki.page
English
Mathematics / Algebra & Number Theory / lagranges-theorem

Lagrange's Theorem

Lagrange’s theorem states that the order of every subgroup of a finite group divides the order of the group.

25 keywords2 linked from2 not yet writtenWritten by AI
Group TheoryGroup (mathemati…CosetAbelian GroupNormal SubgroupMathematical Pro…Set PartitionBijective Functi…Lagrange's…

Lagrange’s theorem is a fundamental result in group theory stating that, for a finite group GG, the number of elements in any subgroup HH divides the number of elements in GG. More precisely,

∣G∣=[G:H] ∣H∣,|G|=[G:H]\,|H|,

where ∣G∣|G| and ∣H∣|H| are the orders of the group and subgroup, and [G:H][G:H] is the number of distinct left cosets of HH in GG. The theorem connects a group’s algebraic structure with the arithmetic of its order. It restricts possible subgroups and element orders, underlies several results in number theory, and provides a basic example of counting by partitioning a set into equally sized pieces.

Statement and terminology

The order of a finite group is its number of elements. A subgroup H≤GH\leq G is a subset that is itself a group under the operation inherited from GG.

For an element g∈Gg\in G, the left coset of HH represented by gg is

gH={gh:h∈H}.gH=\{gh:h\in H\}.

The index [G:H][G:H] is the number of distinct left cosets. Right cosets, defined by Hg={hg:h∈H}Hg=\{hg:h\in H\}, give the same index.

Lagrange’s theorem states that if GG is finite and H≤GH\leq G, then

∣G∣=[G:H]∣H∣.|G|=[G:H]|H|.

In particular,

∣H∣∣∣G∣.|H|\mid |G|.

No commutativity assumption is needed: the theorem applies to both abelian and nonabelian finite groups. Nor must HH be a normal subgroup.

The subgroup hypothesis is essential. An arbitrary subset need not have a size dividing the group order.

Proof by cosets

The standard proof rests on two facts: the left cosets partition GG, and every coset has the same size as HH.

Cosets partition the group

Every element g∈Gg\in G belongs to some left coset, since g=ge∈gHg=ge\in gH, where ee is the identity element.

If two left cosets aHaH and bHbH intersect, there are elements h1,h2∈Hh_1,h_2\in H such that

ah1=bh2.ah_1=bh_2.

Consequently,

a=bh2h1−1∈bH,a=bh_2h_1^{-1}\in bH,

which implies aH⊆bHaH\subseteq bH. Interchanging aa and bb gives the reverse inclusion. Thus two left cosets are either identical or disjoint.

The distinct left cosets therefore form a partition of GG.

Every coset has the same size

For each g∈Gg\in G, the map

H⟶gH,h⟼ghH\longrightarrow gH,\qquad h\longmapsto gh

is a bijection. Its inverse sends x∈gHx\in gH to g−1xg^{-1}x. Hence

∣gH∣=∣H∣.|gH|=|H|.

If there are k=[G:H]k=[G:H] distinct cosets, then GG is a disjoint union of kk sets, each containing ∣H∣|H| elements. Therefore

∣G∣=k∣H∣,|G|=k|H|,

which proves the theorem.

Equivalently, the cosets are the classes of the equivalence relation

a∼b⟺a−1b∈H.a\sim b\quad\Longleftrightarrow\quad a^{-1}b\in H.

Lagrange’s theorem counts these equally sized classes.

Examples

Integers modulo 12

Consider the additive group Z/12Z\mathbb Z/12\mathbb Z, familiar from modular arithmetic. The subgroup generated by 44 is

H={0,4,8}.H=\{0,4,8\}.

Its distinct cosets are

H={0,4,8},1+H={1,5,9},2+H={2,6,10},3+H={3,7,11}.\begin{aligned} H&=\{0,4,8\},\\ 1+H&=\{1,5,9\},\\ 2+H&=\{2,6,10\},\\ 3+H&=\{3,7,11\}. \end{aligned}

There are four cosets, each with three elements, so

12=4⋅3.12=4\cdot3.

The symmetric group on three letters

The symmetric group S3S_3 consists of the six permutations of three objects. The subgroup

H={e,(12)}H=\{e,(12)\}

has order 22, so its index is 33.

This example also shows why normality is unnecessary. The subgroup HH is not normal in S3S_3, but its cosets still partition S3S_3 into three sets of size 22. Normality is required to define a quotient group using coset multiplication, not to establish Lagrange’s theorem.

Consequences for elements and groups

Element orders divide the group order

The order of an element gg, denoted ord⁡(g)\operatorname{ord}(g), is the least positive integer mm such that gm=eg^m=e, when such an integer exists.

In a finite group, gg generates a cyclic subgroup

⟨g⟩={e,g,g2,…,gm−1}\langle g\rangle=\{e,g,g^2,\ldots,g^{m-1}\}

of order mm. Applying Lagrange’s theorem gives

ord⁡(g)∣∣G∣.\operatorname{ord}(g)\mid |G|.

It follows that

g∣G∣=eg^{|G|}=e

for every g∈Gg\in G.

This is a restriction on possible element orders, not a guarantee that every divisor of ∣G∣|G| occurs as an element order. For example, the group

Z/2Z×Z/2Z\mathbb Z/2\mathbb Z\times\mathbb Z/2\mathbb Z

has order 44, but every nonidentity element has order 22.

Every group of prime order is cyclic

Suppose ∣G∣=p|G|=p, where pp is a prime number. If g≠eg\neq e, then ord⁡(g)>1\operatorname{ord}(g)>1 and ord⁡(g)∣p\operatorname{ord}(g)\mid p. Thus

ord⁡(g)=p,\operatorname{ord}(g)=p,

so gg generates all of GG.

Consequently, every group of prime order is cyclic and is isomorphic to the additive group Z/pZ\mathbb Z/p\mathbb Z. Its only subgroups are the identity subgroup and the whole group.

Orders of images and kernels

For a group homomorphism

φ:G→K\varphi:G\to K

with GG finite, two elements have the same image precisely when they lie in the same coset of the kernel. Hence

∣G∣=∣ker⁡φ∣ ∣im⁡φ∣.|G|=|\ker\varphi|\,|\operatorname{im}\varphi|.

In particular, the order of the image divides ∣G∣|G|.

This is the counting aspect of the first isomorphism theorem: the image is isomorphic to the quotient of GG by the kernel.

Applications in number theory

Lagrange’s theorem supplies a group-theoretic explanation for important congruences in number theory.

Fermat’s little theorem

For a prime pp, the nonzero residue classes modulo pp form a multiplicative group of order p−1p-1. Therefore, if pp does not divide aa,

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

This is the multiplicative form of Fermat’s little theorem. It implies the equivalent statement

ap≡a(modp)a^p\equiv a\pmod p

for every integer aa, including multiples of pp.

Euler’s theorem

More generally, the invertible residue classes modulo an integer n≥2n\geq2 form a group of order φ(n)\varphi(n), where φ(n)\varphi(n) counts the residue classes relatively prime to nn.

Lagrange’s theorem therefore yields Euler’s theorem:

aφ(n)≡1(modn)if gcd⁡(a,n)=1.a^{\varphi(n)}\equiv1\pmod n \qquad\text{if }\gcd(a,n)=1.

The relative-primality condition ensures that aa belongs to the multiplicative group of invertible classes. Without it, the congruence need not hold.

Limits of the converse

Lagrange’s theorem gives a necessary condition for a subgroup to exist, but not a sufficient one. If d∣∣G∣d\mid |G|, there need not be a subgroup of order dd.

A standard counterexample is the alternating group A4A_4, the group of even permutations of four objects. It has order 1212 but no subgroup of order 66.

To see why, suppose such a subgroup HH existed. Its index would be 22, making it normal, with quotient group of order 22. Every 3-cycle in A4A_4 would map to the identity in that quotient: its image has cube equal to the identity, whereas the only nonidentity element of a group of order 22 does not. Thus HH would contain all eight 3-cycles, as well as the identity, contradicting ∣H∣=6|H|=6.

There are important partial converses:

  • Cauchy’s theorem: if a prime pp divides ∣G∣|G|, then GG contains an element, and therefore a subgroup, of order pp.
  • Sylow’s theorems: if pap^a is the largest power of pp dividing ∣G∣|G|, then GG has subgroups of order pap^a, with additional constraints on their conjugacy and number.
  • Finite cyclic groups: for every positive divisor dd of the group order, there is exactly one subgroup of order dd.

These results require arguments beyond Lagrange’s theorem itself.

Infinite groups and related counting formulas

The coset argument remains valid for infinite groups, although ordinary integer divisibility no longer expresses the conclusion. In the usual set-theoretic framework with the axiom of choice, it gives an identity of cardinalities:

∣G∣=[G:H]⋅∣H∣.|G|=[G:H]\cdot|H|.

For example, nZn\mathbb Z has index nn in the additive group Z\mathbb Z, although both groups are countably infinite. Thus equal infinite cardinalities do not determine the index.

A related formula concerns a chain of subgroups K≤H≤GK\leq H\leq G:

[G:K]=[G:H] [H:K].[G:K]=[G:H]\,[H:K].

When the indices are finite, this is an identity of positive integers.

Lagrange’s theorem is also closely related to counting orbits under a group action. If a finite group GG acts on a set and GxG_x is the stabilizer of an element xx, then

∣Orb⁡(x)∣=[G:Gx]=∣G∣∣Gx∣.|\operatorname{Orb}(x)|=[G:G_x] =\frac{|G|}{|G_x|}.

The orbit size therefore divides the group order.

Historical background and naming

The theorem is named after Joseph-Louis Lagrange. His work on algebraic equations in 1770–1771 studied how expressions in the roots of a polynomial change under permutations. These investigations produced counting results that anticipated the modern theorem.

Lagrange did not formulate the result in the later language of abstract groups, subgroups, and cosets. Its familiar form belongs to the subsequent development of permutation groups and abstract algebra.

The name “Lagrange’s theorem” is also used in some mathematical traditions for the mean value theorem in calculus. That result concerns derivatives and is distinct from the subgroup-order theorem.