01e-subgroups-lagrange.ipynb

Kernel: SageMath

Subgroups and Lagrange's Theorem

Module 01e | Modular Arithmetic and Groups

Some elements can't reach the whole group, but the little group they DO reach is surprisingly constrained.

Where we left off. In 01d we discovered that $g = 2$ in $(\mathbb{Z}/7\mathbb{Z}^*, \times)$ only generates $\{1, 2, 4\}$, three elements out of six. Meanwhile $g = 3$ reaches all six. But here's a question we didn't answer: is $\{1, 2, 4\}$ itself a group? And could it have been size 5 instead of size 3? What sizes are even possible?

Objectives

By the end of this notebook you will be able to:

1. Recognize a subgroup by checking the group axioms on a subset.

2. State Lagrange's theorem: a subgroup's size must divide the group's size.

3. Explain why it works using cosets (shifted copies of the subgroup).

4. Apply Lagrange's theorem to predict which element orders are possible.

A Group Inside a Group

Let's pick up right where 01d left off. In $(\mathbb{Z}/7\mathbb{Z}^*, \times)$, element 2 generates the set $\{1, 2, 4\}$. Is this a genuine group under multiplication mod 7?

We need the four axioms from 01c: closure, associativity, identity, inverses.

# Is {1, 2, 4} a group under multiplication mod 7?
R = Zmod(7)
S = [R(1), R(2), R(4)]
S_set = set(S)

# Closure: multiply every pair, check the result stays in S
print('Closure check (multiplication table):')
all_closed = True
for a in S:
    row = [a * b for b in S]
    if not all(x in S_set for x in row):
        all_closed = False
    print(f'  {a} * {[int(b) for b in S]} = {[int(x) for x in row]}')
print(f'  All products land in {{1, 2, 4}}? {all_closed}')

# Identity: 1 is in S
print(f'\nIdentity: {R(1)} is in S? {R(1) in S_set}')

# Inverses: for each element, find its inverse
print(f'\nInverses:')
for a in S:
    inv = a^(-1)
    print(f'  {a}^(-1) = {inv}   in S? {inv in S_set}')

# Associativity: inherited from Z/7Z* (always holds for modular multiplication)
print(f'\nAssociativity: inherited from the bigger group (always holds).')
print(f'\nVerdict: {{1, 2, 4}} IS a group under multiplication mod 7!')

This smaller group living inside the bigger one has a name: it's a subgroup.

Definition. A subset $H \subseteq G$ is a subgroup of $G$ (written $H \leq G$) if $H$ is itself a group under the same operation.

Two subgroups always exist for free:

• The trivial subgroup $\{e\}$ (just the identity), here $\{1\}$.

• The whole group $G$ (every group is a subgroup of itself).

The interesting subgroups are the ones in between.

What Sizes Are Possible?

$(\mathbb{Z}/7\mathbb{Z}^*, \times)$ has 6 elements. The subgroup $\{1, 2, 4\}$ has 3 elements. Could we find a subgroup of size 4? Or size 5?

Let's generate the subgroup $\langle g \rangle$ for every element $g$ and see what sizes appear.

# Generate <g> for every g in (Z/7Z*, ×)
R = Zmod(7)
G_elems = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
group_order = euler_phi(7)  # 6

print(f'Subgroups of (Z/7Z*, ×):     [group size = {group_order}]\n')

seen_sizes = set()
for g in G_elems:
    # Build <g> by repeated multiplication: g, g*g, g*g*g, ...
    cycle = []
    val = R(1)
    for k in range(1, group_order + 1):
        val = val * g
        cycle.append(int(val))
        if val == R(1):
            break
    seen_sizes.add(len(cycle))
    chain = ' -> '.join(str(c) for c in cycle)
    print(f'  <{g}>: {int(g)}^1..{int(g)}^{len(cycle)} = [{chain}]   (size {len(cycle)})')

print(f'\nSubgroup sizes that appear: {sorted(seen_sizes)}')
print(f'Divisors of 6: {divisors(6)}')
print(f'\nNotice: every subgroup size divides the group size 6.')
print(f'Sizes 4 and 5 are NOT divisors of 6, so they CANNOT appear.')

Subgroup sizes 1, 2, 3, 6. Group size 6. Every subgroup size divides 6.

Is this a coincidence? Let's try a bigger group to find out.

More Evidence: Additive Groups

$(\mathbb{Z}/12\mathbb{Z}, +)$ has 12 elements, so 12 has many divisors: 1, 2, 3, 4, 6, 12. This gives us more room to spot the pattern.

In an additive group, the subgroup generated by $a$ is $\langle a \rangle = \{a, 2a, 3a, \ldots\}$, keep adding $a$ until you cycle back to 0.

# Generate <a> for every a in (Z/12Z, +)
R = Zmod(12)
n = 12

def generated_subgroup(a, R):
    """Compute the additive subgroup <a> in R = Z/nZ."""
    a = R(a)
    order = a.additive_order()
    return sorted(set(k * a for k in range(order + 1)))

print(f'Subgroups of (Z/{n}Z, +):     [group size = {n}]\n')

# Collect distinct subgroups
seen = {}
for a in R:
    sg = generated_subgroup(a, R)
    key = frozenset(sg)
    if key not in seen:
        seen[key] = (a, sg)

for key in sorted(seen.keys(), key=len):
    gen, sg = seen[key]
    print(f'  <{gen}> = {[int(x) for x in sg]}   (size {len(sg)})')

sizes = sorted(set(len(sg) for _, sg in seen.values()))
print(f'\nSubgroup sizes: {sizes}')
print(f'Divisors of {n}: {divisors(n)}')
print(f'\nAgain: every subgroup size divides the group size. Not a coincidence.')

Checkpoint. Before reading on, try to predict: in $(\mathbb{Z}/15\mathbb{Z}, +)$, what subgroup sizes are possible? (Hint: divisors of 15 are 1, 3, 5, 15.)

Lagrange's Theorem

This pattern has been proven true for ALL finite groups, not just our examples.

Lagrange's Theorem. If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$.

That's it. Subgroup sizes must divide the group size. No exceptions, ever.

This is arguably the most important theorem in elementary group theory. But why is it true? The answer involves a beautiful idea: cosets.

Why It Works: Cosets

Here's the key idea. Take a subgroup $H$ and "slide" it around the group. Each slide produces a coset.

Concretely, in $(\mathbb{Z}/12\mathbb{Z}, +)$ with $H = \langle 4 \rangle = \{0, 4, 8\}$:

• Slide by 0: $0 + H = \{0, 4, 8\}$

• Slide by 1: $1 + H = \{1, 5, 9\}$

• Slide by 2: $2 + H = \{2, 6, 10\}$

• Slide by 3: $3 + H = \{3, 7, 11\}$

Slide by 4? That gives $\{4, 8, 0\}$, the same as the first coset. We've already covered everything.

Think of it like dealing cards into piles. Each pile (coset) has the same number of cards as $H$. The piles never overlap. Together they use up every card in the deck.

# Compute cosets of H = <4> = {0, 4, 8} in Z/12Z
R = Zmod(12)
H = generated_subgroup(4, R)
print(f'Subgroup H = <4> = {[int(h) for h in H]}   (size {len(H)})\n')

# Build distinct cosets by sliding H
covered = set()
cosets = []
for a in R:
    if a in covered:
        continue
    coset = sorted(set(a + h for h in H))
    additions = [f'{int(a)}+{int(h)}={int(a+h)}' for h in H]
    cosets.append((a, coset, additions))
    covered.update(coset)

for rep, coset, additions in cosets:
    print(f'  {int(rep)} + H:  {", ".join(additions)}  ->  {[int(x) for x in coset]}')

print(f'\n{len(cosets)} cosets, each of size {len(H)}, covering all 12 elements.')
print(f'12 = {len(H)} x {len(cosets)}   (group size = subgroup size x number of cosets)')
print(f'\nSince 12 = |H| x (number of cosets), |H| must divide 12. That is Lagrange!')

The argument works for ANY subgroup of ANY finite group:

1. Every coset has the same size as $H$ (sliding doesn't change the count).

2. Cosets never overlap (if two cosets share an element, they're identical).

3. Cosets cover everything (every element $a$ lives in the coset $a + H$).

So the group is partitioned into equal-sized pieces: $|G| = |H| \times (\text{number of cosets})$. Since both sides are integers, $|H|$ must divide $|G|$. Done.

The number of cosets is called the index of $H$ in $G$, written $[G:H]$.

Why cosets never partially overlap

The non-overlap property is the heart of the proof. Let's see it concretely. Elements 1 and 5 both live in the coset $1 + H = \{1, 5, 9\}$. Elements 1 and 2 live in different cosets. Watch what happens when we compute cosets starting from each element.

# Why cosets never partially overlap
R = Zmod(12)
H = generated_subgroup(4, R)
print(f'H = {[int(h) for h in H]}\n')

# Two elements from the SAME coset
a, b = R(1), R(5)
coset_a = set(a + h for h in H)
coset_b = set(b + h for h in H)
adds_a = ', '.join(f'{int(a)}+{int(h)}={int(a+h)}' for h in H)
adds_b = ', '.join(f'{int(b)}+{int(h)}={int(b+h)}' for h in H)
print('Elements 1 and 5 are in the SAME coset:')
print(f'  1 + H: {adds_a}  ->  {sorted(int(x) for x in coset_a)}')
print(f'  5 + H: {adds_b}  ->  {sorted(int(x) for x in coset_b)}')
print(f'  Identical? {coset_a == coset_b}')

# Two elements from DIFFERENT cosets
c = R(2)
coset_c = set(c + h for h in H)
adds_c = ', '.join(f'{int(c)}+{int(h)}={int(c+h)}' for h in H)
print(f'\nElements 1 and 2 are in DIFFERENT cosets:')
print(f'  1 + H: {adds_a}  ->  {sorted(int(x) for x in coset_a)}')
print(f'  2 + H: {adds_c}  ->  {sorted(int(x) for x in coset_c)}')
overlap = coset_a & coset_c
print(f'  Overlap: {sorted(int(x) for x in overlap) if overlap else "empty"}')

print(f'\nTwo cosets either match perfectly or share nothing.')
print(f'There is no partial overlap. That is why the partition works.')

Seeing Cosets

Let's color the elements of $\mathbb{Z}/12\mathbb{Z}$ by which coset they belong to. This makes the partition visible.

R = Zmod(12)
n = 12
H = generated_subgroup(4, R)

# Assign each element to its coset
coset_colors = ['royalblue', 'orangered', 'forestgreen', 'mediumorchid']
element_colors = {}
coset_list = []
covered = set()
coset_idx = 0
for a in R:
    if a in covered:
        continue
    coset = [a + h for h in H]
    for elem in coset:
        element_colors[int(elem)] = coset_colors[coset_idx]
    coset_list.append((int(a), [int(x) for x in coset]))
    covered.update(coset)
    coset_idx += 1

# Draw elements on a circle, colored by coset
P = Graphics()
angles = [2 * pi * i / n - pi/2 for i in range(n)]
r = 1.0

for i in range(n):
    cx = r * cos(angles[i])
    cy = r * sin(angles[i])
    P += circle((cx, cy), 0.12, fill=True, facecolor=element_colors[i],
                edgecolor='white', thickness=2, zorder=3)
    P += text(str(i), (cx, cy), fontsize=11, fontweight='bold',
              color='white', zorder=4)

# Faint outline circle
var('t')
P += parametric_plot((r * cos(t), r * sin(t)), (t, 0, 2*pi),
                      color='lightgray', thickness=0.5, zorder=1)

P.axes(False)
P.set_aspect_ratio(1)
P.show(figsize=5, title='Z/12Z colored by cosets of H = {0, 4, 8}')

# Print the legend
for rep, coset in coset_list:
    print(f'  {rep} + H = {coset}')
print('\nSame color = same coset. Four colors, three elements each, no overlap.')

The pattern is striking: the cosets are evenly spaced around the circle. Each coset is a "rotated copy" of $H$.

Checkpoint. What happens if we use $H = \langle 3 \rangle = \{0, 3, 6, 9\}$ instead? How many cosets would there be, and what size? (Answer: $12/4 = 3$ cosets of size 4.)

Cosets in multiplicative groups

Everything we just did with addition works identically with multiplication. Back to our opening example: $H = \{1, 2, 4\}$ is a subgroup of $(\mathbb{Z}/7\mathbb{Z}^*, \times)$. The cosets are $aH = \{a \cdot h : h \in H\}$.

# Cosets of H = {1, 2, 4} in (Z/7Z*, ×)
R = Zmod(7)
H = [R(1), R(2), R(4)]
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]

print(f'Subgroup H = {[int(h) for h in H]}  in (Z/7Z*, x)\n')

covered = set()
cosets = []
for a in units:
    if a in covered:
        continue
    coset = sorted(set(a * h for h in H))
    products = [f'{int(a)}*{int(h)}={int(a*h)}' for h in H]
    cosets.append((a, coset, products))
    covered.update(coset)

for rep, coset, products in cosets:
    print(f'  {int(rep)} * H:  {", ".join(products)}  ->  {[int(x) for x in coset]}')

print(f'\n{len(cosets)} cosets x {len(H)} elements = {len(cosets) * len(H)} elements total.')
print(f'6 = 3 x 2. Lagrange confirmed for multiplicative groups too.')
print(f'\nThis is the partition that matters for crypto: the subgroup {[int(h) for h in H]}')
print(f'and its single coset {[int(x) for x in cosets[1][1]]} split (Z/7Z*) into two halves.')

Consequences for Element Orders

Here is the key chain of reasoning. Pick any element $a$ in a group $G$:

1. The subgroup $\langle a \rangle$ generated by repeating the group operation ($a, a^2, a^3, \ldots$ for multiplication, or $a, 2a, 3a, \ldots$ for addition) is always a subgroup.

2. By Lagrange, $|\langle a \rangle|$ must divide $|G|$.

3. But $|\langle a \rangle| = \text{ord}(a)$ (the subgroup size equals the cycle length).

4. So $\text{ord}(a)$ divides $|G|$.

Corollary. The order of every element must divide the size of the group.

Let's trace this chain for element 8 in $(\mathbb{Z}/12\mathbb{Z}, +)$. Here $\langle 8 \rangle = \{8,\; 8{+}8,\; 8{+}8{+}8, \ldots\}$, keep adding 8 until we return to 0.

# The order constraint: trace the logic for element 8 in (Z/12Z, +)
R = Zmod(12)
a = R(8)

# Step 1: generate <8> by adding 8 repeatedly
print(f'Step 1: generate <{int(a)}> by adding 8 repeatedly:\n')
val = R(0)
subgroup = []
for k in range(1, 13):
    val = val + a
    subgroup.append(int(val))
    prev = int(val - a) if k > 1 else '0'
    print(f'  {prev} + 8 = {int(val)} (mod 12)')
    if val == R(0):
        break
print(f'\n  <8> = {subgroup}   (size {len(subgroup)})')
print(f'  Closed, contains 0, every element has an inverse. It is a subgroup.')

# Step 2: Lagrange
print(f'\nStep 2: Lagrange says |<8>| divides |G|.')
print(f'  |<8>| = {len(subgroup)},  |G| = 12.')
print(f'  {len(subgroup)} divides 12? {12 % len(subgroup) == 0}  (12 = {len(subgroup)} x {12 // len(subgroup)})')

# Step 3: connect order to subgroup size
print(f'\nStep 3: ord(8) = {len(subgroup)} = |<8>|.')
print(f'  The order IS the subgroup size. Always.')

# Step 4: conclusion
print(f'\nStep 4: ord(8) = {len(subgroup)} divides |G| = 12.  Done.')
print(f'\nThis works for EVERY element. An element of order 5 would generate')
print(f'a subgroup of size 5, but 5 does not divide 12, so Lagrange forbids it.')

We traced the chain for one element. Now let's verify the constraint holds for every element in $(\mathbb{Z}/12\mathbb{Z}, +)$. The group has 12 elements, so Lagrange says the only possible orders are the divisors of 12: $\{1, 2, 3, 4, 6, 12\}$. No element can have order 5, 7, 8, 9, 10, or 11.

# Element orders in (Z/12Z, +) must divide 12
R = Zmod(12)
n = 12
print(f'Group: (Z/{n}Z, +),  |G| = {n}')
print(f'Divisors of {n}: {divisors(n)}')
print(f'So element orders can ONLY be: {divisors(n)}\n')

for a in R:
    # Show the cycle: a, 2a, 3a, ... until we hit 0
    cycle = []
    val = R(0)
    for k in range(1, n + 1):
        val = val + R(a)
        cycle.append(int(val))
        if val == R(0):
            break
    chain = ' -> '.join(str(c) for c in cycle)
    print(f'  a={int(a):>2}: [{chain}]  (order {len(cycle)})')

actual_orders = sorted(set(R(a).additive_order() for a in R))
print(f'\nOrders that actually appear: {actual_orders}')
print(f'Every single divisor of 12 shows up. (This always happens in cyclic groups.)')

Back to Multiplication: A Surprise

Let's apply Lagrange to $(\mathbb{Z}/15\mathbb{Z}^*, \times)$. This group has $\varphi(15) = 8$ elements, so Lagrange says element orders can only be divisors of 8: that's 1, 2, 4, or 8.

Let's check.

# Element orders in (Z/15Z*, ×)
R = Zmod(15)
phi_n = euler_phi(15)
units = [R(a) for a in R.list_of_elements_of_multiplicative_group()]

print(f'Group: (Z/15Z*, ×),  |G| = phi(15) = {phi_n}')
print(f'Divisors of {phi_n}: {divisors(phi_n)}')
print(f'So possible element orders: {divisors(phi_n)}\n')

actual_orders = set()
for a in units:
    # Show the power chain: a, a^2, a^3, ... until we hit 1
    cycle = []
    val = R(1)
    for k in range(1, phi_n + 1):
        val = val * a
        cycle.append(int(val))
        if val == R(1):
            break
    order = len(cycle)
    actual_orders.add(order)
    chain = ' -> '.join(str(c) for c in cycle)
    tag = '  <-- generator!' if order == phi_n else ''
    print(f'  g={int(a):>2}: {int(a)}^1..{int(a)}^{order} = [{chain}]  (order {order}){tag}')

print(f'\nOrders that actually appear: {sorted(actual_orders)}')
missing = set(divisors(phi_n)) - actual_orders
if missing:
    print(f'Missing: {sorted(missing)}')
    print(f'\nNo element has order 8! That means no single element generates the')
    print(f'whole group. (Z/15Z*, ×) is NOT cyclic.')

This is an important subtlety:

Common mistake. "Lagrange says every divisor of $|G|$ appears as a subgroup size." No! Lagrange only goes one direction: subgroup sizes must be divisors. It does NOT promise that every divisor appears. For cyclic groups (like $\mathbb{Z}/n\mathbb{Z}$) every divisor does give a subgroup, but for non-cyclic groups some divisors can be missing.

Why This Matters for Cryptography

Lagrange's theorem explains why cryptographers care about safe primes.

If $p$ is prime, $(\mathbb{Z}/p\mathbb{Z}^*)$ has order $p - 1$. The subgroup sizes are the divisors of $p - 1$. If $p - 1$ has lots of small factors, there are lots of small subgroups, and an attacker can exploit them.

The Pohlig-Hellman idea

Suppose you need to solve $g^x = h$ in a group of order $n = p - 1$. If $n$ has a small factor $d$, here is the trick:

1. Raise both sides to the power $n/d$: compute $g' = g^{n/d}$ and $h' = h^{n/d}$.

2. Both $g'$ and $h'$ now live in a subgroup of size $d$ (Lagrange guarantees this, since $(g')^d = g^n = 1$).

3. Solve the DLP in this tiny subgroup by brute force: find $x'$ with $(g')^{x'} = h'$.

4. This gives you $x \bmod d$, one piece of the secret.

Repeat for each small factor of $n$, then combine with the Chinese Remainder Theorem (Module 04). If $n$ has many small factors, you solve several tiny DLPs instead of one massive one.

A safe prime $p = 2q + 1$ (where $q$ is also prime) blocks this: $p - 1 = 2q$ has no small factors beyond 2, so there are no useful small subgroups to exploit.

# Compare subgroup structure: regular prime vs safe prime

print('=== Regular prime: p = 41 ===\n')
p1 = 41
divs1 = divisors(p1 - 1)
print(f'  |G| = p - 1 = {p1 - 1} = {factor(p1 - 1)}')
print(f'  Subgroup sizes: {divs1}')
print(f'  That is {len(divs1)} possible subgroup sizes.')
small1 = [d for d in divs1 if 1 < d <= 8]
print(f'  Small subgroups (size 2 to 8): {small1}')

print(f'\n=== Safe prime: p = 47 ===\n')
p2 = 47
divs2 = divisors(p2 - 1)
print(f'  |G| = p - 1 = {p2 - 1} = {factor(p2 - 1)}')
print(f'  Subgroup sizes: {divs2}')
print(f'  That is {len(divs2)} possible subgroup sizes.')
small2 = [d for d in divs2 if 1 < d <= 8]
print(f'  Small subgroups (size 2 to 8): {small2 if small2 else "only size 2"}')

print(f'\n=== The security difference ===\n')
print(f'p = {p1}: an attacker can solve the DLP in subgroups of size {small1}.')
print(f'         Brute-force in a size-4 subgroup takes 4 tries. Trivial.')
print(f'p = {p2}: smallest nontrivial subgroup has 23 elements.')
print(f'         No shortcut available.')
print(f'\nWith real primes (2048 bits), the contrast is stark:')
print(f'  Bad prime:  p-1 might have factors like 2, 3, 5, 7, 11, ...')
print(f'  Safe prime: p-1 = 2q, only subgroups of size 1, 2, q, 2q.')
print(f'  The Pohlig-Hellman attack (Module 05) exploits small subgroups.')
print(f'  Choosing a safe prime neutralizes it completely.')

# Pohlig-Hellman in action: small subgroups leak information
p = 41  # p - 1 = 40 = 2^3 * 5
R = Zmod(p)
g = R(7)  # a generator of (Z/41Z)*
n = p - 1

# Secret exponent
x_secret = 27
h = g^x_secret

print(f'DLP: find x such that {int(g)}^x = {int(h)} (mod {p})')
print(f'Group order: n = {n} = {factor(n)}')
print(f'Full brute force would take up to {n} steps.\n')

# Project into the subgroup of order 5
d = 5
print(f'Step 1: pick a small factor of n = {n}. We pick d = {d}.')
print(f'        Lagrange says there is a subgroup of order {d}.\n')

print(f'Step 2: project g and h into that subgroup.')
print(f'        Raise both to the power n/d = {n}/{d} = {n // d}:')
g_small = g^(n // d)
h_small = h^(n // d)
print(f'        g\' = g^{n//d} = {int(g)}^{n//d} = {int(g_small)} (mod {p})')
print(f'        h\' = h^{n//d} = {int(h)}^{n//d} = {int(h_small)} (mod {p})')
print(f'\n        Why does this work? (g\')^{d} = g^{n} = 1 (mod {p}),')
print(f'        so g\' has order dividing {d}. It lives in the size-{d} subgroup.')
print(f'        Check: ord(g\') = {g_small.multiplicative_order()}.  Good.\n')

print(f'Step 3: brute-force the DLP in the tiny subgroup ({d} tries):')
x_mod_d = None
for candidate in range(d):
    val = g_small^candidate
    if val == h_small:
        print(f'        g\'^{candidate} = {int(g_small)}^{candidate} = {int(val)} (mod {p})  <-- match!')
        x_mod_d = candidate
    else:
        print(f'        g\'^{candidate} = {int(g_small)}^{candidate} = {int(val)} (mod {p})')

print(f'\nStep 4: interpret the result.')
print(f'        x = {x_mod_d} (mod {d})')
print(f'        Verify: {x_secret} mod {d} = {x_secret % d}.  Correct!')
print(f'\n        We do not know x yet, but we know its remainder mod {d}.')
print(f'        That rules out {n - n//d} of the {n} candidates in one shot.')
print(f'\nRepeat for each factor of {n} = {factor(n)}, combine with CRT (Module 04),')
print(f'and x is fully recovered. Total work: a few tiny brute forces, not one big one.')

Exercises

Exercise 1 (Worked)

Find all subgroups of $(\mathbb{Z}/7\mathbb{Z}^*, \times)$. For each, list its elements and verify its size divides 6.

# Exercise 1 (Worked): All subgroups of (Z/7Z*, ×)
R = Zmod(7)
G_elems = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
group_order = euler_phi(7)

print(f'Group: (Z/7Z*, ×),  |G| = {group_order}')
print(f'Divisors of {group_order}: {divisors(group_order)}\n')

# Generate <g> for each g, collect distinct subgroups
seen = {}
for g in G_elems:
    order = g.multiplicative_order()
    subgroup = sorted(set(g^k for k in range(1, order + 1)))
    key = frozenset(subgroup)
    if key not in seen:
        seen[key] = (g, subgroup)

for key in sorted(seen.keys(), key=len):
    gen, sg = seen[key]
    divides = group_order % len(sg) == 0
    print(f'  <{gen}> = {[int(x) for x in sg]}   size {len(sg)}   divides 6? {"yes" if divides else "NO"}')

print(f'\n{len(seen)} subgroups total. Sizes 1, 2, 3, 6 = all divisors of 6.')
print(f'(Z/7Z* is cyclic, so every divisor appears.)')

Exercise 2 (Guided)

Compute the cosets of $H = \langle 5 \rangle$ in $(\mathbb{Z}/15\mathbb{Z}, +)$. How many cosets are there? Verify they partition $\{0, 1, \ldots, 14\}$.

# Exercise 2: Cosets of <5> in (Z/15Z, +)
R = Zmod(15)

# Step 1: compute H = <5>
H = generated_subgroup(5, R)
print(f'H = <5> = {[int(h) for h in H]},  |H| = {len(H)}')
print(f'Predicted number of cosets: 15 / {len(H)} = {15 // len(H)}\n')

# Step 2: TODO, compute cosets a + H for a = 0, 1, 2, ...
# until all 15 elements are covered
# Hint: for each a not yet covered, compute {a + h for h in H}

# Step 3: TODO, verify the cosets partition {0, 1, ..., 14}
# Check: no overlaps, and union = set(R)

Exercise 3 (Independent)

In $(\mathbb{Z}/31\mathbb{Z}^*, \times)$, the group has order 30.

1. List all possible subgroup sizes (= divisors of 30).

2. For each divisor $d$, find an element whose order is $d$.

3. Is there a divisor with no corresponding element? Is $(\mathbb{Z}/31\mathbb{Z}^*)$ cyclic?

# Exercise 3: Your code here

Summary

Concept	Key idea
Subgroup	A subset $H \subseteq G$ that is itself a group under the same operation
Cosets	Shifted copies $a + H$ that tile $G$ into equal-sized, non-overlapping pieces
Lagrange's theorem	$|H|$ divides $|G|$, because the coset tiling forces $|G| = |H| \times (\text{number of cosets})$
Index	$[G:H] = |G|/|H|$, the number of cosets
Order constraint	$\langle a \rangle$ is a subgroup of size $\text{ord}(a)$, so Lagrange forces $\text{ord}(a) \mid |G|$
Pohlig-Hellman	Small subgroups leak partial DLP solutions; project via $g^{n/d}$, brute-force in the small subgroup, recover $x \bmod d$
Safe primes	$p = 2q + 1$ leaves only subgroups of size $1, 2, q, 2q$, blocking Pohlig-Hellman

The punchline: Lagrange says group structure is not free-form. Subgroup sizes, element orders, and coset counts are all locked together by divisibility. Cryptographers exploit this rigidity: choosing a safe prime controls exactly which subgroups exist, shutting down the Pohlig-Hellman attack.

Next: Visualizing Group Structure, where we'll draw Cayley graphs, subgroup lattices, and multiplication heatmaps to see everything we've computed.