# Tour:Lagrange's theorem

**This article adapts material from the main article:** Lagrange's theorem

This page is part of the Groupprops Guided tour for beginners (Jump to beginning of tour)PREVIOUS: Index of a subgroup |UP: Introduction three (beginners) |NEXT: Generating set of a group

WHAT YOU NEED TO DO:

- Read and understand the statement of Lagrange's theorem
- Make sure the proof is clear to you. Fill in any missing details.

## Statement

### Verbal statement

In a finite group, the order of any subgroup divides the order of the group. In fact, the ratio of the orders is the index of the subgroup, which is the same as the number of left cosets, and as the number of right cosets, of the subgroup.

### Statement with symbols

Let be a finite group, and be a subgroup. Then, if denote the orders of these groups (i.e., the cardinalities of their underlying sets) and denotes the index of in , then:

## Facts used

- Left cosets partition a group: So the group is a disjoint union of left cosets of the subgroup
- Left cosets are in bijection via left multiplication: All the left cosets have the same size.

## Proof

**Given**: A finite group , a subgroup

**To prove**:

**Proof**: From fact (1), we know that we can write as a disjoint union of left cosets of . Let be the number of left cosets of and be the left cosets of . Then, we can write:

(the symbol stands for disjoint union).

Taking cardinalities both sides:

By fact (2) for each left coset of , so:

WHAT'S MORE: Further information on applications, converses, infinite versions and measure-theoretic versions of Lagrange's theorem. Some of these will be touched upon in the Mind's Eye Test and Interdisciplinary problems.

## Related facts

### Stronger facts

- Index is multiplicative: This states that if are subgroups then . Lagrange's theorem is a special case with the trivial subgroup.

### Applications

Lagrange's theorem is extremely useful in providing information about the size and structure of subgroups given information about the size of the whole group. Here are some obvious corollaries of Lagrange's theorem:

- Subgroup of size more than half is whole group: This turns out to be useful when trying to prove that a certain subgroup is the whole group. It is also used to design probabilistic tests of primality.
- Prime order implies no proper nontrivial subgroup
- Order of element divides order of group: In a finite group, the order of any element, i.e., the smallest positive integer for which its power is the identity element, is a divisor of the order of the group.

### Normal subgroups and surjective homomorphisms

Combining Lagrange's theorem with the first isomorphism theorem, we see that given any surjective homomorphism of finite groups and , the order of must divide the order of . That's because, if is the kernel of the homomorphism, the first isomorphism theorem identifies with the quotient group , whose order equals the index . See:

- Order of quotient group divides order of group
- Order of extension group is product of order of normal subgroup and quotient group

In fact, more is true: the surjective homomorphism from to has the property that the inverse images of all elements of have equal size.
`Further information: Variety of groups is congruence-uniform`

### Transitive group actions

`Further information: orbit-counting theorem, fundamental theorem of group actions`

If acts transitively on a set , and denotes the isotropy subgroup of a point , then the set can be identified with the left coset space . In particular, we get:

Hence, the order of divides the order of .

### Converse

`Further information: Group having subgroups of every order dividing the group order`

While there's no direct formulation of a *converse* to Lagrange's theorem, one plausible converse might be: given any finite group , and any positive divisor of the order of , there exists a subgroup of of order . This is, however false. The smallest counterexample is the alternating group on four elements, which has order 12 and has no subgroup of order 6 (see its subgroup structure). However, partial versions of the converse are true:

- For a cyclic group, there is a unique subgroup of every order dividing the order of the group.
- A group of prime power order, and more generally, a finite nilpotent group, and even more generally a finite supersolvable group, has subgroups of every possible order dividing the order of the group.
`For full proof, refer: Prime power order implies subgroups of all orders dividing the group order, Finite supersolvable implies subgroups of all orders dividing the group order` - Sylow's theorem: In any finite group, there exist Sylow subgroups. A Sylow subgroup is a group of prime power order, whose order and index are relatively prime.
- Hall's theorem: A finite group is a finite solvable group if and only if it has Hall subgroups of all permissible orders. A Hall subgroup is a subgroup whose order and index are relatively prime.
- Every finite solvable group is a subgroup of a finite group having subgroups of all orders dividing the group order

### Choice of coset representatives

Lagrange's theorem proves that the order of a group equals the product of the order of the subgroup and the number of left cosets. There is, however, no natural bijection between the group and the Cartesian product of the subgroup and the left coset space. In other words, for a subgroup , there is no natural bijection:

.

We *can* obtain a bijection if we choose a set of coset representatives, i.e., we make a choice of one element in each left coset. Such a choice gives a specific bijection between the subgroup and each of its left cosets. Essentially, the coset representative is used as a reference point. To describe an element of , we describe its coset, and the ratio between that element and its coset representative, and this yields the bijection.

However, there is in general no natural choice of coset representatives, and being able to choose coset representatives requires the axiom of choice. The Vitali construction of a non-measurable set, as well as the Banach-Tarski paradox, use precisely this ability.

## Infinite versions

`Further information: Cardinal multiplication#Lagrange's theorem`

While Lagrange's theorem is typically stated for a finite group, the reasoning used in its proof also works for infinite groups. Thus, if is any group, is a subgroup, then, in the sense of cardinals:

The theory of multiplication of infinite cardinals allows us to determine the cardinality of knowing the cardinality of and ; however, it does not permit us to always compute successfully the cardinality of using the other two, or to compute the index using the other two quantities.

## Analogues

### Groups with measures

Lagrange's theorem has analogues in groups equipped with measures (in fact, the analogues make sense in groups equipped with finitely additive functions, such as amenable discrete groups). Here, we replace the *order* of the group and subgroup by their measures, while the index remains the index. Thus, if is a group with a left-invariant measure and is a measurable subgroup of , of finite index in , then:

`Further information: Lagrange's theorem for measures`

### Weaker algebraic structures

The analogue of Lagrange's theorem fails to hold for structures like magmas, semigroups, and monoids. There are two problems: the *left cosets* of any submonoid are not necessarily pairwise disjoint, and the left cosets may not have equal size. For a cancellative monoid, the left cosets do always have equal size, but they still may not be pairwise disjoint.

This page is part of the Groupprops Guided tour for beginners (Jump to beginning of tour). If you found anything difficult or unclear, make a note of it; it is likely to be resolved by the end of the tour.PREVIOUS: Index of a subgroup |UP: Introduction three (beginners) |NEXT: Generating set of a group