01b-modular-arithmetic.ipynb

Kernel: Python 3

# This notebook has two versions:
#   Python (this file) -- runs in browser via JupyterLite, no install needed
#   SageMath (../sage/) -- richer algebra system, needs local install or Codespaces
#
# Both versions cover the same material. Choose whichever works for you.

import sys, os
sys.path.insert(0, os.path.join('..', '..', '..', 'shared'))

from cryptolab import Mod, Zmod, euler_phi, gcd

Modular Arithmetic

Module 01b | Modular Arithmetic and Groups

What if remainders aren't just leftovers, but a complete number system?

Question: On a 12-hour clock, 7 + 8 = 3. You can always "undo" addition (subtract). But can you always "undo" multiplication? Is there a number $x$ such that $3 \times x = 1$ on the clock?

The answer reveals a deep split in modular arithmetic: some elements play nicely, others don't.

Objectives

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

1. Perform addition and multiplication in $\mathbb{Z}/n\mathbb{Z}$ using SageMath

2. Read and interpret operation tables to spot algebraic structure

3. Identify zero divisors and explain why they break multiplication

4. List the units of $\mathbb{Z}/n\mathbb{Z}$ and connect them to $\gcd$

From Remainders to a Number System

In 01a we saw that Mod(a, n) creates elements that live in a "remainder world" where arithmetic wraps around. Now let's take this seriously: what if we treat these remainders as a complete number system, with its own addition, multiplication, and algebraic rules?

This system is called $\mathbb{Z}/n\mathbb{Z}$ (read "Z mod n Z"). It has exactly $n$ elements: $\{0, 1, 2, \ldots, n-1\}$.

$\mathbb{Z}/n\mathbb{Z}$ as a Number System

Zmod(n) from cryptolab creates the ring $\mathbb{Z}/n\mathbb{Z}$. Let's explore it.

# Create Z/7Z and list its elements
R = Zmod(7)
print('Elements of Z/7Z:', list(R))
print('Number of elements:', R.order())

# Arithmetic inside Z/7Z
R = Zmod(7)
a, b = R(3), R(5)
print(f'{a} + {b} = {a + b}')   # 3 + 5 = 1 (wraps past 7)
print(f'{a} * {b} = {a * b}')   # 3 * 5 = 1 (since 15 = 2*7 + 1)
print(f'{a} - {b} = {a - b}')   # 3 - 5 = 5 (since -2 ≡ 5 mod 7)

Checkpoint: Before running the next cell, predict: what is $4 \times 3$ in $\mathbb{Z}/7\mathbb{Z}$? What about $4 \times 2$?

R = Zmod(7)
print(f'4 * 3 = {R(4) * R(3)}')
print(f'4 * 2 = {R(4) * R(2)}')

Operation Tables Reveal Structure

An operation table shows every possible computation at a glance. Let's compare addition and multiplication in $\mathbb{Z}/7\mathbb{Z}$.

# Addition table for Z/7Z
R = Zmod(7)
print('Addition table for Z/7Z:')
R.addition_table('elements')

# Multiplication table for Z/7Z
print('Multiplication table for Z/7Z:')
R.multiplication_table('elements')

Look at the addition table: every row contains each element exactly once (it's a Latin square). This means for any $a$ and $b$, the equation $a + x = b$ has exactly one solution, you can always "undo" addition.

Now look at the multiplication table: the row for 0 is all zeros (no surprise). But every other row is also a Latin square! In $\mathbb{Z}/7\mathbb{Z}$, you can "undo" multiplication too, every non-zero element has a multiplicative inverse.

Will this always happen? Let's try a composite modulus.

Zero Divisors: When Multiplication Breaks

Let's look at $\mathbb{Z}/12\mathbb{Z}$.

# Multiplication in Z/12Z, look for trouble
R = Zmod(12)
print('Some products in Z/12Z:')
print(f'3 * 4 = {R(3) * R(4)}')  # = 0!
print(f'2 * 6 = {R(2) * R(6)}')  # = 0!
print(f'4 * 9 = {R(4) * R(9)}')  # = 0!
print('\nThese are ZERO DIVISORS: non-zero elements whose product is 0.')

Checkpoint: In $\mathbb{Z}/12\mathbb{Z}$, we found $3 \times 4 = 0$. Why is this a problem? Think about it: if you could "divide by 3," then from $3 \times 4 = 0$ you'd get $4 = 0$. But $4 \neq 0$! Zero divisors make division impossible.

# Which elements are zero divisors?
R = Zmod(12)
print('Zero divisors in Z/12Z (elements a where a*b=0 for some b\u22600):')
for a in range(1, 12):
    for b in range(1, 12):
        if R(a) * R(b) == 0:
            print(f'  {a} * {b} = 0   (gcd({a}, 12) = {gcd(a, 12)})')
            break

Pattern: Element $a$ is a zero divisor in $\mathbb{Z}/n\mathbb{Z}$ if and only if $\gcd(a, n) > 1$. When $n$ is prime, $\gcd(a, n) = 1$ for all $a \neq 0$, so there are NO zero divisors. This is why prime moduli are special.

Units: The Elements That Behave

The units of $\mathbb{Z}/n\mathbb{Z}$ are elements with multiplicative inverses: $a$ is a unit if there exists $b$ with $a \cdot b = 1$.

# Find units of Z/12Z
R = Zmod(12)
units = [a for a in range(1, 12) if gcd(a, 12) == 1]
print(f'Units of Z/12Z: {units}')
print(f'Number of units: {len(units)} = euler_phi(12) = {euler_phi(12)}')
print()
for u in units:
    inv = Mod(u, 12)**(-1)
    print(f'  {u} * {inv} = {Mod(u,12) * inv}')

# Compare: units of Z/pZ when p is prime
for p in [5, 7, 11, 13]:
    units = [a for a in range(1, p) if gcd(a, p) == 1]
    print(f'Units of Z/{p}Z: {units}  (count: {len(units)} = {p}-1)')

When $n = p$ is prime, every non-zero element is a unit: $\mathbb{Z}/p\mathbb{Z}^* = \{1, 2, \ldots, p-1\}$ has $p-1$ elements. For composite $n$, only the elements coprime to $n$ are units, and there are $\varphi(n)$ of them.

The units form their own self-contained system, you can multiply and divide freely within them. This system will turn out to be a group, which we'll study in the next notebook.

Common mistake: "$\mathbb{Z}/n\mathbb{Z}$ is just the integers with a mod operation stuck on." No! It's a complete number system with its own rules. In $\mathbb{Z}/12\mathbb{Z}$, the number 3 has no multiplicative inverse, not because we haven't looked hard enough, but because $3 \times 4 = 0$ proves it cannot exist. You can't "cancel" 3 when it annihilates 4.

Exercises

Exercise 1 (Worked)

Build the multiplication table for $\mathbb{Z}/8\mathbb{Z}$. Identify all zero divisors. For each, find a non-zero $b$ with $a \cdot b = 0$, and verify $\gcd(a, 8) > 1$.

# Exercise 1: Worked solution
R = Zmod(8)
R.multiplication_table('elements')

# Zero divisors in Z/8Z
R = Zmod(8)
print('Zero divisors of Z/8Z:')
for a in range(1, 8):
    for b in range(1, 8):
        if R(a) * R(b) == 0:
            print(f'  {a} * {b} = 0, gcd({a}, 8) = {gcd(a, 8)}')
            break
print(f'\nUnits of Z/8Z: {[a for a in range(1,8) if gcd(a,8)==1]}')

Exercise 2 (Guided)

List the units of $\mathbb{Z}/15\mathbb{Z}$. For each unit $u$, find $u^{-1}$ using Mod(u, 15)^(-1). Verify that the number of units equals $\varphi(15)$.

Compute $\varphi(15)$ by hand: $\varphi(15) = 15 \cdot (1 - 1/3) \cdot (1 - 1/5) = ?$

# Exercise 2: Find units and their inverses
n = 15
units = [a for a in range(1, n) if gcd(a, n) == 1]
print(f'Units of Z/{n}Z: {units}')

for u in units:
    # TODO: compute the inverse of u mod n and print it
    pass

# TODO: verify len(units) == euler_phi(15)

Exercise 3 (Independent)

For each $n$ from 2 to 20, compute the number of zero divisors in $\mathbb{Z}/n\mathbb{Z}$. (A zero divisor is a non-zero element $a$ with $a \cdot b = 0$ for some non-zero $b$.)

For which $n$ are there no zero divisors? State a conjecture about what these $n$ have in common.

# Exercise 3: Your code here

Summary

Concept	Key idea
$\mathbb{Z}/n\mathbb{Z}$	A complete number system with $n$ elements where arithmetic wraps at $n$
Zero divisors	Non-zero elements with $a \cdot b = 0$, they exist exactly when $\gcd(a, n) > 1$
Units	Elements with multiplicative inverses, exactly those with $\gcd(a, n) = 1$
$\varphi(n)$	Counts the units. When $n$ is prime, $\varphi(n) = n - 1$ (every non-zero element is a unit)
Prime vs. composite	Prime moduli have no zero divisors and the maximum number of units

Zero divisors and units are two sides of the same coin: an element is one or the other, determined entirely by its gcd with $n$. This split shapes all of modular algebra.

Crypto teaser: RSA works in $\mathbb{Z}/n\mathbb{Z}$ where $n = p \cdot q$. The number of units $\varphi(n) = (p-1)(q-1)$ is the secret that makes decryption possible, and it can only be computed if you know the factorization of $n$.

Next: Groups: A First Look, we extract the common pattern behind additive and multiplicative arithmetic.