Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order (number of elements) of every subgroup H of G divides the order of G. Lagrange's theorem is named after Joseph Lagrange.
Contents |
This can be shown using the concept of left cosets of H in G. The left cosets are the equivalence classes of a certain equivalence relation on G and therefore form a partition of G. If we can show that all cosets of H have the same number of elements, then we are done, since H itself is a coset of H. Now, if aH and bH are two left cosets of H, we can define a map f : aH → bH by setting f(x) = ba-1x. This map is bijective because its inverse is given by f −1(y) = ab−1y.
This proof also shows that the quotient of the orders |G| / |H| is equal to the index [G : H] (the number of left cosets of H in G). If we write this statement as
then, interpreted as a statement about cardinal numbers, it remains true even for infinite groups G and H.
A consequence of the theorem is that the order of any element a of a finite group (i.e. the smallest positive integer k with ak = e) divides the order of that group, since the order of a is equal to the order of the cyclic subgroup generated by a. If the group has n elements, it follows
This can be used to prove Fermat's little theorem and its generalization, Euler's theorem. These special cases were known long before the general theorem was proved.
The theorem also shows a group of prime order is cyclic and simple.
Lagrange's theorem raises the question of whether every divisor of the order of a group is the order of a subgroup. This need not hold. Given a finite group G and a divisor d of |G|, there does not necessarily exist a subgroup of G with order d. The smallest example is the alternating group G = A4 which has 12 elements but no subgroup of order 6. Any finite group which has a subgroup with size equal to any (positive) divisor of the size of the group must be solvable, so nonsolvable groups are examples of this phenonenon, although A4 shows that they aren't the only examples. If G is abelian, then there always exists a subgroup of any order dividing the size of G. A partial generalization is given by Cauchy's theorem.
Lagrange did not prove Lagrange's theorem in its general form. What he actually proved was that if a polynomial in n variables has its variables permuted in all n! ways, the number of different polynomials that are obtained is always a factor of n!. (For example if the variables x, y, and z are permuted in all 6 possible ways in the polynomial x + y - z then we get a total of 3 different polynomials: x + y − z, x + z - y, and y + z − x. Note 3 is a factor of 6.) The number of such polynomials is the index in the symmetric group Sn of the subgroup H of permutations which preserve the polynomial. (For the example of x + y − z, the subgroup H in S3 contains the identity and the transposition (xy).) So the size of H divides n!. With the later development of abstract groups, this result of Lagrange on polynomials was recognized to extend to the general theorem about finite groups which now bears his name.