--- title: Cosets, Lagrange, and Normal Subgroups module: Subgroups and Quotients moduleNumber: 3 lessonNumber: 4 order: 304 summary: > The left cosets of a subgroup partition a group into equal-sized blocks, so the order of a subgroup divides the order of the group: Lagrange's theorem. When the blocks can be multiplied consistently — exactly when the subgroup is normal — they form the quotient group $G/N$. Fermat's and Euler's theorems fall out as index computations. topics: [Subgroups and Quotients] sources: - book: Dummit & Foote ref: "Ch. 3 Quotient Groups; §3.1 Definitions and Examples, §3.2 More on Cosets and Lagrange's Theorem" - book: Judson ref: "Ch. 6 Cosets and Lagrange; §6.1 Cosets, §6.2 Lagrange's Theorem, §6.3 Fermat's and Euler's Theorems" draft: false --- Subgroups do more than sit inside a group; each one slices the group into translates of itself. Those translates, the cosets, are all the same size, and that single fact is the most-used counting theorem in finite group theory. When the cosets can be multiplied among themselves, they form a new, smaller group, the quotient. ## Cosets and the partition of a group > **Definition (Coset).** For $N \le G$ and $g \in G$, the **left coset** is > $gN = \{ gn \mid n \in N \}$ and the **right coset** is > $Ng = \{ ng \mid n \in N \}$. Any element of a coset is a **representative** > of it. In additive notation, $g + N$ and $N + g$. Left cosets carve $G$ into disjoint blocks that cover it. > **Theorem (Cosets partition $G$).** The left cosets of $N$ in $G$ form a > partition of $G$. For $u, v \in G$, $uN = vN$ if and only if $v^{-1}u \in N$; > equivalently, $u$ and $v$ represent the same coset. Every $g$ lies in its own coset $gN$ (since $1 \in N$), so the cosets cover $G$. If two cosets share an element $x = un = vm$, then for any $ut \in uN$ one writes $ut = v(mn^{-1}t) \in vN$, and symmetrically, so the two cosets coincide. Distinct cosets are therefore disjoint.[^df-part] The equivalence $uN = vN \iff v^{-1}u \in N$ is the practical membership test. $$ % caption: The left cosets of $N$ tile $G$ into disjoint blocks, each a % bijective translate of $N$ and so each of size $|N|$. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \draw[draw=black] (0,0) rectangle (8.4,1.5); \foreach \i in {1,...,5} \draw[black] (\i*1.4,0) -- (\i*1.4,1.5); \fill[acc!16] (0,0) rectangle (1.4,1.5); \node at (0.7,0.75) {$N$}; \node at (2.1,0.75) {$g_1 N$}; \node at (3.5,0.75) {$g_2 N$}; \node at (4.9,0.75) {$g_3 N$}; \node at (6.3,0.75) {$g_4 N$}; \node at (7.7,0.75) {$g_5 N$}; \draw[->, acc, thick] (0.7,-0.35) -- node[below, font=\scriptsize]{translate by $g_1$} (2.1,-0.35); \draw[black] (0,1.75) -- (8.4,1.75); \draw[black] (0,1.65) -- (0,1.85); \draw[black] (8.4,1.65) -- (8.4,1.85); \node[black, font=\scriptsize] at (4.2,2.1) {$G$, all blocks the size of $N$}; \end{tikzpicture} $$ Each coset $gN$ has exactly $|N|$ elements, because $n \mapsto gn$ is a bijection from $N$ onto $gN$ (left cancellation makes it injective). Equal-size blocks partitioning $G$ is all Lagrange's theorem needs. Everything above holds verbatim for right cosets, which partition $G$ as well. The two partitions differ in general — for a non-normal subgroup some left coset is not a right coset for any representative — but they always have the same number of blocks: $x \mapsto x^{-1}$ maps each left coset $gN$ onto the right coset $Ng^{-1}$, a bijection between the two collections. So "index" is unambiguous. These notes work with left cosets throughout.[^df-lr] ## Lagrange's theorem > **Theorem (Lagrange).** If $G$ is finite and $H \le G$, then $|H|$ divides > $|G|$, and the number of left cosets of $H$ in $G$ is $|G|/|H|$. If there are $k$ cosets, each of size $|H| = n$, and they partition $G$, then $|G| = kn$, so $|H| \mid |G|$ and $k = |G|/|H|$.[^df-lag] The number $k$ is named. > **Definition (Index).** The **index** $[G : H]$ is the number of left cosets > of $H$ in $G$. For finite $G$, $[G : H] = |G|/|H|$. Three consequences are immediate and constant tools. - **Order divides.** For $x \in G$, $|x| = |\langle x \rangle|$ divides $|G|$, so $x^{|G|} = 1$ for every $x$. - **Prime order forces cyclic.** If $|G| = p$ is prime, any nonidentity $x$ generates a subgroup of order dividing $p$ and larger than $1$, so $G = \langle x \rangle \cong \mathbb{Z}/p\mathbb{Z}$. - **A product-size formula.** For finite subgroups $H, K$, $|HK| = \dfrac{|H|\,|K|}{|H \cap K|}$, where $HK = \{hk\}$ need not be a subgroup. The partition is concrete for $S_3$ and the order-$2$ subgroup $H = \langle (1\,2) \rangle = \{1, (1\,2)\}$. The three left cosets each hold two of the six elements. $$ % caption: The six elements of $S_3$ split into three left cosets of % $H = \{1, (1\,2)\}$, each of size two, so $[S_3 : H] = 3$. \begin{tikzpicture}[>=stealth, font=\footnotesize, cell/.style={draw, minimum width=20mm, minimum height=8mm, font=\scriptsize}] \definecolor{acc}{HTML}{4A6FA5} \node[cell, fill=acc!14, draw=acc] (a1) at (0,0) {$1$}; \node[cell, fill=acc!14, draw=acc] (a2) at (0,-0.8){$(1\,2)$}; \node[cell] (b1) at (2.4,0) {$(1\,3)$}; \node[cell] (b2) at (2.4,-0.8){$(1\,2\,3)$}; \node[cell] (c1) at (4.8,0) {$(2\,3)$}; \node[cell] (c2) at (4.8,-0.8){$(1\,3\,2)$}; \node[font=\scriptsize, acc, anchor=south] at (0,0.35) {$H$}; \node[font=\scriptsize, black, anchor=south] at (2.4,0.35) {$(1\,3)H$}; \node[font=\scriptsize, black, anchor=south] at (4.8,0.35) {$(2\,3)H$}; \end{tikzpicture} $$ The converse of Lagrange is false: a divisor of $|G|$ need not be the order of a subgroup. The alternating group $A_4$ has order $12$ but no subgroup of order $6$: such a subgroup would have index $2$, forcing $g^2 \in H$ for every $g \in A_4$, but $A_4$ has eight elements of order $3$ and each is the square of its own square, more than a subgroup of order $6$ can hold.[^df-conv] Two partial converses hold and are proved later: **Cauchy's theorem**, that a prime $p \mid |G|$ forces an element (hence a subgroup) of order $p$, and **Sylow's theorem**, giving subgroups of every prime-power order dividing $|G|$. ### Products of subgroups The set $HK = \{ hk \mid h \in H, k \in K \}$ collects all products across two subgroups. Counting its elements is a coset argument: $HK$ is a union of cosets $hK$, and $h_1 K = h_2 K$ exactly when $h_2^{-1} h_1 \in H \cap K$, so the number of distinct cosets is $[H : H \cap K]$ and $$ |HK| \;=\; \frac{|H|\,|K|}{|H \cap K|}. $$ The formula holds whether or not $HK$ is a subgroup, and often proves it is not: in $S_3$ with $H = \langle (1\,2) \rangle$ and $K = \langle (2\,3) \rangle$, $|HK| = \tfrac{2 \cdot 2}{1} = 4$, which does not divide $6$, so $HK$ is not a subgroup (and, as a byproduct, $\langle (1\,2), (2\,3) \rangle = S_3$). The clean criterion: $HK$ is a subgroup if and only if $HK = KH$, which holds in particular whenever $H \le N_G(K)$ — so a product with a **normal** subgroup is always a subgroup.[^df-hk] ## Normal subgroups and well-defined coset multiplication The goal is to multiply cosets: define $(uN)(vN) = (uv)N$. This depends on choosing representatives, and in general the choice matters. The operation is consistent exactly for a distinguished class of subgroups. > **Proposition.** The rule $uN \cdot vN = (uv)N$ on left cosets of $N$ is well > defined if and only if $gng^{-1} \in N$ for all $g \in G$ and $n \in N$. If the rule is well defined, comparing the products of the reps $1, n$ of $N$ and $g^{-1}, g^{-1}$ of $g^{-1}N$ forces $gng^{-1} \in N$. Conversely, that condition lets one push a representative change from one factor through the other and land in the same coset.[^df-well] The condition names the subgroup. > **Definition (Normal subgroup).** $N \le G$ is **normal**, written > $N \trianglelefteq G$, if $gNg^{-1} = N$ for all $g \in G$ (equivalently > $gNg^{-1} \subseteq N$ for all $g$). The element $gng^{-1}$ is the > **conjugate** of $n$ by $g$. Several conditions on $N$ are the same statement, tying normality back to the [normalizer](/abstract-algebra/subgroups-and-quotients/subgroups-and-substructures). > **Theorem (Characterizations of normality).** For $N \le G$, the following > are equivalent: (1) $N \trianglelefteq G$; (2) $N_G(N) = G$; (3) $gN = Ng$ for > all $g \in G$; (4) coset multiplication makes the left cosets a group; > (5) $gNg^{-1} \subseteq N$ for all $g$. $$ % caption: Coset multiplication by representatives is consistent when $N$ is % normal (left) and inconsistent otherwise (right), where two representatives of % one coset land in different product cosets. \begin{tikzpicture}[>=stealth, font=\footnotesize, bx/.style={draw, minimum width=14mm, minimum height=7mm, font=\scriptsize}] \definecolor{acc}{HTML}{4A6FA5} \definecolor{wrn}{HTML}{B0413E} % left: normal, consistent \node[font=\scriptsize, acc] at (0,2.1) {$N$ normal}; \node[bx] (u) at (-1.0,1.3) {$u N$}; \node[bx] (v) at (1.0,1.3) {$v N$}; \node[bx, fill=acc!12, draw=acc] (p) at (0,0.1) {$uv N$}; \draw[->, black] (u) -- (p); \draw[->, black] (v) -- (p); \node[font=\scriptsize, black] at (0,-0.6) {any reps give this block}; % right: non-normal, inconsistent \begin{scope}[xshift=6.2cm] \node[font=\scriptsize, wrn] at (0,2.1) {$H$ not normal}; \node[bx] (u2) at (-1.0,1.3) {$u H$}; \node[bx] (v2) at (1.0,1.3) {$v H$}; \node[bx] (p1) at (-0.9,0.1) {block $X$}; \node[bx] (p2) at (1.1,0.1) {block $Y$}; \draw[->, wrn] (u2) -- (p1); \draw[->, wrn] (v2) -- (p2); \node[font=\scriptsize, wrn] at (0,-0.6) {reps disagree}; \end{scope} \end{tikzpicture} $$ For the non-normal $H = \langle (1\,2) \rangle$ in $S_3$, the cosets $1H$ and $(1\,3)H$ have no consistent product: the representatives $1$ and $(1\,2)$ of $1H$ give $1 \cdot (1\,3) = (1\,3)$ and $(1\,2)(1\,3) = (1\,3\,2)$, which lie in different cosets. So the "quotient" of $S_3$ by $H$ is not a group.[^df-s3] Normal subgroups are precisely the kernels of homomorphisms. > **Theorem (Normal $=$ kernel).** $N \trianglelefteq G$ if and only if $N$ is > the kernel of some homomorphism. For $N \trianglelefteq G$, the **natural > projection** $\pi : G \to G/N$, $\pi(g) = gN$, is a surjective homomorphism > with kernel $N$. A kernel is normal because $\varphi(gng^{-1}) = \varphi(g)\varphi(g)^{-1} = 1$; conversely, the projection $\pi$ realizes any normal $N$ as a kernel.[^df-ker] Two shortcuts make normality cheap to check: it suffices to test conjugates of a generating set of $N$ by a generating set of $G$, and any subgroup of **index 2** is automatically normal, since the two left cosets ($H$ and its complement) must coincide with the two right cosets. ## The quotient group > **Definition (Quotient group).** For $N \trianglelefteq G$, the **quotient > group** $G/N$ has the left cosets of $N$ as elements, with > $(uN)(vN) = (uv)N$. Its identity is $N$, the inverse of $gN$ is $g^{-1}N$, and > $|G/N| = |G|/|N|$ when $G$ is finite. The quotient collapses $N$ to a point and translates that collapse across all of $G$. A small case: in $\mathbb{Z}/6\mathbb{Z}$ take $N = \langle 3 \rangle = \{0, 3\}$. Its three cosets $\{0,3\}$, $\{1,4\}$, $\{2,5\}$ multiply (here, add) as representatives, and the quotient is a group of order $3$. $$ % caption: The quotient $(\mathbb{Z}/6\mathbb{Z}) / \langle 3 \rangle$: three % cosets $A, B, C$ add as their representatives, giving a Cayley table % isomorphic to $\mathbb{Z}/3\mathbb{Z}$. \begin{tikzpicture}[>=stealth, font=\footnotesize, hd/.style={draw, minimum size=9mm, fill=acc!12, font=\scriptsize}, cl/.style={draw, minimum size=9mm, font=\scriptsize}] \definecolor{acc}{HTML}{4A6FA5} \node[hd, draw=acc] at (0,0) {$+$}; \node[hd] at (1,0) {$A$}; \node[hd] at (2,0) {$B$}; \node[hd] at (3,0) {$C$}; \node[hd] at (0,-1) {$A$}; \node[hd] at (0,-2) {$B$}; \node[hd] at (0,-3) {$C$}; \node[cl] at (1,-1) {$A$}; \node[cl] at (2,-1) {$B$}; \node[cl] at (3,-1) {$C$}; \node[cl] at (1,-2) {$B$}; \node[cl] at (2,-2) {$C$}; \node[cl] at (3,-2) {$A$}; \node[cl] at (1,-3) {$C$}; \node[cl] at (2,-3) {$A$}; \node[cl] at (3,-3) {$B$}; \node[black, align=left, font=\scriptsize, anchor=west] at (3.9,-1.5) {$A$: $0$, $3$\\$B$: $1$, $4$\\$C$: $2$, $5$}; \end{tikzpicture} $$ A structural example: $D_8 / Z(D_8)$ with $Z(D_8) = \langle r^2 \rangle$. Each coset $gZ = \{g, gr^2\}$ has two elements, so there are four cosets. Every nonidentity coset squares to the identity coset, so the quotient has no element of order $4$ and is the Klein four-group: $D_8/Z(D_8) \cong V_4$.[^df-d8] ## Application: Fermat and Euler Lagrange, read inside the group of units $(\mathbb{Z}/n\mathbb{Z})^\times$, gives two number-theoretic theorems at once. The order of that group is $\varphi(n)$, so $x^{\varphi(n)} = 1$ for every unit. > **Theorem (Euler).** If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 > \pmod{n}$. This is $x^{|G|} = 1$ applied to $G = (\mathbb{Z}/n\mathbb{Z})^\times$ and $x = \bar{a}$.[^ju-fe] Specializing to a prime $n = p$, where $\varphi(p) = p - 1$, gives the classical case. > **Theorem (Fermat's Little Theorem).** For a prime $p$ and $p \nmid a$, > $a^{p-1} \equiv 1 \pmod{p}$; and $b^p \equiv b \pmod{p}$ for every integer $b$. No number theory beyond the definition of $\varphi$ enters: both are the statement that an element's order divides the group's order. > **Worked example.** Find the last two digits of $3^{100}$. The last two digits > of an integer are its residue modulo $100$. Since $\gcd(3, 100) = 1$, the class > $\bar{3}$ lies in $(\mathbb{Z}/100\mathbb{Z})^\times$, whose order is > $\varphi(100) = \varphi(4)\,\varphi(25) = 2 \cdot 20 = 40$. Euler gives > $3^{40} \equiv 1 \pmod{100}$, so exponents reduce modulo $40$: > $$ > 3^{100} = 3^{40 \cdot 2 + 20} \equiv 3^{20} > = (3^4)^5 = 81^5 \equiv 81^2 \cdot 81^2 \cdot 81 > \equiv 61 \cdot 61 \cdot 81 \equiv 21 \cdot 81 \equiv 1 \pmod{100}, > $$ > so $3^{100}$ ends in $\dots 01$. A $48$-digit number is resolved by one group order and a handful of squarings: the [repeated-squares](/abstract-algebra/subgroups-and-quotients/cyclic-groups) ladder, with Euler shrinking the exponent before the ladder even starts. [^df-part]: **Dummit & Foote**, _Abstract Algebra_, §3.1, Proposition 4 — left cosets partition $G$, with $uN = vN \iff v^{-1}u \in N$. [^df-lr]: **Dummit & Foote**, §3.2 and Exercise 12 — right cosets satisfy the same combinatorics, and $x \mapsto x^{-1}$ gives a bijection between left and right cosets. [^df-lag]: **Dummit & Foote**, §3.2, Theorem 8 (Lagrange) — $|H|$ divides $|G|$ and $[G:H] = |G|/|H|$, with Corollaries 9 and 10. [^df-conv]: **Dummit & Foote**, §3.2 — the failure of the converse of Lagrange for $A_4$, and the statements of Cauchy's and Sylow's theorems as partial converses. [^df-hk]: **Dummit & Foote**, §3.2, Propositions 13–14 and Corollary 15 — $|HK| = |H||K|/|H \cap K|$, $HK$ a subgroup iff $HK = KH$, and the normalizer sufficient condition. [^df-well]: **Dummit & Foote**, §3.1, Proposition 5 — coset multiplication by representatives is well defined if and only if $gng^{-1} \in N$ for all $g, n$. [^df-s3]: **Dummit & Foote**, §3.2, Example 1 — the cosets of $\langle (1\,2) \rangle$ in $S_3$ have no well-defined product. [^df-ker]: **Dummit & Foote**, §3.1, Proposition 7 and Theorem 6 — the equivalence of the characterizations of normality and the identification of normal subgroups with kernels via the natural projection. [^df-d8]: **Dummit & Foote**, §3.1, Example — $D_8 / Z(D_8) \cong V_4$. [^ju-fe]: **Judson**, _Abstract Algebra: Theory and Applications_, §6.3 — Euler's Theorem and Fermat's Little Theorem as Lagrange's theorem in $(\mathbb{Z}/n\mathbb{Z})^\times$.