Chapter 04

Hard

Cosets & Lagrange's Theorem

00 · Symbol Glossary

$aH$Left coset of H by a

The set $\{ah : h\in H\}$ — every element of $H$ , shifted by $a$ on the left. Generally not a subgroup itself (it usually doesn't even contain $e$ ), just a translated copy of $H$ 's shape.

$Ha$Right coset of H by a

The set $\{ha : h\in H\}$ — shifted by $a$ on the right. Equals $aH$ when $G$ is abelian, but can differ from it otherwise; the distinction becomes essential in Chapter 05.

$[G:H]$Index of H in G

The number of distinct left cosets of $H$ in $G$ . Finite even when $G$ and $H$ are both infinite, as long as the count of cosets itself is finite (e.g. $[\mathbb{Z}:n\mathbb{Z}]=n$ ).

$G/H$Set of left cosets (as a set, for now)

The collection of all left cosets of $H$ in $G$ . Purely a set at this stage — it becomes a group in its own right only when $H$ satisfies an extra condition, introduced in Chapter 05.

$a^{-1}b \in H$Coset-membership test

The algebraic shortcut for " $a$ and $b$ are in the same left coset of $H$ " — used constantly in proofs instead of comparing two whole sets element by element.

01 · Cosets

Subgroups don't just sit inside $G$ — they can be shifted by any element of $G$ , producing a whole family of same-sized "copies" that, remarkably, tile the entire group with no gaps and no overlaps.

Definition — Left and Right Cosets

For $H\le G$ and $a\in G$ , the left coset of $H$ by $a$ is $aH=\{ah:h\in H\}$ , and the right coset is $Ha=\{ha:h\in H\}$ .

Example — Cosets of $3\mathbb{Z}$ in $\mathbb{Z}$

$H=3\mathbb{Z}=\{\ldots,-3,0,3,6,\ldots\}$ inside $(\mathbb{Z},+)$ (additive notation, so " $aH$ " is written $a+H$ ).

$0+H = H = \{\ldots,-3,0,3,6,\ldots\}$

$1+H = \{\ldots,-2,1,4,7,\ldots\}$

$2+H = \{\ldots,-1,2,5,8,\ldots\}$

These three cosets are pairwise disjoint and their union is all of $\mathbb{Z}$ — every integer lands in exactly one, sorted by remainder mod 3. (And $3+H=H$ again — cosets repeat once every representative differs by a multiple of $3$ .)

A coset is usually not a subgroup

$1+3\mathbb{Z} = \{\ldots,-2,1,4,\ldots\}$ doesn't even contain $0$ , so it fails to be a subgroup outright. Cosets are translates, not substructures — same size and shape as $H$ , just relocated. Only the coset $eH=H$ itself is a subgroup.

Theorem 4.1 — Coset Membership Test

For $H\le G$ and $a,b\in G$ : $aH = bH \iff a^{-1}b \in H \iff b \in aH$ .

Proof

$aH=bH \Rightarrow a^{-1}b\in H$ : Since $b = be \in bH = aH$ , we have $b=ah$ for some $h\in H$ , so $a^{-1}b = h \in H$ .

$a^{-1}b\in H \Rightarrow b \in aH$ : Write $a^{-1}b=h\in H$ . Then $b=ah \in aH$ .

$b\in aH \Rightarrow aH=bH$ : Suppose $b=ah_0$ for some $h_0\in H$ . For any $x\in bH$ , $x=bh=ah_0h\in aH$ (since $h_0h\in H$ by closure), so $bH\subseteq aH$ . Conversely, $a=bh_0^{-1}$ , so by the same argument with $a,b$ swapped, $aH\subseteq bH$ . Hence $aH=bH$ .

Chaining the three implications gives all stated equivalences.

Step-by-step — Are $4+3\mathbb{Z}$ and $1+3\mathbb{Z}$ the same coset?

Apply the test: check whether

a^{-1}b \in H

, i.e. (additively) whether

b-a \in H

, for

a=4

b=1

Compute:

1-4=-3

Check membership:

-3 \in 3\mathbb{Z}

? Yes,

-3 = 3\times(-1)

Conclude: by Theorem 4.1,

4+3\mathbb{Z} = 1+3\mathbb{Z}

— same coset, different representative.

02 · Cosets Partition the Group

Theorem 4.2 — Left Cosets Partition G

For fixed $H\le G$ , the left cosets of $H$ partition $G$ : every element of $G$ lies in exactly one left coset of $H$ .

Proof

Define a relation on $G$ by $a\sim b \iff a^{-1}b\in H$ .

Reflexive: $a^{-1}a=e\in H$ (since $H\le G$ contains $e$ ).

Symmetric: if $a^{-1}b\in H$ , then $(a^{-1}b)^{-1}=b^{-1}a\in H$ (H is closed under inverses), so $b\sim a$ .

Transitive: if $a^{-1}b\in H$ and $b^{-1}c\in H$ , then $(a^{-1}b)(b^{-1}c)=a^{-1}c\in H$ (closure), so $a\sim c$ .

So $\sim$ is an equivalence relation, and by Theorem 1.3 its equivalence classes partition $G$ . It remains to identify $[a]$ with $aH$ : by Theorem 4.1, $b\sim a$ (i.e. $a^{-1}b\in H$ ) is exactly the condition $b\in aH$ . So $[a]=aH$ , and the partition is precisely the partition into left cosets.

This is Theorem 1.3, again, in a new costume

Compare this proof to Theorem 1.3's original statement about equivalence classes, and to Theorem 1.4's verification that congruence mod $n$ is an equivalence relation. The pattern — define a relation via a subgroup or divisibility condition, verify reflexive/symmetric/transitive using closure and inverses, invoke the partition theorem — is now the third time it has produced a partition. This is exactly the reusability abstract algebra is built for.

03 · All Cosets Have the Same Size

Theorem 4.3 — Cosets Are Equinumerous with H

For any $a\in G$ , there is a bijection between $H$ and $aH$ . Consequently $|aH|=|H|$ for every $a\in G$ .

Proof

Define $\varphi: H\to aH$ by $\varphi(h)=ah$ .

Surjective: every element of $aH$ has the form $ah$ for some $h\in H$ by definition, so it's hit by $\varphi(h)$ .

Injective: suppose $\varphi(h_1)=\varphi(h_2)$ , i.e. $ah_1=ah_2$ . By left cancellation (Theorem 2.1), $h_1=h_2$ .

A bijective $\varphi$ exists, so $H$ and $aH$ have the same cardinality: $|aH|=|H|$ .

Example — Verifying equal size directly

From Section 01, $H=3\mathbb{Z}$ and the coset $1+3\mathbb{Z} = \{\ldots,-2,1,4,7,\ldots\}$ . Both are (countably) infinite, consistent with Theorem 4.3 — but the theorem's real power shows up for finite $H$ , where "same size" becomes a literal, checkable number, as in the next section.

04 · Lagrange's Theorem

Combining Theorem 4.2 (cosets partition $G$ ) with Theorem 4.3 (every coset has size $|H|$ ) gives one of the most quoted results in all of finite group theory.

Theorem 4.4 — Lagrange's Theorem

If $G$ is a finite group and $H\le G$ , then $|H|$ divides $|G|$ , and specifically $|G| = [G:H]\cdot|H|$ .

Proof

By Theorem 4.2, the distinct left cosets of $H$ partition $G$ into some number of pieces — call that number $[G:H]$ (finite, since $G$ is finite). By Theorem 4.3, every one of these pieces has exactly $|H|$ elements. Since a partition's pieces are disjoint and their union is everything, counting elements gives:

|G| = \underbrace{|H| + |H| + \cdots + |H|}_{[G:H]\text{ copies}} = [G:H]\cdot|H|

In particular $|H|$ divides $|G|$ , with quotient exactly $[G:H]$ .

Common mistake — The converse of Lagrange's Theorem is false

Does every divisor of $|G|$ have to be the order of some subgroup? No. $A_4$ (even permutations of 4 letters) has order $12$ , and $6$ divides $12$ — but $A_4$ has no subgroup of order $6$ , a genuinely surprising fact usually proved by direct case analysis. Lagrange's Theorem is a one-directional constraint ("subgroup orders must divide $|G|$ "), never a guarantee that every divisor is achieved. Chapter 09's Sylow theorems give a partial converse, but only for prime-power divisors.

Corollary 4.5 — Element Orders Divide the Group Order

For any finite group $G$ and $g\in G$ , $|g|$ divides $|G|$ .

Proof

By Theorem 3.4, $|g|=|\langle g\rangle|$ . Since $\langle g\rangle \le G$ (Theorem 3.3), Lagrange's Theorem gives $|\langle g\rangle|$ divides $|G|$ . Combining, $|g|$ divides $|G|$ .

Corollary 4.6 — Groups of Prime Order Are Cyclic

If $|G|=p$ for a prime $p$ , then $G$ is cyclic, and in fact every nonidentity element is a generator.

Proof

Take any $g\in G$ with $g\neq e$ . By Corollary 4.5, $|g|$ divides $p$ . Since $p$ is prime, its only positive divisors are $1$ and $p$ . If $|g|=1$ , then $g=g^1=e$ , contradicting the choice of $g$ . So $|g|=p$ . By Theorem 3.4, $|\langle g\rangle| = |g| = p = |G|$ , and since $\langle g\rangle \subseteq G$ with equal finite size, $\langle g\rangle = G$ . So $g$ generates all of $G$ — and $g$ was an arbitrary nonidentity element.

A complete classification, for free

Corollary 4.6 says there is, up to relabeling, only one group of each prime order: $\mathbb{Z}_p$ . This is a full classification theorem — a statement that every group of a certain kind must look like a specific known example — derived in three lines from Lagrange's Theorem. Full classification theorems are rare and prized; this is the simplest one in the subject.

05 · The Index and a Multiplicative Chain

Definition — Index

$[G:H]$ , the index of $H$ in $G$ , is the number of distinct left cosets of $H$ in $G$ . By Lagrange's Theorem, $[G:H] = |G|/|H|$ when $G$ is finite.

Example — Index inside a chain of subgroups

$\{e\} \le \langle r\rangle \le D_4$ , where $\langle r\rangle$ is the rotation subgroup of the square's symmetry group. $|D_4|=8$ , $|\langle r\rangle|=4$ , $|\{e\}|=1$ .

$[D_4:\langle r\rangle] = 8/4=2$ . $[\langle r\rangle:\{e\}]=4/1=4$ . $[D_4:\{e\}]=8/1=8$ .

Notice $[D_4:\langle r\rangle]\cdot[\langle r\rangle:\{e\}] = 2\times4=8=[D_4:\{e\}]$ — indices multiply along a chain of subgroups, a direct consequence of Lagrange's Theorem applied twice.

06 · A Number-Theoretic Application

Group theory's counting machinery reaches back to prove a classical fact from elementary number theory almost for free.

Theorem 4.7 — Euler's Theorem

If $\gcd(a,n)=1$ , then $a^{\varphi(n)} \equiv 1 \pmod n$ , where $\varphi(n) = |\mathbb{Z}_n^\times|$ (Euler's totient function — the count of integers in $\{1,\ldots,n\}$ coprime to $n$ ).

Proof

Since $\gcd(a,n)=1$ , the class $[a]$ lies in the group $(\mathbb{Z}_n^\times, \times)$ , a finite group of order $\varphi(n)$ by definition. By Corollary 4.5, $|[a]|$ (the order of the element $[a]$ inside this group) divides $\varphi(n)$ , so $\varphi(n) = |[a]|\cdot m$ for some positive integer $m$ . Then:

[a]^{\varphi(n)} = \big([a]^{|[a]|}\big)^m = [1]^m = [1]

using that $[a]^{|[a]|}=[1]$ by the definition of element order. Translating back: $a^{\varphi(n)}\equiv1\pmod n$ .

Example — Fermat's Little Theorem as a special case

When $n=p$ is prime, every $a$ with $1\le a\le p-1$ satisfies $\gcd(a,p)=1$ automatically, and $\varphi(p)=p-1$ (all of $\{1,\ldots,p-1\}$ are coprime to $p$ ). Theorem 4.7 then reads $a^{p-1}\equiv1\pmod p$ — Fermat's Little Theorem, usually proved separately in a first number theory course, falling out here as one line of group theory.

07 · Exercises

EXERCISE 4.1

Use the coset membership test (Theorem 4.1): are $2-8=-6$ and other differences multiples of 4?

Additively, $a\sim b \iff b-a \in 4\mathbb{Z}$ . Check $2$ and $8$ : $8-2=6$ , not a multiple of $4$ — different cosets, actually. Let's instead directly list: $2+4\mathbb{Z} = \{\ldots,-2,2,6,10,\ldots\}$ and $8 \in$ this set? $8-2=6$ , not divisible by 4, so no, $8\notin 2+4\mathbb{Z}$ .

Check $8$ and $-4$ : $-4-8=-12=4\times(-3)$ , a multiple of $4$ . So $8+4\mathbb{Z} = -4+4\mathbb{Z}$ — same coset.

There are exactly $4$ distinct cosets of $4\mathbb{Z}$ in $\mathbb{Z}$ (one per remainder $0,1,2,3$ ), and $8\equiv0$ , $-4\equiv0$ , $2\equiv2 \pmod4$ — confirming $8$ and $-4$ share a coset, while $2$ is in a different one.

In $(\mathbb{Z},+)$ with $H=4\mathbb{Z}$ , determine whether $2+H$ and $8+H$ are the same coset, and whether $8+H$ and $-4+H$ are the same coset. Justify using Theorem 4.1.

EXERCISE 4.2

Compute $[G:H]$ from Lagrange's Theorem, then count that many distinct cosets directly to double check.

$|G|=|D_4|=8$ , $H=\{e,r^2\}$ (order 2, since $r^2\neq e$ but $r^4=e$ ). By Lagrange, $[D_4:H] = 8/2=4$ — there are $4$ distinct left cosets.

$D_4$ has order 8. Let $H=\{e,r^2\}$ where $r$ is the order-4 rotation. What is $[D_4:H]$ ?

EXERCISE 4.3

Apply Corollary 4.5 directly: what are the divisors of 7?

By Corollary 4.5, $|g|$ divides $|G|=7$ . Since $7$ is prime, its only positive divisors are $1$ and $7$ . So every element of $G$ has order $1$ (only $e$ ) or order $7$ .

By Corollary 4.6, $G$ is in fact cyclic — isomorphic in structure to $\mathbb{Z}_7$ , with every nonidentity element serving as a generator.

If $|G|=7$ , what are the possible orders of elements of $G$ ? What can you conclude about the structure of $G$ itself?

EXERCISE 4.4

Use Theorem 4.7 with $n=9$ : first find $\varphi(9)$ by counting integers from 1 to 9 coprime to 9.

$\gcd(2,9)=1$ , so Theorem 4.7 applies. $\varphi(9)$ counts $\{1,2,4,5,7,8\}$ (excluding multiples of $3$ : $3,6,9$ ) — six values, so $\varphi(9)=6$ .

Theorem 4.7 gives $2^6 \equiv 1 \pmod 9$ . Check: $2^6=64=63+1=9(7)+1$ , so $64\equiv1\pmod9$ . ✓

Use Euler's Theorem to find a small exponent $k$ with $2^k \equiv 1 \pmod 9$ , and verify the arithmetic directly.

EXERCISE 4.5

$60=2^2\times3\times5$ . Compare its divisors to what a subgroup of order 6 would require, thinking about $A_4$ 's specific structure only if you recall it — otherwise, just state Lagrange's constraint and why it alone can't rule this out.

Lagrange's Theorem only says any subgroup's order must divide $60$ . Since $6\mid60$ , Lagrange's Theorem alone does not rule out a subgroup of order $6$ — it is silent on the question, exactly as the FailBlock in Section 04 warned. (In fact, whether such a subgroup exists depends on the specific group in question — some groups of order $60$ have a subgroup of order $6$ and others, like $A_5$ , famously do not, but that requires more than Lagrange's Theorem to establish.)

A group has order $60$ . Does Lagrange's Theorem, by itself, guarantee the existence of a subgroup of order $6$ ? Explain what Lagrange's Theorem does and does not tell you here.

08 · Chapter Summary

Concept	Statement
Left/right coset	$aH=\{ah:h\in H\}$ , $Ha=\{ha:h\in H\}$
Coset test	$aH=bH \iff a^{-1}b\in H$ (Thm 4.1)
Cosets partition $G$	Every $g\in G$ in exactly one left coset (Thm 4.2)
Equal size	$
Lagrange's Theorem	$
Element order divides $	G
Prime-order groups are cyclic	Corollary 4.6
Index	$[G:H]=
Euler's Theorem	$a^{\varphi(n)}\equiv1\pmod n$ when $\gcd(a,n)=1$ (Thm 4.7)

Next: Chapter 05 — Normal Subgroups & Quotient Groups asks exactly when the set of cosets $G/H$ can be given its own group operation, turning a set of translated copies of $H$ into a brand-new group in its own right.