# Subgroups and Cosets: Why Lagrange's Theorem Produces Divisibility

> From the one-step subgroup test to Lagrange's theorem: left cosets split a group into blocks of equal size, giving Euler's theorem and a counterexample to the converse.
> https://rikai.mugen-giken.com/en/mathematics/algebra/subgroups-and-lagrange

## 0. Key points

- A **subgroup** of a group $G$ is a subset that becomes a group under the restriction of the operation of $G$. Only two things need checking: that it is nonempty, and that $a, b \in H$ implies $ab^{-1} \in H$ (<Ref to="prop-subgroup-criterion" />).
- A subgroup $H$ partitions $G$ into **left cosets** $aH$. These are the equivalence classes of the relation "$a^{-1}b \in H$", which is a direct generalization of congruence of integers, $a \equiv b \pmod{n}$.
- Every left coset has exactly as many elements as $H$. For finite groups this yields $|G| = [G:H]\,|H|$ (<Ref to="thm-lagrange" />): the order of a subgroup divides the order of the group.
- As a corollary, the order of an element divides the order of the group, and $a^{|G|} = e$ (<Ref to="cor-element-order" />). Applied to the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$, this gives Euler's theorem and Fermat's little theorem in three lines.
- The converse fails. The alternating group $A_4$ has order 12 but no subgroup of order 6 (<Ref to="prop-a4-no-order-six" />).

## 1. Motivation — the order alone constrains the internal structure

In [Introduction to group theory: the definition and examples](/en/mathematics/algebra/groups) we saw that the framework of a group (<Ref to="mathematics/algebra/groups#def-group" text="definition of a group" />) lets us treat addition of integers, multiplication of matrices, symmetries of figures, and permutations in one and the same language. Once we have the definition, the next question is how to probe the inside of a group.

Let us begin with a naive question. **Can a group of order 12 contain a substructure of order 5?**

The question is naive because we have said nothing about what the group looks like. It might be part of the symmetry group of a dodecahedron, or a collection of matrices. Yet the answer is determined: no. And the reason is startlingly simple — $5$ does not divide $12$. That is all. This is the content of Lagrange's theorem.

The strength of the word "divides" here becomes clear when we compare with linear algebra. As we saw in [Vector spaces and linear maps](/en/mathematics/linear-algebra/vector-spaces), a subspace $W \subseteq V$ only gives us the **inequality** $\dim W \le \dim V$ (<Ref to="mathematics/linear-algebra/vector-spaces#prop-finite-dim-facts" text="basic properties of finite-dimensional spaces" />). If $\dim V = 12$, then $\dim W$ may be anything from $0$ to $12$. For groups, by contrast, the size of a subgroup is restricted to **divisors** of the size of the whole: the possible values drop from twelve to six ($1, 2, 3, 4, 6, 12$).

Let us state up front why a division appears. The "copies of $H$" obtained by translating a subgroup $H$ inside the group tile $G$ exactly. The number of tiles is the index $[G:H]$, each tile carries $|H|$ elements, and the whole floor has $|G|$ of them. Making this single picture precise is the purpose of this article.

Historically, the theorem originates in Lagrange's work on the theory of equations in 1770–71, where he found that the number of distinct values taken by a rational function of $n$ variables, as the variables are permuted, divides $n!$. At that time the notion of a group did not exist. More than half a century of clarification by Cauchy and Jordan was needed before the statement took its modern form, "the order of a subgroup divides the order of the group". We say more in the Appendix.

## 2. Preliminaries — notation and conventions

Throughout, $G$ denotes a group, and unless stated otherwise its operation is written multiplicatively. We write $e$ for the identity, $a^{-1}$ for the inverse of $a$, and $a^k$ for the product of $k$ copies of $a$ (for negative $k$, the product of $|k|$ copies of $a^{-1}$; and $a^0 = e$). For a group written additively, such as $\mathbb{Z}$, read $e$ as $0$, $a^{-1}$ as $-a$, and $a^k$ as $ka$.

For a finite group $G$ we write $|G|$ for the number of its elements and call it the **order** of $G$.

One tool will be used again and again, so let us record it. Groups satisfy the **cancellation laws** (<Ref to="mathematics/algebra/groups#prop-group-basics" text="basic properties of groups" />): if $ax = ay$ then $x = y$. Indeed, multiplying on the left by $a^{-1}$ gives $a^{-1}(ax) = a^{-1}(ay)$, and associativity turns this into $(a^{-1}a)x = (a^{-1}a)y$, that is, $x = y$. The right-hand law $xa = ya \implies x = y$ is proved in the same way.

We also fix notation for symmetric groups (<Ref to="mathematics/algebra/groups#def-permutation" text="permutations and symmetric groups" />). The symmetric group $S_n$ of degree $n$ consists of all bijections (permutations) of $\{1, 2, \ldots, n\}$ onto itself under composition, and $|S_n| = n!$. We read the product $\sigma\tau$ as "first apply $\tau$, then apply $\sigma$". The cycle notation $(1\,2\,3)$ denotes the permutation sending $1 \mapsto 2$, $2 \mapsto 3$, $3 \mapsto 1$ and fixing everything else; a two-letter cycle such as $(1\,2)$ is called a transposition. We write $A_n$ for the set of all even permutations (so $|A_n| = n!/2$ for $n \ge 2$).

## 3. Subgroups

### 3.1. Definition

<Definition id="def-subgroup" title="Subgroup">

Let $G$ be a group and $H$ a subset of $G$. We call $H$ a **subgroup** of $G$, written $H \le G$, if the following three conditions hold.

- (S1) $e \in H$, where $e$ is the identity of $G$.
- (S2) If $a, b \in H$ then $ab \in H$ (closure under the operation).
- (S3) If $a \in H$ then $a^{-1} \in H$ (closure under inverses).

Both $\{e\}$ and $G$ itself are always subgroups of $G$; these are called the **trivial subgroups**. If $H \le G$ and $H \ne G$, we call $H$ a **proper subgroup**.

</Definition>

<Remark id="rem-subgroup-is-group">

The three conditions of <Ref to="def-subgroup" /> are equivalent to saying that $H$ is itself a group under the restricted operation. Let us fill in the details.

Assume (S1)–(S3). Condition (S2) guarantees that the multiplication of $G$ restricts to a map $H \times H \to H$. Associativity already holds in $G$, so it holds in $H$. By (S1) there is an identity and by (S3) there are inverses, so $H$ is a group.

Conversely, suppose $H$ is a group under the restricted operation. Writing $e_H$ for the identity of $H$, we have $e_H e_H = e_H$. This is also an equation in $G$, so multiplying on the right by $e_H^{-1}$ in $G$ gives $e_H = e$. Hence (S1) holds. Likewise, if $a'$ denotes the inverse of $a \in H$ taken in $H$, then $a a' = e_H = e$, and multiplying on the left by $a^{-1}$ in $G$ gives $a' = a^{-1}$, which is (S3).

So the statements "the identity of a subgroup coincides with the identity of the whole group" and "inverses in a subgroup coincide with inverses in the whole group" are conclusions, not hypotheses. This is where the situation differs from substructures of rings, where one must decide whether to demand that a subring contain the identity; for groups the agreement is automatic.

</Remark>

### 3.2. Criteria

Verifying three conditions every time is tedious. In fact they can be compressed into one.

<Proposition id="prop-subgroup-criterion" title="Subgroup criteria">

Let $G$ be a group and $H$ a subset of $G$.

1. (One-step test) $H \le G$ if and only if $H \ne \emptyset$ and $ab^{-1} \in H$ for all $a, b \in H$.
2. (Finite test) If $H$ is a **finite** set, then $H \le G$ if and only if $H \ne \emptyset$ and $ab \in H$ for all $a, b \in H$.

</Proposition>

<Proof of="prop-subgroup-criterion">

**Necessity in (1).** Let $H \le G$. By (S1) we have $e \in H$, so $H \ne \emptyset$. Given $a, b \in H$, condition (S3) gives $b^{-1} \in H$, and then (S2) gives $ab^{-1} \in H$.

**Sufficiency in (1).** Assume $H \ne \emptyset$ and that $a, b \in H \implies ab^{-1} \in H$.

Since $H \ne \emptyset$, choose an element $a \in H$. Applying the hypothesis to the pair $(a, a)$ gives $aa^{-1} = e \in H$, which is (S1). Next, for $b \in H$, applying the hypothesis to $(e, b)$ gives $eb^{-1} = b^{-1} \in H$, which is (S3). Finally, for $a, b \in H$, the (S3) just proved gives $b^{-1} \in H$, so applying the hypothesis to $(a, b^{-1})$ yields $a(b^{-1})^{-1} = ab \in H$, which is (S2).

**Necessity in (2).** This is exactly (S2).

**Sufficiency in (2).** Suppose $H$ is finite, nonempty, and closed under multiplication. Fix $a \in H$ and consider the map

$$
\lambda_a : H \longrightarrow H, \qquad \lambda_a(x) = ax
$$

Closure gives $ax \in H$, so $\lambda_a$ really does map $H$ into $H$. If $\lambda_a(x) = \lambda_a(y)$, then $ax = ay$, and cancellation (§2) gives $x = y$; hence $\lambda_a$ is injective. Since $H$ is a **finite** set, an injection from a finite set to itself is surjective. This is where finiteness enters.

By surjectivity there is an $x \in H$ with $\lambda_a(x) = a$. Cancelling in $ax = a = ae$ gives $x = e$, so $e \in H$ and (S1) holds. Again by surjectivity there is a $y \in H$ with $\lambda_a(y) = e$; multiplying $ay = e$ on the left by $a^{-1}$ gives $y = a^{-1}$, so $a^{-1} \in H$ and (S3) holds.

</Proof>

<Aside type="caution">
Finiteness in (2) cannot be dropped. The subset $H = \{0, 1, 2, \ldots\}$ of the additive group $\mathbb{Z}$ is nonempty and closed under addition, but it does not contain $-1$, the inverse of $1$, so it is not a subgroup. The slogan "closure under multiplication drags inverses in for free" holds only in the finite world, where multiplying an element by itself repeatedly eventually comes back around.
</Aside>

### 3.3. Examples and non-examples

<Example id="ex-familiar-subgroups" title="Subgroups we use constantly">

Using <Ref to="prop-subgroup-criterion" />(1), each of the following is checked to be a subgroup in one line.

**(a) $n\mathbb{Z} \le \mathbb{Z}$.** Let $n$ be an integer and $n\mathbb{Z} = \{nk : k \in \mathbb{Z}\}$. It is nonempty since $0 = n \cdot 0$, and $nk - nl = n(k-l) \in n\mathbb{Z}$ (the group is additive, so read $ab^{-1}$ as $a - b$).

**(b) $SL_n(\mathbb{R}) \le GL_n(\mathbb{R})$.** Here $GL_n(\mathbb{R})$ is the multiplicative group of invertible real matrices and $SL_n(\mathbb{R}) = \{A : \det A = 1\}$. It is nonempty since $\det I = 1$, and for $A, B \in SL_n(\mathbb{R})$ we have $\det(AB^{-1}) = \det A \cdot (\det B)^{-1} = 1 \cdot 1^{-1} = 1$.

**(c) $O(n) \le GL_n(\mathbb{R})$.** Let $O(n) = \{A : A^{\mathsf{T}}A = I\}$. Then $I \in O(n)$. If $A, B \in O(n)$, then $B^{\mathsf{T}}B = I$ gives $B^{-1} = B^{\mathsf{T}}$, so $AB^{-1} = AB^{\mathsf{T}}$, and

$$
(AB^{\mathsf{T}})^{\mathsf{T}}(AB^{\mathsf{T}}) = B A^{\mathsf{T}} A B^{\mathsf{T}} = B I B^{\mathsf{T}} = BB^{-1} = I
$$

**(d) $A_n \le S_n$.** Using the fact that the sign map $\operatorname{sgn} : S_n \to \{\pm 1\}$ satisfies $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$, we get $\operatorname{sgn}(\sigma\tau^{-1}) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)^{-1} = 1 \cdot 1 = 1$. The set is nonempty because the identity permutation is even.

**Some non-examples.** The set of all odd integers is not a subgroup of $\mathbb{Z}$: it violates (S2) since $1 + 1 = 2$ is not odd, and it violates (S1) since it does not contain $0$. The set of real matrices of determinant $2$ is not a subgroup of $GL_n(\mathbb{R})$ either, since a product would have determinant $4$. Carving out a subset by a condition does not automatically give a subgroup; the condition must be compatible with both multiplication and inversion.

</Example>

The next example shows that in $\mathbb{Z}$, the most familiar group of all, subgroups are already tied to the language of divisors.

<Example id="ex-subgroups-of-z" title="Every subgroup of Z has the form nZ">

The subgroups of the additive group $\mathbb{Z}$ are exactly the sets $n\mathbb{Z}$ with $n \ge 0$, and this $n$ is unique.

**Proof.** Let $H \le \mathbb{Z}$. If $H = \{0\}$ then $H = 0\mathbb{Z}$. Otherwise $H$ contains a nonzero element $a$, and by (S3) also $-a$, so $H$ contains a positive integer. Since the natural numbers are well ordered, there is a least positive integer belonging to $H$; call it $n$.

The inclusion $n\mathbb{Z} \subseteq H$ follows from $n \in H$ together with (S2) and (S3): $nk$ is the sum of $k$ copies of $n$, or of $|k|$ copies of $-n$ when $k$ is negative.

For the reverse inclusion, take any $a \in H$ and write $a = qn + r$ with $0 \le r < n$ by the division algorithm. Then $qn \in n\mathbb{Z} \subseteq H$, so $-qn \in H$ by (S3), and $r = a + (-qn) \in H$ by (S2). If $r > 0$, then $r$ would be a positive integer in $H$ with $r < n$, contradicting the minimality of $n$. Hence $r = 0$, that is, $a = qn \in n\mathbb{Z}$.

As for uniqueness, if $n\mathbb{Z} = m\mathbb{Z}$ with $n, m \ge 0$, then each divides the other, so $n = m$. $\square$

**What this example is telling us.** We have $n\mathbb{Z} \subseteq m\mathbb{Z}$ precisely when $m \mid n$. In other words, the inclusion order among subgroups of $\mathbb{Z}$ is nothing but divisibility of integers. The notion of a subgroup is on intimate terms with the relation "divides" from the very start.

</Example>

## 4. Cyclic subgroups and the order of an element

To translate Lagrange's theorem into the language of elements, we set up the smallest subgroup generated by a single element.

<Definition id="def-cyclic-and-order" title="Generated cyclic subgroup and the order of an element">

Let $G$ be a group and $a \in G$. We call

$$
\langle a \rangle := \{a^k : k \in \mathbb{Z}\}
$$

the **cyclic subgroup generated by** $a$. It is indeed a subgroup: it is nonempty since $a^0 = e$, and $a^k (a^l)^{-1} = a^{k-l} \in \langle a \rangle$, so <Ref to="prop-subgroup-criterion" />(1) applies.

If there exists a positive integer $n$ with $a^n = e$, the least such $n$ is called the **order** of $a$, written $\operatorname{ord}(a)$. If no such $n$ exists we set $\operatorname{ord}(a) = \infty$.

</Definition>

<Proposition id="prop-cyclic-subgroup" title="The order of an element and the size of its cyclic subgroup">

Let $G$ be a group and $a \in G$.

1. If $G$ is finite then $\operatorname{ord}(a) < \infty$.
2. Let $n = \operatorname{ord}(a) < \infty$. For an integer $k$ we have $a^k = e$ if and only if $n \mid k$.
3. Let $n = \operatorname{ord}(a) < \infty$. Then $\langle a \rangle = \{e, a, a^2, \ldots, a^{n-1}\}$ and these $n$ elements are pairwise distinct. In particular $|\langle a \rangle| = \operatorname{ord}(a)$.

</Proposition>

<Proof of="prop-cyclic-subgroup">

**(1)** All of $a^1, a^2, a^3, \ldots$ lie in the finite set $G$, so by the pigeonhole principle there are indices $1 \le i < j$ with $a^i = a^j$. Multiplying by $(a^i)^{-1}$ gives $a^{j-i} = e$, and $j - i$ is a positive integer. Hence a positive integer $n$ with $a^n = e$ exists, and $\operatorname{ord}(a)$ is defined as the least such.

**(2)** If $n \mid k$, say $k = nq$, then $a^k = (a^n)^q = e^q = e$. Conversely suppose $a^k = e$, and write $k = qn + r$ with $0 \le r < n$ by the division algorithm. Then

$$
a^r = a^{k - qn} = a^k (a^n)^{-q} = e \cdot e^{-q} = e
$$

So $a^r = e$ with $0 \le r < n$. But $n$ was the **least positive integer** with $a^m = e$, so $r$ cannot be positive. Hence $r = 0$, that is, $n \mid k$.

**(3)** Writing any integer $k$ as $k = qn + r$ with $0 \le r < n$ gives $a^k = (a^n)^q a^r = a^r$, so $\langle a \rangle = \{a^0, a^1, \ldots, a^{n-1}\}$. We show these are distinct. Suppose $a^i = a^j$ with $0 \le i < j \le n-1$. Then $a^{j-i} = e$, so $n \mid j - i$ by (2). But $0 < j - i \le n - 1 < n$, so $j - i$ cannot be a positive multiple of $n$ — a contradiction. Hence the $n$ elements are distinct and $|\langle a \rangle| = n$.

</Proof>

For instance, in $S_3$ the transposition $(1\,2)$ has order 2 because $(1\,2)^2 = e$, while the cycle $(1\,2\,3)$ has order 3 because $(1\,2\,3)^2 = (1\,3\,2) \ne e$ and $(1\,2\,3)^3 = e$. In general a cycle on $k$ letters has order $k$.

## 5. Cosets — the partition induced by a subgroup

### 5.1. Definition

<Definition id="def-coset" title="Left and right cosets">

Let $H \le G$ and $a \in G$. The sets

$$
aH := \{ah : h \in H\}, \qquad Ha := \{ha : h \in H\}
$$

are called the **left coset** and the **right coset** of $H$ containing $a$. We write $G/H$ for the set of all left cosets and $H \backslash G$ for the set of all right cosets.

</Definition>

Let us see where this definition comes from, in the most familiar case. Take $G = \mathbb{Z}$ (additive) and $H = n\mathbb{Z}$. Then a left coset is

$$
a + n\mathbb{Z} = \{\ldots,\ a - n,\ a,\ a + n,\ \ldots\}
$$

which is the set of all integers leaving the same remainder as $a$ upon division by $n$ — in other words, the **congruence class** modulo $n$. And as we will see, $a + n\mathbb{Z} = b + n\mathbb{Z}$ holds if and only if $a - b \in n\mathbb{Z}$, that is, $a \equiv b \pmod{n}$. A coset is a generalization of congruence, and that is where the name "residue class" comes from.

### 5.2. Basic properties

<Lemma id="lem-coset-basic" title="Basic properties of left cosets">

Let $H \le G$ and $a, b \in G$.

1. $a \in aH$.
2. The following three conditions are equivalent: (i) $aH = bH$; (ii) $a^{-1}b \in H$; (iii) $b \in aH$.
3. If $aH \cap bH \ne \emptyset$ then $aH = bH$. Hence distinct left cosets are disjoint, and together with (1) this writes $G$ as a disjoint union of left cosets.
4. The map $H \to aH$, $h \mapsto ah$, is a bijection. In particular $|aH| = |H|$ (as an equality of cardinalities in the infinite case).

</Lemma>

<Proof of="lem-coset-basic">

**(1)** By (S1) of <Ref to="def-subgroup" /> we have $e \in H$, so $a = ae \in aH$.

**(2)** We prove the three implications in turn.

(i) $\implies$ (ii). Suppose $aH = bH$. Applying (1) to $b$ gives $b \in bH = aH$, so $b = ah$ for some $h \in H$. Hence $a^{-1}b = h \in H$.

(ii) $\implies$ (iii). Put $h_0 := a^{-1}b \in H$; then $b = a h_0 \in aH$.

(iii) $\implies$ (i). Suppose $b \in aH$ and write $b = ah_0$ with $h_0 \in H$. For any $h \in H$ we have $bh = a(h_0h)$, and $h_0h \in H$ by (S2), so $bh \in aH$; thus $bH \subseteq aH$. Conversely, (S3) gives $h_0^{-1} \in H$ and $a = bh_0^{-1}$, so the same argument gives $aH \subseteq bH$. Hence $aH = bH$.

**(3)** Let $c \in aH \cap bH$. From $c \in aH$ and the implication (iii) $\implies$ (i) of (2) we get $aH = cH$; similarly $c \in bH$ gives $bH = cH$. Hence $aH = bH$.

Moreover, by (1) every $g \in G$ lies in $gH$, so the union of the left cosets is all of $G$. Two distinct left cosets cannot meet, for if they did they would coincide by what we just proved. Thus the left cosets form a partition of $G$.

**(4)** Put $\lambda : H \to aH$, $\lambda(h) = ah$. By the definition of $aH$ the map $\lambda$ is surjective. If $\lambda(h) = \lambda(h')$, that is, $ah = ah'$, then cancellation (§2) gives $h = h'$, so $\lambda$ is injective.

</Proof>

<Remark id="rem-coset-equivalence">

Parts (2) and (3) of <Ref to="lem-coset-basic" /> are a restatement of the fact that the relation

$$
a \sim b \quad :\Longleftrightarrow \quad a^{-1}b \in H
$$

is an equivalence relation on $G$ whose equivalence classes are exactly the left cosets. Indeed, reflexivity holds because $a^{-1}a = e \in H$; symmetry because $a^{-1}b \in H$ gives $(a^{-1}b)^{-1} = b^{-1}a \in H$ by (S3); and transitivity because $a^{-1}b, b^{-1}c \in H$ give $(a^{-1}b)(b^{-1}c) = a^{-1}c \in H$ by (S2). It is pleasing that the three conditions defining a subgroup correspond one for one to the three conditions defining an equivalence relation.

The general fact that an equivalence relation induces a partition of a set is in [Relations and equivalence relations: what does "the same" mean?](/mathematics/foundations/equivalence-relations) (<Ref to="mathematics/foundations/equivalence-relations#thm-partition" text="the correspondence between equivalence relations and partitions" />). For $G = \mathbb{Z}$ and $H = n\mathbb{Z}$, this equivalence relation reads $b - a \in n\mathbb{Z}$, which is precisely congruence modulo $n$.

</Remark>

<Definition id="def-index" title="Index">

For $H \le G$, the number of left cosets (in general, the cardinality of $G/H$) is called the **index** of $H$ in $G$ and is written $[G:H]$.

</Definition>

<Remark id="rem-right-cosets">

Defining the index using right cosets gives the same value, because the map

$$
\Phi : G/H \longrightarrow H \backslash G, \qquad \Phi(aH) = Ha^{-1}
$$

is a bijection. Reflecting the argument of <Ref to="lem-coset-basic" />(2) left to right gives $Hx = Hy \iff xy^{-1} \in H$, so $Ha^{-1} = Hb^{-1}$ holds if and only if $a^{-1}(b^{-1})^{-1} = a^{-1}b \in H$, that is, if and only if $aH = bH$. This equivalence simultaneously shows that $\Phi$ is well defined, independent of the choice of representative (read left to right), and that it is injective (read right to left). Surjectivity follows since any right coset $Ha$ satisfies $\Phi(a^{-1}H) = H(a^{-1})^{-1} = Ha$.

The naive assignment $aH \mapsto Ha$, by contrast, fails: it depends on the choice of representative and so does not define a map at all. The next example, <Ref to="ex-s3-cosets" />, exhibits this concretely.

</Remark>

### 5.3. A computation in S3

<Example id="ex-s3-cosets" title="Cosets in S3 (left and right do not agree)">

Take $G = S_3$ and $H = \langle (1\,2) \rangle = \{e, (1\,2)\}$. Since $(1\,2)^2 = e$, this $H$ is indeed a subgroup of order 2. Products are computed right to left.

**Left cosets.** First, $eH = H = \{e, (1\,2)\}$. Next,

$$
(1\,3)(1\,2) : \quad 1 \mapsto 2 \mapsto 2, \quad 2 \mapsto 1 \mapsto 3, \quad 3 \mapsto 3 \mapsto 1
$$

so $(1\,3)(1\,2) = (1\,2\,3)$ and hence $(1\,3)H = \{(1\,3),\ (1\,2\,3)\}$. Similarly,

$$
(2\,3)(1\,2) : \quad 1 \mapsto 2 \mapsto 3, \quad 2 \mapsto 1 \mapsto 1, \quad 3 \mapsto 3 \mapsto 2
$$

gives $(2\,3)(1\,2) = (1\,3\,2)$, so $(2\,3)H = \{(2\,3),\ (1\,3\,2)\}$.

The three sets $\{e, (1\,2)\}$, $\{(1\,3), (1\,2\,3)\}$, $\{(2\,3), (1\,3\,2)\}$ are pairwise disjoint and their union is all six elements of $S_3$: exactly the partition asserted by <Ref to="lem-coset-basic" />. Therefore $[S_3 : H] = 3$.

**Right cosets.** Computing in the same way, $(1\,2)(1\,3) = (1\,3\,2)$ and $(1\,2)(2\,3) = (1\,2\,3)$, so

$$
He = \{e, (1\,2)\}, \quad H(1\,3) = \{(1\,3),\ (1\,3\,2)\}, \quad H(2\,3) = \{(2\,3),\ (1\,2\,3)\}
$$

There are three of them, the same number as on the left, but **as a family of sets they do not coincide with the left cosets**. For example, $(1\,3)H = \{(1\,3), (1\,2\,3)\}$ while $H(1\,3) = \{(1\,3), (1\,3\,2)\}$.

</Example>

<Figure caption="S3 split into the left cosets of the subgroup H = ⟨(1 2)⟩. Each of the three boxes holds two elements, and they are pairwise disjoint.">
<svg viewBox="0 0 720 250" width="100%" role="img" aria-label="S3 partitioned into three left cosets">
  <rect x="14" y="46" width="692" height="128" rx="12" fill="none" stroke="currentColor" stroke-width="1.5" stroke-dasharray="6 5" opacity="0.55" />
  <text x="18" y="34" font-size="17" fill="currentColor">The 6 elements of S₃ split by the left cosets of H = ⟨(1 2)⟩</text>
  <rect x="34" y="64" width="196" height="92" rx="10" fill="none" stroke="var(--sl-color-accent)" stroke-width="2" />
  <text x="132" y="94" font-size="16" text-anchor="middle" fill="var(--sl-color-accent)">eH = H</text>
  <text x="132" y="128" font-size="17" text-anchor="middle" fill="currentColor">e ,  (1 2)</text>
  <rect x="262" y="64" width="196" height="92" rx="10" fill="none" stroke="currentColor" stroke-width="2" />
  <text x="360" y="94" font-size="16" text-anchor="middle" fill="currentColor">(1 3)H</text>
  <text x="360" y="128" font-size="17" text-anchor="middle" fill="currentColor">(1 3) ,  (1 2 3)</text>
  <rect x="490" y="64" width="196" height="92" rx="10" fill="none" stroke="currentColor" stroke-width="2" />
  <text x="588" y="94" font-size="16" text-anchor="middle" fill="currentColor">(2 3)H</text>
  <text x="588" y="128" font-size="17" text-anchor="middle" fill="currentColor">(2 3) ,  (1 3 2)</text>
  <text x="360" y="206" font-size="17" text-anchor="middle" fill="currentColor">3 cosets × 2 elements each = 6 elements</text>
  <text x="360" y="233" font-size="15" text-anchor="middle" fill="currentColor" opacity="0.8">index 3 × order of subgroup 2 = order of group 6</text>
</svg>
</Figure>

A subgroup whose left cosets and right cosets agree as families is special: it is called a **normal subgroup**. In that case the set of cosets $G/H$ itself carries a group structure, and one obtains a quotient group. We treat this in [Normal subgroups and quotient groups](/en/mathematics/algebra/quotient-groups). What matters here is that, without assuming normality, the left cosets **always** partition $G$ into blocks of equal size. That is all Lagrange's theorem needs.

## 6. Lagrange's theorem

<Figure caption="The logical route to Lagrange's theorem. Starting from the three subgroup axioms, two pillars — the partition and the equality of sizes — support the theorem.">
<Mermaid code={`flowchart TD
  A["subgroup H ⊆ G"] --> B["equivalence relation a ~ b ⟺ a⁻¹b ∈ H"]
  B --> C["left cosets cover G without overlap"]
  A --> D["h ↦ ah is a bijection H → aH"]
  D --> E["every coset has as many elements as H"]
  C --> F["order of G = number of cosets × order of H"]
  E --> F
  F --> G["Lagrange's theorem"]
  G --> H["the order of an element divides the order of the group"]
  H --> I["Euler's theorem and Fermat's little theorem"]`} />
</Figure>

<Theorem id="thm-lagrange" title="Lagrange's theorem">

Let $G$ be a **finite** group and $H$ a subgroup of $G$. Then

$$
|G| = [G : H] \cdot |H|
$$

In particular $|H|$ divides $|G|$, and the index is given by $[G:H] = |G| / |H|$.

</Theorem>

<Proof of="thm-lagrange">

Since $G$ is finite, there are only finitely many left cosets, being subsets of $G$. List all the distinct ones as $a_1H, a_2H, \ldots, a_rH$, so that $r = [G:H]$.

By <Ref to="lem-coset-basic" />(3) these are pairwise disjoint and their union is all of $G$. For a union of finitely many pairwise disjoint sets, the number of elements adds:

$$
|G| = \sum_{i=1}^{r} |a_iH|
$$

Next, by <Ref to="lem-coset-basic" />(4) we have $|a_iH| = |H|$ for each $i$. Therefore

$$
|G| = \sum_{i=1}^{r} |H| = r \, |H| = [G:H] \cdot |H|
$$

Since $|H| \ge 1$ (because $e \in H$), this equation shows that $|H|$ divides $|G|$. Dividing both sides by $|H|$ gives $[G:H] = |G|/|H|$.

</Proof>

Only two things did any real work in the proof: that the cosets **cover without overlapping** (<Ref to="lem-coset-basic" />(3)), and that every coset has **the same size** (part (4) of the same lemma). The first holds because the three subgroup axioms translate directly into the three axioms of an equivalence relation; the second because left multiplication in a group is a bijection. It is the requirement that inverses exist, built into the definition of a group, that pays off here.

<Remark id="rem-infinite-index">

The index $[G:H]$ is defined even when $G$ is infinite. For example $[\mathbb{Z} : n\mathbb{Z}] = n$ for $n \ge 1$. Indeed, the left cosets are exhausted by the $n$ sets $0 + n\mathbb{Z}, 1 + n\mathbb{Z}, \ldots, (n-1) + n\mathbb{Z}$, and these are distinct: if $i + n\mathbb{Z} = j + n\mathbb{Z}$ with $0 \le i < j \le n-1$, then $n \mid j - i$, which is impossible since $0 < j-i < n$. In this situation the identity $|G| = [G:H]|H|$ degenerates into a product involving infinities and loses its information, whereas the index itself remains a finite and meaningful quantity. When working with infinite groups, it is the index rather than the order that takes the leading role.

</Remark>

<Example id="ex-s3-subgroups" title="Finding all subgroups of S3">

Since $|S_3| = 6$, <Ref to="thm-lagrange" /> tells us that the order of a subgroup is a divisor of $6$, that is, one of $1, 2, 3, 6$. We enumerate by order.

**Order 1.** Since $e \in H$ is required, the only possibility is $H = \{e\}$.

**Order 2.** Write $H = \{e, \sigma\}$ with $\sigma \ne e$. By (S2) we have $\sigma^2 \in H$. If $\sigma^2 = \sigma$, cancellation gives $\sigma = e$, a contradiction; hence $\sigma^2 = e$, so $\sigma$ has order 2. The elements of order 2 in $S_3$ are exactly the three transpositions $(1\,2), (1\,3), (2\,3)$ (the 3-cycles have order 3, as we saw). Conversely each of these gives a subgroup $\langle \sigma \rangle$ of order 2, so there are exactly three subgroups of order 2.

**Order 3.** Since $3$ is prime, <Ref to="cor-prime-order" /> below shows that $H$ is cyclic, generated by an element of order 3. The elements of order 3 in $S_3$ are $(1\,2\,3)$ and $(1\,3\,2)$, but $(1\,3\,2) = (1\,2\,3)^2$, so

$$
\langle (1\,2\,3) \rangle = \langle (1\,3\,2) \rangle = \{e, (1\,2\,3), (1\,3\,2)\} = A_3
$$

and the generated subgroup is the same in both cases. Hence there is exactly one subgroup of order 3, namely $A_3$.

**Order 6.** Only $H = S_3$.

Altogether $S_3$ has exactly six subgroups. In this case every divisor of $6$, namely $1, 2, 3, 6$, is realized as the order of some subgroup. This does not hold in general, however (§8).

</Example>

## 7. Corollaries — from the order of an element to number theory

<Corollary id="cor-element-order" title="The order of an element divides the order of the group">

Let $G$ be a finite group and $a \in G$.

1. $\operatorname{ord}(a)$ divides $|G|$.
2. $a^{|G|} = e$.

</Corollary>

<Proof of="cor-element-order">

**(1)** Since $G$ is finite, <Ref to="prop-cyclic-subgroup" />(1) shows that $n := \operatorname{ord}(a)$ is finite, and part (3) of the same proposition gives $|\langle a \rangle| = n$. As $\langle a \rangle$ is a subgroup of $G$ (<Ref to="def-cyclic-and-order" />), applying <Ref to="thm-lagrange" /> with $H = \langle a \rangle$ shows that $n = |\langle a \rangle|$ divides $|G|$.

**(2)** By (1) there is a positive integer $m$ with $|G| = n m$. Hence

$$
a^{|G|} = a^{nm} = (a^n)^m = e^m = e
$$

</Proof>

This is a practical tool. In a group of order 15, for instance, every element has order $1, 3, 5$, or $15$; there is no element of order 2 and none of order 4. We learn all this merely by counting, without knowing how the group is built.

<Corollary id="cor-prime-order" title="Groups of prime order">

Let $G$ be a finite group, $p$ a prime, and suppose $|G| = p$. Then:

1. The only subgroups of $G$ are $\{e\}$ and $G$.
2. For every $a \in G$ with $a \ne e$ we have $G = \langle a \rangle$. In particular $G$ is cyclic, hence abelian.

</Corollary>

<Proof of="cor-prime-order">

**(1)** If $H \le G$, then $|H|$ divides $p$ by <Ref to="thm-lagrange" />, and since $p$ is prime we get $|H| = 1$ or $|H| = p$. In the first case $e \in H$ forces $H = \{e\}$. In the second case $H \subseteq G$ and both are finite with the same number of elements, so $H = G$.

**(2)** If $a \ne e$, then $\langle a \rangle$ is a subgroup containing $a$, so $\langle a \rangle \ne \{e\}$. By (1) we conclude $\langle a \rangle = G$. The cyclic group $\langle a \rangle$ is abelian since $a^k a^l = a^{k+l} = a^l a^k$.

</Proof>

<Aside type="tip">
<Ref to="cor-prime-order" /> is the doorway to the strong conclusion that a group of prime order has only one possible shape. A group of order 5 and a group of order 101 are both, in essence, the additive group $\mathbb{Z}/p\mathbb{Z}$. Making "in essence the same" precise requires the language of isomorphism (<Ref to="mathematics/algebra/homomorphism-theorems#def-isomorphism" text="isomorphisms and isomorphic groups" />), which we develop in [The isomorphism theorems for groups](/mathematics/algebra/homomorphism-theorems).
</Aside>

Let us now translate the theorem into number theory. First we set up the group in question. Fix $n \ge 2$ and let $\mathbb{Z}/n\mathbb{Z}$ be the set of residue classes modulo $n$, writing $\bar{a} = a + n\mathbb{Z}$. As we saw in §5.1, this is precisely the set of cosets of the subgroup $n\mathbb{Z}$ of the additive group $\mathbb{Z}$. Now put

$$
(\mathbb{Z}/n\mathbb{Z})^{\times} := \{\bar{a} : \gcd(a, n) = 1\}
$$

with multiplication defined by $\bar{a}\,\bar{b} = \overline{ab}$; that this product is independent of the choice of representatives is in <Ref to="mathematics/foundations/equivalence-relations#thm-zmod-ops" text="well-definedness of multiplication of residue classes" />. Three details deserve checking. First, if $a \equiv a' \pmod n$ then $a' = a + kn$, so $\gcd(a', n) = \gcd(a, n)$ and the defining condition does not depend on the representative. Second, if $\gcd(a,n) = \gcd(b,n) = 1$ then $\gcd(ab, n) = 1$, so the set is closed under multiplication. Third, if $\gcd(a,n) = 1$ then Bézout's identity provides integers $x, y$ with $ax + ny = 1$, which means $\bar{a}\bar{x} = \bar{1}$, so inverses exist (and the same identity gives $\gcd(x,n) = 1$, so $\bar x$ really is an element). Hence $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is a group. Its order is the number of $a$ with $1 \le a \le n$ that are coprime to $n$, that is, the value $\varphi(n)$ of Euler's totient function.

<Theorem id="thm-euler-fermat" title="Euler's theorem and Fermat's little theorem">

1. (Euler) Let $n \ge 2$ and let $a$ be an integer with $\gcd(a, n) = 1$. Then $a^{\varphi(n)} \equiv 1 \pmod{n}$.
2. (Fermat) Let $p$ be a prime. If $p \nmid a$ then $a^{p-1} \equiv 1 \pmod{p}$; moreover $a^{p} \equiv a \pmod{p}$ for every integer $a$.

</Theorem>

<Proof of="thm-euler-fermat">

**(1)** The group $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$ is finite of order $\varphi(n)$. Since $\gcd(a,n) = 1$ we have $\bar{a} \in G$, so <Ref to="cor-element-order" />(2) gives $\bar{a}^{\varphi(n)} = \bar{1}$, that is, $a^{\varphi(n)} \equiv 1 \pmod{n}$.

**(2)** For a prime $p$, all of $1, 2, \ldots, p-1$ are coprime to $p$, so $\varphi(p) = p - 1$. The condition $p \nmid a$ is equivalent to $\gcd(a,p) = 1$, so (1) gives $a^{p-1} \equiv 1 \pmod p$. Multiplying both sides by $a$ gives $a^p \equiv a \pmod p$. If instead $p \mid a$, then $a \equiv 0$ and so $a^p \equiv 0 \equiv a \pmod p$. Hence $a^p \equiv a$ holds for every integer $a$.

</Proof>

That Fermat's little theorem is a one-line consequence of "$a^{|G|} = e$ in a finite group" illustrates well what group theory gained by abstraction. The original statement is a theorem about congruences of integers, yet the only properties used in the proof were finiteness, associativity, and the existence of inverses.

<Example id="ex-modular-power" title="The remainder of 7 to the 2026th power modulo 45">

Let $n = 45 = 3^2 \cdot 5$. By multiplicativity of Euler's function,

$$
\varphi(45) = \varphi(9)\varphi(5) = (9 - 3)(5 - 1) = 6 \cdot 4 = 24
$$

Since $\gcd(7, 45) = 1$, <Ref to="thm-euler-fermat" />(1) gives $7^{24} \equiv 1 \pmod{45}$. As $2026 = 24 \cdot 84 + 10$,

$$
7^{2026} = (7^{24})^{84} \cdot 7^{10} \equiv 7^{10} \pmod{45}
$$

The rest is repeated squaring:

$$
\begin{aligned}
7^2 &= 49 = 45 + 4 \equiv 4, \\
7^4 &\equiv 4^2 = 16, \\
7^8 &\equiv 16^2 = 256 = 5 \cdot 45 + 31 \equiv 31, \\
7^{10} &= 7^8 \cdot 7^2 \equiv 31 \cdot 4 = 124 = 2 \cdot 45 + 34 \equiv 34 .
\end{aligned}
$$

So the remainder of $7^{2026}$ on division by $45$ is $34$.

**Computing the order shortens the work.** By <Ref to="cor-element-order" />(1), the order of $\bar 7$ divides $24$. Now

$$
7^{12} = (7^6)^2 \equiv 19^2 = 361 = 8 \cdot 45 + 1 \equiv 1 \pmod{45}
$$

where along the way we used $7^6 = 7^4 \cdot 7^2 \equiv 16 \cdot 4 = 64 \equiv 19$. By <Ref to="prop-cyclic-subgroup" />(2), $\operatorname{ord}(\bar 7)$ divides $12$, so it is one of $1, 2, 3, 4, 6, 12$. We rule out the proper divisors in turn:

$$
7^1 \equiv 7, \quad 7^2 \equiv 4, \quad 7^3 = 343 = 7 \cdot 45 + 28 \equiv 28, \quad 7^4 \equiv 16, \quad 7^6 \equiv 19
$$

None of these is $1$, so $\operatorname{ord}(\bar 7) = 12$. Indeed $12 \mid 24 = \varphi(45)$, consistent with <Ref to="cor-element-order" />(1). Since $2026 = 12 \cdot 168 + 10$, this route also gives $7^{2026} \equiv 7^{10} \equiv 34$, the same answer.

</Example>

## 8. The converse is false

Lagrange's theorem says that if a subgroup exists, its order divides $|G|$. Conversely, does a subgroup of order $d$ necessarily exist whenever $d$ divides $|G|$? For $S_3$ in <Ref to="ex-s3-subgroups" /> that was the case. In general, however, it fails. The smallest counterexample is $A_4$.

<Proposition id="prop-a4-no-order-six" title="A counterexample to the converse of Lagrange's theorem">

The alternating group $A_4$ has order 12 but has no subgroup of order 6. Hence the assertion "if $d$ divides $|G|$ then there is a subgroup of order $d$" is false.

</Proposition>

<Proof of="prop-a4-no-order-six">

We first classify the elements of $A_4$. We have $|A_4| = 4!/2 = 12$. The even permutations split into: the identity (1 element); 3-cycles (choose 3 letters out of $\{1,2,3,4\}$ in $\binom{4}{3} = 4$ ways, and for each choice there are the two cycles $(a\,b\,c)$ and $(a\,c\,b)$, giving 8 in all); and products of two disjoint transpositions ($(1\,2)(3\,4)$, $(1\,3)(2\,4)$, $(1\,4)(2\,3)$, that is 3 elements). The total is $1 + 8 + 3 = 12$, so the list is complete. The key point is that **there are 8 three-cycles**.

**Step 1.** In general, if $G$ is a group and $H$ a subgroup with $[G : H] = 2$, then $g^2 \in H$ for every $g \in G$.

To see this: if $g \in H$ then $g^2 \in H$ by (S2). So suppose $g \notin H$. Since the index is 2 there are exactly two left cosets, one of which is $eH = H$. By <Ref to="lem-coset-basic" />(1) and (2) we have $g \in gH$ and $gH \ne H$ (for $gH = H$ would give $g \in H$, contrary to assumption), so the two cosets are precisely $H$ and $gH$. They are disjoint with union $G$, hence $gH = G \setminus H$.

Now suppose, for contradiction, that $g^2 \notin H$. Then $g^2 \in G \setminus H = gH$, so $g^2 = gh$ for some $h \in H$. Cancellation gives $g = h \in H$, contradicting $g \notin H$. Hence $g^2 \in H$.

**Step 2.** Suppose $H \le A_4$ with $|H| = 6$. By <Ref to="thm-lagrange" />, $[A_4 : H] = 12/6 = 2$.

Let $\sigma$ be any 3-cycle. Then $\sigma^3 = e$, so $\sigma^4 = \sigma$. Applying Step 1 with $g = \sigma^2$ gives $(\sigma^2)^2 = \sigma^4 = \sigma \in H$. As $\sigma$ was arbitrary, all 8 three-cycles lie in $H$. Together with $e \in H$ this forces $|H| \ge 9$, contradicting $|H| = 6$.

Hence no subgroup of order 6 exists.

</Proof>

<Remark id="rem-partial-converse">

The converse is not entirely lost. The following partial converses are known.

| Statement | Content |
|---|---|
| Cauchy's theorem | If a prime $p$ divides $\lvert G\rvert$, there is an element of order $p$ |
| Sylow's theorems | If $p^k$ is the largest power of $p$ dividing $\lvert G\rvert$, there is a subgroup of order $p^k$ |
| Finite abelian groups | If $d$ divides $\lvert G\rvert$, there is a subgroup of order $d$ |

For $A_4$ we have $|A_4| = 12 = 2^2 \cdot 3$, so Sylow's theorems guarantee a subgroup of order 4 (indeed $\{e, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3)\}$ is one) and a subgroup of order 3, but say nothing about $6 = 2 \cdot 3$, which is not a prime power. This is consistent with <Ref to="prop-a4-no-order-six" />. Proofs of these results lie beyond the scope of this article; see Chapter 4 of Yukie's *Daisūgaku 1* or Chapter 4 of Dummit–Foote in the references.

</Remark>

We have now seen how a subgroup, a "static" substructure, gets translated into the language of numbers by way of the partition into cosets. The next step is to ask whether the partition $G/H$ can itself be made into a group. The condition for this is exactly the agreement of left and right cosets (<Ref to="mathematics/algebra/quotient-groups#thm-normality-criterion" text="a necessary and sufficient condition for the product of cosets to be well defined" />), and it is the subject of [Normal subgroups and quotient groups](/en/mathematics/algebra/quotient-groups).

## 9. Exercises

<Exercise id="exr-intersection-union" difficulty="Easy">

Let $G$ be a group and $H, K \le G$.

1. Show that $H \cap K \le G$.
2. Show that $H \cup K \le G$ holds if and only if $H \subseteq K$ or $K \subseteq H$.

<Solution>

**(1)** We use <Ref to="prop-subgroup-criterion" />(1). Since $e \in H$ and $e \in K$, we have $e \in H \cap K$, so $H \cap K \ne \emptyset$. Let $a, b \in H \cap K$. Then $a, b \in H$ and $H \le G$ give $ab^{-1} \in H$, and similarly $ab^{-1} \in K$. Hence $ab^{-1} \in H \cap K$, and $H \cap K \le G$.

**(2)** Sufficiency first. If $H \subseteq K$ then $H \cup K = K$, which is a subgroup, so $H \cup K \le G$. If $K \subseteq H$ then $H \cup K = H$, and again $H \cup K \le G$.

For necessity we argue by contraposition. Assume $H \not\subseteq K$ and $K \not\subseteq H$, and show that $H \cup K$ is not a subgroup. By assumption we may pick $h \in H \setminus K$ and $k \in K \setminus H$. If $H \cup K \le G$, then (S2) gives $hk \in H \cup K$.

- If $hk \in H$, then $h^{-1} \in H$ by (S3), so $k = h^{-1}(hk) \in H$, contradicting $k \notin H$.
- If $hk \in K$, then $k^{-1} \in K$, so $h = (hk)k^{-1} \in K$, contradicting $h \notin K$.

Both cases give a contradiction, so $H \cup K$ is not a subgroup.

This result is also used in the form: a group is never the union of two proper subgroups.

</Solution>
</Exercise>

<Exercise id="exr-order-four" difficulty="Standard">

Let $G$ be a group of order 4. Show that $G$ is abelian, and moreover that one of the following holds.

- $G$ has an element of order 4 and is the cyclic group $\langle a \rangle$.
- $G = \{e, a, b, ab\}$ with $a^2 = b^2 = e$ and $ab = ba$ (the Klein four-group).

<Solution>

By <Ref to="cor-element-order" />(1), the order of each element of $G$ divides $4$, hence is $1, 2$, or $4$. The only element of order 1 is $e$ (since $\operatorname{ord}(x) = 1$ means $x = x^1 = e$).

**Case 1: there is an element $a$ of order 4.** By <Ref to="prop-cyclic-subgroup" />(3) we have $|\langle a \rangle| = 4 = |G|$, and since $\langle a \rangle \subseteq G$ with both finite, $G = \langle a \rangle$. A cyclic group is abelian because $a^k a^l = a^{k+l} = a^l a^k$.

**Case 2: there is no element of order 4.** Then every element other than $e$ has order 2, so $x^2 = e$ for all $x \in G$ (this also holds for $x = e$). Equivalently $x^{-1} = x$. For any $a, b \in G$ we have $ab \in G$, so $(ab)^2 = e$, and therefore

$$
ab = (ab)^{-1} = b^{-1}a^{-1} = ba
$$

so $G$ is abelian. Here we used the reversal rule $(ab)^{-1} = b^{-1}a^{-1}$.

Now we pin down the structure. Choose an element $a \ne e$, and then an element $b$ not in $\{e, a\}$. Consider $ab$: if $ab = e$ then $b = a^{-1} = a$, a contradiction; if $ab = a$ then cancellation gives $b = e$, a contradiction; if $ab = b$ then $a = e$, a contradiction. So $ab$ differs from each of $e, a, b$, and since $|G| = 4$ we get $G = \{e, a, b, ab\}$. The relations $a^2 = b^2 = e$ together with commutativity determine the whole multiplication table.

</Solution>
</Exercise>

<Exercise id="exr-index-tower" difficulty="Hard">

Let $G$ be a group and $K \le H \le G$ (that is, $K$ is a subgroup of $H$ and $H$ is a subgroup of $G$).

1. Show that $[G : K] = [G : H]\,[H : K]$ when $G$ is finite.
2. Show that if $G$ is not assumed finite but $[G:H]$ and $[H:K]$ are both finite, then $[G:K] = [G:H][H:K]$.

<Solution>

**(1)** From $K \le H$ and $H \le G$ we also get $K \le G$ (being a subgroup amounts to checking (S1), (S2), (S3), which follows at once from $K$ being closed under the operation of $G$). Applying <Ref to="thm-lagrange" /> three times,

$$
[G:K] = \frac{|G|}{|K|} = \frac{|G|}{|H|} \cdot \frac{|H|}{|K|} = [G:H]\,[H:K]
$$

where we used $|H| \ne 0$ along the way.

**(2)** Finiteness is unavailable, so we construct representatives directly. Let $[G:H] = r$ and $[H:K] = s$. Choose a complete set of representatives $a_1, \ldots, a_r$ for the left cosets of $H$ in $G$ (so $G = a_1H \sqcup \cdots \sqcup a_rH$) and a complete set of representatives $b_1, \ldots, b_s$ for the left cosets of $K$ in $H$ (so $H = b_1K \sqcup \cdots \sqcup b_sK$, with $b_j \in H$). We show that the $rs$ elements $a_ib_j$ form a complete set of representatives for the left cosets of $K$ in $G$.

**They cover.** Let $g \in G$. For some $i$ we have $g \in a_iH$, so $g = a_ih$ with $h \in H$. For some $j$ we have $h \in b_jK$, so $h = b_jk$ with $k \in K$. Hence $g = a_ib_jk \in a_ib_jK$.

**They are distinct.** Suppose $a_ib_jK = a_{i'}b_{j'}K$. By <Ref to="lem-coset-basic" />(2) there is a $k \in K$ with $a_ib_jk = a_{i'}b_{j'}$. Since $b_j, k \in H$ we have $b_jk \in H$, so $a_{i'} = a_i(b_jk) \in a_iH$. By <Ref to="lem-coset-basic" />(2) again, $a_{i'}H = a_iH$, and the choice of representatives forces $i = i'$.

Then $a_ib_jk = a_ib_{j'}$, so cancellation gives $b_jk = b_{j'}$, that is, $b_{j'} \in b_jK$. Once more by <Ref to="lem-coset-basic" />(2) we get $b_jK = b_{j'}K$, and the choice of representatives forces $j = j'$.

Hence there are exactly $rs$ left cosets of $K$ in $G$, and $[G:K] = rs = [G:H][H:K]$.

</Solution>
</Exercise>

<Exercise id="exr-product-formula" difficulty="Hard">

Let $G$ be a group, let $H, K$ be **finite** subgroups of $G$, and set $HK := \{hk : h \in H,\ k \in K\}$ (note that $HK$ need not be a subgroup). Show that

$$
|HK| = \frac{|H|\,|K|}{|H \cap K|}
$$

Then deduce that if $|H| = |K| = 6$ and $|G| = 24$, then $H \cap K \ne \{e\}$.

<Solution>

**First part.** Consider the map $f : H \times K \to HK$, $f(h,k) = hk$. By the definition of $HK$, this $f$ is surjective. Hence summing the sizes of the fibres $f^{-1}(x)$ over all $x \in HK$ gives $|H||K|$. So it suffices to show that each fibre has size $|H \cap K|$, from which $|H||K| = |HK| \cdot |H \cap K|$ follows.

Write $x = hk$ with $h \in H$ and $k \in K$, and put $D := H \cap K$; by <Ref to="exr-intersection-union" />(1) we have $D \le G$.

First, for any $d \in D$ we have $(hd, d^{-1}k) \in H \times K$ (since $d \in H$ gives $hd \in H$, and $d^{-1} \in K$ gives $d^{-1}k \in K$), and $f(hd, d^{-1}k) = h d d^{-1} k = hk = x$. Moreover $d \ne d'$ implies $hd \ne hd'$ by cancellation, so these give $|D|$ distinct elements of the fibre.

Conversely, suppose $f(h', k') = x$, that is, $h'k' = hk$. Multiplying on the left by $h^{-1}$ and on the right by $(k')^{-1}$ gives

$$
h^{-1}h' = k (k')^{-1}
$$

The left-hand side lies in $H$ and the right-hand side in $K$, so this common value, call it $d$, lies in $H \cap K = D$. From $h^{-1}h' = d$ we get $h' = hd$, and from $k(k')^{-1} = d$ we get $k' = d^{-1}k$, so $(h', k')$ has exactly the form counted above.

Therefore $|f^{-1}(x)| = |D|$ for every $x \in HK$, and

$$
|H||K| = \sum_{x \in HK} |f^{-1}(x)| = |HK| \cdot |H \cap K|
$$

Dividing by $|H \cap K| \ge 1$ gives the stated formula.

**Second part.** Suppose $|H| = |K| = 6$, $|G| = 24$, and assume $H \cap K = \{e\}$. The formula above gives

$$
|HK| = \frac{6 \cdot 6}{1} = 36
$$

But $HK \subseteq G$ forces $|HK| \le |G| = 24$, a contradiction. Hence $H \cap K \ne \{e\}$.

Using <Ref to="thm-lagrange" /> further, $H \cap K$ is a subgroup of $H$, so $|H \cap K|$ divides $6$; being different from $1$, it is $2, 3$, or $6$. In particular $|H\cap K| \ge 2$ yields $|HK| \le 18$.

</Solution>
</Exercise>

## References

- Kazuo Matsuzaka, *Daisūkei Nyūmon*, Iwanami Shoten, 1976 (in Japanese) — Chapter 2 treats groups, subgroups, cosets, and Lagrange's theorem carefully, with a wealth of concrete examples. A good first book for beginners.
- Akihiko Yukie, *Daisūgaku 1: Gunron Nyūmon*, Nippon Hyoron Sha, 2010 (in Japanese) — Chapter 2 covers subgroups and cosets, Chapter 4 the Sylow theorems. The partial converses mentioned in <Ref to="rem-partial-converse" /> are found here.
- Toshiyuki Katsura, *Daisūgaku I: Gun to Kan*, University of Tokyo Press, 2004 (in Japanese) — a concise textbook on the foundations of group theory; Chapter 1 contains subgroups and Lagrange's theorem.
- D. S. Dummit and R. M. Foote, *Abstract Algebra*, 3rd ed., Wiley, 2004 — Chapter 2 on subgroups, Chapter 3 on cosets and Lagrange's theorem, Chapter 4 on the Sylow theorems. The exercise sets are exceptionally rich.
- J. J. Rotman, *An Introduction to the Theory of Groups*, 4th ed., Graduate Texts in Mathematics 148, Springer, 1995 — Chapter 2 develops cosets and the index in general, including the treatment of the index for infinite groups.
- J.-L. Lagrange, "Réflexions sur la résolution algébrique des équations", *Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin*, 1770–1771 — the original paper from which the theorem takes its name.

## Appendix: On the name "Lagrange's theorem"

**Lagrange himself knew nothing of groups.** In the paper cited above, published in 1770–71, what Lagrange investigated was a unified understanding of methods for solving algebraic equations: why are equations of degree 3 and 4 solvable while those of degree 5 are not? His apparatus was to count, for a rational function $f(x_1, \ldots, x_n)$ of the roots $x_1, \ldots, x_n$ of an equation, how many distinct values $f$ takes as the variables are permuted. He found that this number divides $n!$.

Translated into modern language: the permutations fixing $f$ form a subgroup $H$ of $S_n$, the number of distinct values taken by $f$ is exactly the index $[S_n : H]$, and by <Ref to="thm-lagrange" /> this divides $|S_n| = n!$. But in Lagrange's day there was no notion of a subgroup, let alone of a group. What he handled were concrete permutations and concrete rational functions, not a general theorem about abstract groups.

**The abstraction took more than half a century.** Cauchy systematized the theory of permutations from 1815 onwards, Galois discovered the correspondence between solvability of equations and groups in the 1830s, and Jordan brought the theory of permutation groups together in his *Traité des substitutions* of 1870. Only at the end of the nineteenth century did the axioms for an abstract group settle into their present form, allowing the statement "the order of a subgroup divides the order of the group" to be made for an arbitrary finite group.

This history is a fine illustration of what abstraction delivers, I think. The phenomenon Lagrange found through individual computations was compressed, once the framework of a group was available, into the two pages of <Ref to="lem-coset-basic" /> and <Ref to="thm-lagrange" />, and at the same time became applicable in identical form to number theory (<Ref to="thm-euler-fermat" />) and to the symmetries of geometric figures. The name preserves the discoverer, but the shape of the theorem was fixed by the abstraction that came after.