Subgroups

Subgroups

A subgroup $H$ of a group $(G, *)$ is a subset $H \subseteq G$ that is itself a group under the same operation.

Subgroup Test

A non-empty subset $H$ of $G$ is a subgroup if and only if for all $a, b \in H$: $a * b^{-1} \in H$

This single condition captures closure, identity, and inverses simultaneously.

Example: Subgroups of $\mathbb{Z}_6$

The group $\mathbb{Z}_6 = \{0,1,2,3,4,5\}$ under addition mod 6 has these subgroups:

• $\{0\}$ — trivial subgroup
• $\{0, 3\}$ — order 2
• $\{0, 2, 4\}$ — order 3
• $\{0, 1, 2, 3, 4, 5\}$ — the whole group

Notice that the subgroup orders (1, 2, 3, 6) all divide $|G| = 6$. This is Lagrange's theorem, which we will prove later.

Finding Subgroups Computationally

For $\mathbb{Z}_n$ under addition, a subset $H$ is a subgroup if:

1. $0 \in H$ (identity)
2. For each $a \in H$, $(n - a) \% n \in H$ (inverses)
3. For each $a, b \in H$, $(a + b) \% n \in H$ (closure)

Generated Subgroups

The subgroup generated by an element $a$, written $\langle a \rangle$, is the smallest subgroup containing $a$:

$\langle a \rangle = \{e, a, a^2, a^3, \ldots\}$

In $\mathbb{Z}_n$, $\langle a \rangle = \{0, a, 2a, 3a, \ldots\} \pmod{n}$.

Your Task

Implement generated_subgroup(a, n) that returns the sorted list of elements in $\langle a \rangle$ within $\mathbb{Z}_n$, and find_all_subgroups(n) that returns all subgroups of $\mathbb{Z}_n$ (each as a sorted list), sorted by size then lexicographically.