Template:Short description {{#invoke:other uses|otheruses}} Template:Group theory sidebar
In the mathematical field of group theory, Lagrange's theorem states that if H is a subgroup of any finite group Template:Mvar, then <math>|H|</math> is a divisor of <math>|G|</math>, i.e. the order (number of elements) of every subgroup H divides the order of group G.
The theorem is named after Joseph-Louis Lagrange. The following variant states that for a subgroup <math>H</math> of a finite group <math>G</math>, not only is <math>|G|/|H|</math> an integer, but its value is the index <math>[G:H]</math>, defined as the number of left cosets of <math>H</math> in <math>G</math>. Template:Math theorem This variant holds even if <math>G</math> is infinite, provided that <math>|G|</math>, <math>|H|</math>, and <math>[G:H]</math> are interpreted as cardinal numbers.
ProofEdit
The left cosets of Template:Mvar in Template:Mvar are the equivalence classes of a certain equivalence relation on Template:Mvar: specifically, call Template:Mvar and Template:Mvar in Template:Mvar equivalent if there exists Template:Mvar in Template:Mvar such that Template:Math. Therefore, the set of left cosets forms a partition of Template:Mvar. Each left coset Template:Math has the same cardinality as Template:Mvar because <math>x \mapsto ax</math> defines a bijection <math>H \to aH</math> (the inverse is <math>y \mapsto a^{-1}y</math>). The number of left cosets is the index Template:Math. By the previous three sentences,
- <math>\left|G\right| = \left[G : H\right] \cdot \left|H\right|.</math>
ExtensionEdit
Lagrange's theorem can be extended to the equation of indexes between three subgroups of Template:Mvar.<ref>Template:Mathworld</ref> Template:Math theorem Template:Math proof If we take Template:Math (Template:Mvar is the identity element of Template:Mvar), then Template:Math and Template:Math. Therefore, we can recover the original equation Template:Math.
ApplicationsEdit
A consequence of the theorem is that the order of any element Template:Mvar of a finite group (i.e. the smallest positive integer number Template:Mvar with Template:Math, where Template:Mvar is the identity element of the group) divides the order of that group, since the order of Template:Mvar is equal to the order of the cyclic subgroup generated by Template:Mvar. If the group has Template:Mvar elements, it follows
- <math>\displaystyle a^n = e\mbox{.}</math>
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 that any group of prime order is cyclic and simple, since the subgroup generated by any non-identity element must be the whole group itself.
Lagrange's theorem can also be used to show that there are infinitely many primes: suppose there were a largest prime <math>p</math>. Any prime divisor <math>q</math> of the Mersenne number <math>2^p -1</math> satisfies <math>2^p \equiv 1 \pmod {q}</math> (see modular arithmetic), meaning that the order of <math>2</math> in the multiplicative group <math>(\mathbb Z/q\mathbb Z)^*</math> is <math>p</math>. By Lagrange's theorem, the order of <math>2</math> must divide the order of <math>(\mathbb Z/q\mathbb Z)^*</math>, which is <math>q-1</math>. So <math>p</math> divides <math>q-1</math>, giving <math> p < q </math>, contradicting the assumption that <math>p</math> is the largest prime.<ref>Template:Citation</ref>
Existence of subgroups of given orderEdit
Lagrange's theorem raises the converse question as to whether every divisor of the order of a group is the order of some subgroup. This does not hold in general: 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 A4 (the alternating group of degree 4), which has 12 elements but no subgroup of order 6.
A "Converse of Lagrange's Theorem" (CLT) group is a finite group with the property that for every divisor of the order of the group, there is a subgroup of that order. It is known that a CLT group must be solvable and that every supersolvable group is a CLT group. However, there exist solvable groups that are not CLT (for example, A4) and CLT groups that are not supersolvable (for example, S4, the symmetric group of degree 4).
There are partial converses to Lagrange's theorem. For general groups, Cauchy's theorem guarantees the existence of an element, and hence of a cyclic subgroup, of order any prime dividing the group order. Sylow's theorem extends this to the existence of a subgroup of order equal to the maximal power of any prime dividing the group order. For solvable groups, Hall's theorems assert the existence of a subgroup of order equal to any unitary divisor of the group order (that is, a divisor coprime to its cofactor).
Counterexample of the converse of Lagrange's theoremEdit
The converse of Lagrange's theorem states that if Template:Mvar is a divisor of the order of a group Template:Mvar, then there exists a subgroup Template:Mvar where Template:Math.
We will examine the alternating group Template:Math, the set of even permutations as the subgroup of the Symmetric group Template:Math.
Template:Math so the divisors are Template:Math. Assume to the contrary that there exists a subgroup Template:Mvar in Template:Math with Template:Math.
Let Template:Mvar be the non-cyclic subgroup of Template:Math called the Klein four-group.
Let Template:Math. Since both Template:Mvar and Template:Mvar are subgroups of Template:Math, Template:Mvar is also a subgroup of Template:Math.
From Lagrange's theorem, the order of Template:Mvar must divide both Template:Math and Template:Math, the orders of Template:Mvar and Template:Mvar respectively. The only two positive integers that divide both Template:Math and Template:Math are Template:Math and Template:Math. So Template:Math or Template:Math.
Assume Template:Math, then Template:Math. If Template:Mvar does not share any elements with Template:Mvar, then the 5 elements in Template:Mvar besides the Identity element Template:Mvar must be of the form Template:Math where Template:Math are distinct elements in Template:Math.
Since any element of the form Template:Math squared is Template:Math, and Template:Math, any element of Template:Mvar in the form Template:Math must be paired with its inverse. Specifically, the remaining 5 elements of Template:Mvar must come from distinct pairs of elements in Template:Math that are not in Template:Mvar. This is impossible since pairs of elements must be even and cannot total up to 5 elements. Thus, the assumptions that Template:Math is wrong, so Template:Math.
Then, Template:Math where Template:Math, Template:Mvar must be in the form Template:Math where Template:Mvar are distinct elements of Template:Math. The other four elements in Template:Mvar are cycles of length 3.
Note that the cosets generated by a subgroup of a group form a partition of the group. The cosets generated by a specific subgroup are either identical to each other or disjoint. The index of a subgroup in a group Template:Math is the number of cosets generated by that subgroup. Since Template:Math and Template:Math, Template:Mvar will generate two left cosets, one that is equal to Template:Mvar and another, Template:Mvar, that is of length 6 and includes all the elements in Template:Math not in Template:Mvar.
Since there are only 2 distinct cosets generated by Template:Mvar, then Template:Mvar must be normal. Because of that, Template:Math. In particular, this is true for Template:Math. Since Template:Math.
Without loss of generality, assume that Template:Math, Template:Math, Template:Math, Template:Math. Then Template:Math, Template:Math, Template:Math, Template:Math, Template:Math. Transforming back, we get Template:Math. Because Template:Mvar contains all disjoint transpositions in Template:Math, Template:Math. Hence, Template:Math.
Since Template:Math, we have demonstrated that there is a third element in Template:Mvar. But earlier we assumed that Template:Math, so we have a contradiction.
Therefore, our original assumption that there is a subgroup of order 6 is not true and consequently there is no subgroup of order 6 in Template:Math and the converse of Lagrange's theorem is not necessarily true. Q.E.D.
HistoryEdit
Lagrange himself did not prove the theorem in its general form. He stated, in his article Réflexions sur la résolution algébrique des équations,<ref>Template:Citation ; see especially pages 202-203.</ref> that if a polynomial in Template:Mvar variables has its variables permuted in all Template:Math ways, the number of different polynomials that are obtained is always a factor of Template:Math. (For example, if the variables Template:Mvar, Template:Mvar, and Template:Mvar are permuted in all 6 possible ways in the polynomial Template:Math then we get a total of 3 different polynomials: Template:Math, Template:Math, and Template:Math. Note that 3 is a factor of 6.) The number of such polynomials is the index in the symmetric group Template:Math of the subgroup Template:Mvar of permutations that preserve the polynomial. (For the example of Template:Math, the subgroup Template:Mvar in Template:Math contains the identity and the transposition Template:Math.) So the size of Template:Mvar divides Template:Math. 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.
In his Disquisitiones Arithmeticae in 1801, Carl Friedrich Gauss proved Lagrange's theorem for the special case of <math>(\mathbb Z/p \mathbb Z)^*</math>, the multiplicative group of nonzero integers modulo Template:Mvar, where Template:Mvar is a prime.<ref>Template:Citation, pp. 41-45, Art. 45-49.</ref> In 1844, Augustin-Louis Cauchy proved Lagrange's theorem for the symmetric group Template:Math.<ref>Augustin-Louis Cauchy, §VI. — Sur les dérivées d'une ou de plusieurs substitutions, et sur les systèmes de substitutions conjuguées [On the products of one or several permutations, and on systems of conjugate permutations] of: "Mémoire sur les arrangements que l'on peut former avec des lettres données, et sur les permutations ou substitutions à l'aide desquelles on passe d'un arrangement à un autre" [Memoir on the arrangements that one can form with given letters, and on the permutations or substitutions by means of which one passes from one arrangement to another] in: Exercises d'analyse et de physique mathématique [Exercises in analysis and mathematical physics], vol. 3 (Paris, France: Bachelier, 1844), pp. 183-185.</ref>
Camille Jordan finally proved Lagrange's theorem for the case of any permutation group in 1861.<ref>Template:Citation Jordan's generalization of Lagrange's theorem appears on page 166.</ref>