Cosets & Lagrange's Theorem

Cosets & Lagrange's Theorem

Cosets

Let $H$ be a subgroup of $G$. For any element $a \in G$, the left coset of $H$ with respect to $a$ is:

$aH = \{a * h : h \in H\}$

In $\mathbb{Z}_n$, where the operation is addition: $a + H = \{(a + h) \bmod n : h \in H\}$.

Example

In $\mathbb{Z}_6$, let $H = \{0, 3\}$. The cosets are:

• $0 + H = \{0, 3\}$
• $1 + H = \{1, 4\}$
• $2 + H = \{2, 5\}$

Notice that every element of $\mathbb{Z}_6$ belongs to exactly one coset, and all cosets have the same size.

Lagrange's Theorem

If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$. Moreover:

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

where $[G : H]$ is the index of $H$ in $G$ (the number of distinct cosets).

Consequences

• The order of any element divides $|G|$
• A group of prime order $p$ is cyclic (its only subgroups are $\{e\}$ and $G$ itself)
• $a^{|G|} = e$ for all $a \in G$ (gives Fermat's little theorem as a special case)

Your Task

Implement left_cosets(subgroup, n) that returns the list of all distinct left cosets of the given subgroup in $\mathbb{Z}_n$ (each coset as a sorted list), sorted by smallest element. Also implement verify_lagrange(n) that checks Lagrange's theorem for all subgroups of $\mathbb{Z}_n$.