01c-groups-first-look.ipynb

Kernel: SageMath 10.0

Groups: A First Look

Module 01c | Modular Arithmetic and Groups

Two completely different operations, one shared structure. Welcome to abstract algebra.

Question: $\mathbb{Z}/7\mathbb{Z}$ under addition has 7 elements and every equation $a + x = b$ has a solution. $(\mathbb{Z}/7\mathbb{Z})^*$ under multiplication has 6 elements and every equation $a \cdot x = b$ has a solution. These are completely different operations, but they share the same deep structure. What IS that structure?

Objectives

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

1. State the four group axioms (closure, associativity, identity, inverses)

2. Verify group axioms for $(\mathbb{Z}/n\mathbb{Z}, +)$ and $(\mathbb{Z}/p\mathbb{Z}^*, \times)$

3. Distinguish groups from non-groups using a concrete failed axiom

4. Explain why prime moduli give the largest multiplicative groups

From Arithmetic to Algebra

In 01b we discovered that $\mathbb{Z}/n\mathbb{Z}$ has two interesting subsets:

• All elements $\{0, 1, \ldots, n-1\}$ under addition

• Units $\{a : \gcd(a, n) = 1\}$ under multiplication

Both let you combine elements and undo the operation. Let's extract the common pattern, this is where abstract algebra begins.

Spotting the Pattern

Let's check the same four properties for two very different systems: $(\mathbb{Z}/7\mathbb{Z}, +)$ and $(\mathbb{Z}/7\mathbb{Z}^*, \times)$.

# System 1: (Z/7Z, +)
R = Zmod(7)
print('=== (Z/7Z, +) ===')
print(f'Elements: {list(R)}')
print(f'Size: {len(list(R))}')
print()

# Closure: does a + b stay in the set?
a, b = R(3), R(5)
print(f'Closure: {a} + {b} = {a+b} \u2208 Z/7Z? {a+b in R}')

# Identity: is there an element e with a + e = a?
print(f'Identity: {a} + 0 = {a + R(0)}')

# Inverses: for each element, does a + (-a) = 0?
print('Inverses:', {int(x): int(-x) for x in R})

# Associativity: does (a+b)+c = a+(b+c)?
c = R(4)
print(f'Associativity: ({a}+{b})+{c} = {(a+b)+c}, {a}+({b}+{c}) = {a+(b+c)}')

# System 2: (Z/7Z*, ×)
R = Zmod(7)
units = [R(x) for x in range(1, 7)]
print('=== (Z/7Z*, \u00d7) ===')
print(f'Elements: {units}')
print(f'Size: {len(units)}')
print()

# Closure
a, b = R(3), R(5)
print(f'Closure: {a} * {b} = {a*b} \u2208 units? {a*b in units}')

# Identity
print(f'Identity: {a} * 1 = {a * R(1)}')

# Inverses
print('Inverses:', {int(x): int(x^(-1)) for x in units})

# Associativity
c = R(4)
print(f'Associativity: ({a}*{b})*{c} = {(a*b)*c}, {a}*({b}*{c}) = {a*(b*c)}')

Two different operations, same four properties:

Property	$(\mathbb{Z}/7\mathbb{Z}, +)$	$(\mathbb{Z}/7\mathbb{Z}^*, \times)$
Closure	$a + b \in \mathbb{Z}/7\mathbb{Z}$	$a \cdot b \in \mathbb{Z}/7\mathbb{Z}^*$
Identity	$0$	$1$
Inverses	$-a$	$a^{-1}$
Associativity	$(a+b)+c = a+(b+c)$	$(a \cdot b) \cdot c = a \cdot (b \cdot c)$

A set + an operation + these four properties = a group.

The Four Axioms, Concretely

A group $(G, \star)$ is a set $G$ with a binary operation $\star$ satisfying:

1. Closure: $a \star b \in G$ for all $a, b \in G$

2. Associativity: $(a \star b) \star c = a \star (b \star c)$

3. Identity: There exists $e \in G$ with $e \star a = a \star e = a$ for all $a$

4. Inverses: For every $a \in G$, there exists $a^{-1} \in G$ with $a \star a^{-1} = e$

Checkpoint: In $(\mathbb{Z}/7\mathbb{Z}^*, \times)$, what is the identity element? What is the inverse of 3? Predict before running:

R = Zmod(7)
print(f'Identity of (Z/7Z*, \u00d7): {R(1)}')
print(f'Inverse of 3: {R(3)^(-1)}')
print(f'Check: 3 * {R(3)^(-1)} = {R(3) * R(3)^(-1)}')

A Non-Example: When Axioms Fail

Is $(\mathbb{Z}/6\mathbb{Z}, \times)$, all of $\mathbb{Z}/6\mathbb{Z}$ under multiplication, a group?

# Check (Z/6Z, ×) — is it a group?
R = Zmod(6)
print('Checking (Z/6Z, \u00d7)...')
print(f'Closure? Yes (multiplication of mod 6 elements stays mod 6)')
print(f'Identity? Yes: 1')
print(f'Associativity? Yes (always holds for modular multiplication)')
print()
print('Inverses?')
for x in R:
    if x == 0:
        continue
    try:
        inv = x^(-1)
        print(f'  {x}^(-1) = {inv} \u2713')
    except ZeroDivisionError:
        print(f'  {x}^(-1) = DOES NOT EXIST \u2717  (gcd({x}, 6) = {gcd(ZZ(x), 6)})')

Not a group! Elements 2, 3, and 4 have no multiplicative inverses. The inverse axiom fails.

But if we restrict to just the units $\{1, 5\}$, we get $(\mathbb{Z}/6\mathbb{Z}^*, \times)$, and this IS a group (albeit a tiny one with just 2 elements).

Additive vs. Multiplicative Groups

Here's the key insight:

# (Z/nZ, +) is ALWAYS a group
print('(Z/nZ, +) \u2014 always a group:')
for n in [2, 5, 6, 12, 15]:
    R = Zmod(n)
    print(f'  Z/{n}Z has {n} elements, identity 0, every element has additive inverse')

print()

# (Z/nZ*, ×) size depends on n
print('(Z/nZ*, \u00d7) \u2014 group of units:')
for n in [2, 5, 6, 7, 12, 13, 15]:
    phi = euler_phi(n)
    print(f'  Z/{n}Z* has {phi} elements (out of {n-1} non-zero)', end='')
    if phi == n - 1:
        print(' \u2190 ALL non-zero elements! (n is prime)')
    else:
        print()

Key facts:

• $(\mathbb{Z}/n\mathbb{Z}, +)$ is ALWAYS a group, for any $n \ge 1$. It has $n$ elements.

• $(\mathbb{Z}/n\mathbb{Z}^*, \times)$ is a group of the $\varphi(n)$ units.

• When $n = p$ is prime, $\mathbb{Z}/p\mathbb{Z}^* = \{1, 2, \ldots, p-1\}$ has the maximum $p-1$ elements.

Prime moduli give us the biggest, cleanest multiplicative groups. This is why cryptography loves primes.

Common mistake: "A group is just a set of numbers." No! A group is a set together with an operation. The same set $\{1, 2, 3, 4, 5, 6\}$ forms a group under multiplication mod 7, but NOT under multiplication mod 12 (because $2 \times 6 \equiv 0$ knocks you out of the set). Always specify both the set and the operation.

Exercises

Exercise 1 (Worked)

Verify all 4 axioms for $(\mathbb{Z}/5\mathbb{Z}, +)$.

# Exercise 1 — Verify (Z/5Z, +) is a group
R = Zmod(5)
elems = list(R)
print(f'Elements: {elems}')

# Closure: addition table is all elements of Z/5Z
print('\nClosure (addition table):')
R.addition_table('elements')

# Identity, inverses, associativity for (Z/5Z, +)
R = Zmod(5)
print(f'Identity: 0 (since a + 0 = a for all a)')
print(f'Inverses: 0\u21940, 1\u21944, 2\u21943  (each pair sums to 0)')

# Verify inverses
for x in R:
    print(f'  {x} + {-x} = {x + (-x)}')

# Spot-check associativity
a, b, c = R(2), R(3), R(4)
print(f'\nAssociativity: ({a}+{b})+{c} = {(a+b)+c}, {a}+({b}+{c}) = {a+(b+c)}')
print('All 4 axioms hold \u2014 (Z/5Z, +) is a group. \u2713')

Exercise 2 (Guided)

Check whether $\{1, 2, 3, 4, 5, 6\}$ under multiplication mod 7 is a group. Verify each axiom.

# Exercise 2 — Check ({1,...,6}, × mod 7)
R = Zmod(7)
elements = [R(x) for x in range(1, 7)]
print(f'Set: {elements}')

# TODO: Check closure — is a*b in elements for all a, b?

# TODO: What is the identity element?

# TODO: Find the inverse of each element

# TODO: Spot-check associativity with a triple

Exercise 3 (Independent)

Investigate the set $\{0, 2, 4, 6, 8, 10\}$ under addition mod 12.

Is this a group? If yes, verify each axiom. If no, identify which axiom fails.

Hint: What is this set really? Try computing $\langle 2 \rangle$ in $(\mathbb{Z}/12\mathbb{Z}, +)$.

# Exercise 3 — Your code here

Summary

Concept	Key idea
Group	A set + an operation satisfying closure, associativity, identity, and inverses
$(\mathbb{Z}/n\mathbb{Z}, +)$	Always a group, for any $n$
$(\mathbb{Z}/n\mathbb{Z}^*, \times)$	A group of the $\varphi(n)$ units (elements coprime to $n$)
Prime moduli	When $n$ is prime, $(\mathbb{Z}/n\mathbb{Z}^*, \times)$ has the maximum $n - 1$ elements
Non-examples	Checking where axioms fail (like missing inverses) sharpens your understanding

The group axioms capture the shared structure behind addition and multiplication. Once you see this pattern, you'll recognize it everywhere in cryptography.

Crypto teaser: Diffie-Hellman key exchange works inside $(\mathbb{Z}/p\mathbb{Z}^*, \times)$. The security depends on this group being large enough that brute force is impossible. In the next notebook, we'll discover that some elements of this group are more powerful than others.

Next: Cyclic Groups and Generators, some elements can regenerate the entire group by themselves.