02d-what-is-a-field.ipynb

Kernel: SageMath 10.5

What Is a Field?

Module 02 | 02-rings-fields-polynomials

Every nonzero element invertible, $\mathbb{Z}/p\mathbb{Z}$ is a field iff $p$ is prime

Objectives

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

1. Define a field and explain how it differs from a ring.

2. Prove computationally that $\mathbb{Z}/p\mathbb{Z}$ is a field exactly when $p$ is prime.

3. Build complete multiplication and inverse tables for a prime field.

4. Identify familiar fields ($\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$) and non-fields ($\mathbb{Z}$, $\mathbb{Z}/12\mathbb{Z}$).

5. Explain why cryptography requires fields, not just rings.

Prerequisites

• Completion of Integers Mod n as a Ring, you should know what units and zero divisors are.

• Completion of Polynomial Rings, you've seen rings with different coefficient sets.

• Concepts: ring axioms, $\mathbb{Z}/n\mathbb{Z}$, $\gcd$.

Motivating Question

In notebook 02b, we discovered that $\mathbb{Z}/12\mathbb{Z}$ has units (elements with multiplicative inverses) and zero divisors (nonzero elements whose product is zero). For instance, $3$ has no inverse in $\mathbb{Z}/12\mathbb{Z}$, you simply cannot "divide by 3" in that ring.

Question: Is there a version of modular arithmetic where you can divide by anything nonzero? In other words: can we find a ring $\mathbb{Z}/n\mathbb{Z}$ where every nonzero element is a unit?

The answer is yes, and such a ring earns a special name: a field. Let's discover which values of $n$ make this work.

From Rings to Fields: The Key Upgrade

Recall that a ring $(R, +, \cdot)$ gives us addition and multiplication with the usual nice properties (associativity, distributivity, additive inverses, etc.).

A field is a commutative ring with one crucial extra property:

Field axiom: For every $a \neq 0$ in $F$, there exists $a^{-1} \in F$ such that $a \cdot a^{-1} = 1$.

In other words: every nonzero element is a unit.

More precisely, a field is a commutative ring $F$ with $0 \neq 1$ where every nonzero element has a multiplicative inverse.

---

Bridge from 02b: In $\mathbb{Z}/12\mathbb{Z}$, we found that the units were $\{1, 5, 7, 11\}$, only 4 out of 11 nonzero elements. The rest were zero divisors. In a field, the set of units equals the set of all nonzero elements. Zero divisors are completely eliminated.

---

Misconception alert: "A field is just a ring with multiplicative inverses." Almost, but you also need (1) multiplication to be commutative, and (2) the ring to be nontrivial, meaning $0 \neq 1$. The trivial ring $\{0\}$ (where $0 = 1$) satisfies every other axiom but is not a field.

The Problem with $\mathbb{Z}/12\mathbb{Z}$: Zero Divisors Block Invertibility

Let's revisit $\mathbb{Z}/12\mathbb{Z}$ and see concretely why it fails to be a field. We'll classify every nonzero element as either a unit or a zero divisor.

# Classify every nonzero element of Z/12Z
R = Zmod(12)
units = []
zero_divisors = []

for a in R:
    if a == 0:
        continue
    if gcd(ZZ(a), 12) == 1:
        inv = R(a)^(-1)
        units.append((a, inv))
    else:
        # Find a witness b != 0 with a*b == 0
        witness = next(b for b in R if b != 0 and a*b == 0)
        zero_divisors.append((a, witness))

print("=== Z/12Z: Units vs Zero Divisors ===")
print(f"\nUnits ({len(units)} out of 11 nonzero elements):")
for a, inv in units:
    print(f"  {a} is a unit:  {a} * {inv} = 1")

print(f"\nZero divisors ({len(zero_divisors)} out of 11 nonzero elements):")
for a, b in zero_divisors:
    print(f"  {a} is a zero divisor:  {a} * {b} = 0")

print(f"\nIs Z/12Z a field? {R.is_field()}")
print("Reason: not every nonzero element has an inverse.")

Only 4 out of 11 nonzero elements are invertible. The other 7 are zero divisors, they "kill" information when you multiply. You cannot undo multiplication by 3 in $\mathbb{Z}/12\mathbb{Z}$, because $3 \times 4 = 0$ means the function $x \mapsto 3x$ is not injective.

Key connection: An element is a zero divisor if and only if it is not a unit (in $\mathbb{Z}/n\mathbb{Z}$). So having zero divisors and failing to be a field are two sides of the same coin.

$\mathbb{Z}/p\mathbb{Z}$ Is a Field When $p$ Is Prime

Now the punchline. Let's check: for which values of $n$ is $\mathbb{Z}/n\mathbb{Z}$ a field?

Checkpoint (predict before running): Look at the list $n = 2, 3, 4, \ldots, 20$. For which values of $n$ do you think every nonzero element of $\mathbb{Z}/n\mathbb{Z}$ will have an inverse? What pattern do you expect?

# Which Z/nZ are fields? Let's find out.

for n in range(2, 21):
    R = Zmod(n)
    num_units = euler_phi(n)
    num_nonzero = n - 1
    is_f = R.is_field()
    marker = " <-- FIELD" if is_f else ""

print("\nPattern: Z/nZ is a field exactly when n is prime!")
print("Reason: if p is prime, gcd(a, p) = 1 for every 0 < a < p,")
print("so every nonzero element is a unit (# units = p - 1 = # nonzero).")

Why Does Primality Guarantee a Field?

Here is the key reasoning:

1. An element $a \in \mathbb{Z}/n\mathbb{Z}$ is a unit $\iff$ $\gcd(a, n) = 1$ (we proved this in 02b).

2. If $p$ is prime and $0 < a < p$, then $p$ cannot divide $a$, so $\gcd(a, p) = 1$.

3. Therefore every nonzero element of $\mathbb{Z}/p\mathbb{Z}$ is a unit.

4. And there are no zero divisors (other than 0 itself).

Conversely, if $n$ is composite, say $n = a \cdot b$ with $1 < a, b < n$, then $a \cdot b \equiv 0 \pmod{n}$, giving us a zero divisor. So $\mathbb{Z}/n\mathbb{Z}$ is a field if and only if $n$ is prime.

This is why prime fields are written $\mathbb{F}_p$ or $\text{GF}(p)$ ("Galois Field of order $p$").

Building the Complete Multiplication Table for $\mathbb{Z}/7\mathbb{Z}$

Checkpoint: Before we build the multiplication table, predict: will there be any zeros in the table (other than in the row/column for 0)? What would a zero entry mean?

Let's build the full multiplication table for $\mathbb{F}_7 = \mathbb{Z}/7\mathbb{Z}$ and verify that the nonzero elements form a closed multiplicative system with no zeros sneaking in.

# Full multiplication table for Z/7Z
F = GF(7)
elements = list(F)

# Print header
header = "  * |" + "".join(f"{ZZ(a)}" for a in elements)
print(header)
print("-" * len(header))

# Print each row
for a in elements:
    row = f"  {ZZ(a)} |" + "".join(f"{ZZ(a*b)}" for b in elements)
    print(row)

# Highlight: no zeros appear in the nonzero-by-nonzero block
print("\nNotice: in the 6x6 block of nonzero rows and columns,")
print("every entry is nonzero. No zero divisors exist!")
print("Each nonzero row is a permutation of {1, 2, 3, 4, 5, 6}.")

That last observation is crucial: each nonzero row of the multiplication table is a permutation of $\{1, 2, 3, 4, 5, 6\}$. This means:

• Every nonzero value appears exactly once in each row.

• In particular, 1 appears in every row, so every nonzero element has an inverse.

• The function $x \mapsto ax$ is a bijection on $\mathbb{F}_7^*$ for any $a \neq 0$.

This is the defining feature of a field: multiplication by any nonzero element is always reversible.

The Inverse Table for $\mathbb{F}_7$

Now let's build the complete inverse table. For each nonzero $a \in \mathbb{F}_7$, we find $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod{7}$.

# Complete inverse table for F_7
F = GF(7)
print("Inverse table for F_7 = Z/7Z:")

for a in F:
    if a == 0:
        continue
    inv = a^(-1)

print("\nEvery nonzero element has a unique inverse.")
print("Notice: 1 and 6 are self-inverse (1*1=1, 6*6=36=1 mod 7).")
print("The others pair up: 2<->4, 3<->5.")

Familiar Fields and Non-Fields

Fields are everywhere in mathematics. Let's check which familiar number systems are fields:

Structure	Field?	Reason
$\mathbb{Q}$ (rationals)	Yes	Every nonzero $\frac{a}{b}$ has inverse $\frac{b}{a}$
$\mathbb{R}$ (reals)	Yes	Every nonzero real has a reciprocal
$\mathbb{C}$ (complex)	Yes	Every nonzero $a + bi$ has inverse $\frac{a - bi}{a^2 + b^2}$
$\mathbb{Z}$ (integers)	No	$2$ has no integer inverse ($1/2 \notin \mathbb{Z}$)
$\mathbb{Z}/12\mathbb{Z}$	No	$3 \times 4 = 0$ (zero divisors)
$\mathbb{Z}/7\mathbb{Z}$	Yes	Every nonzero element coprime to 7

Let's verify with SageMath:

# Check which standard structures are fields
structures = [
    ("QQ (rationals)", QQ),
    ("RR (reals)", RR),
    ("CC (complex)", CC),
    ("ZZ (integers)", ZZ),
    ("Z/12Z", Zmod(12)),
    ("Z/7Z = GF(7)", GF(7)),
]

for name, R in structures:
    print(f"{name}  is_field: {R.is_field()}")

# Why Z is not a field: try to invert 2
print("\nWhy ZZ is not a field:")
print(f"  2 in ZZ: is 1/2 an integer? {1/2 in ZZ}")
print(f"  2 in QQ: is 1/2 a rational? {1/2 in QQ}")
print("  You need to 'enlarge' Z to Q to get inverses for all nonzero elements.")

The Smallest Field: $\text{GF}(2) = \{0, 1\}$

The smallest possible field has just two elements: $0$ and $1$. Its arithmetic is surprisingly familiar:

• Addition in $\text{GF}(2)$ is XOR: $0+0=0,\ 0+1=1,\ 1+0=1,\ 1+1=0$

• Multiplication in $\text{GF}(2)$ is AND: $0 \cdot 0=0,\ 0 \cdot 1=0,\ 1 \cdot 0=0,\ 1 \cdot 1=1$

The only nonzero element is $1$, and $1^{-1} = 1$. Done, it's trivially a field!

Crypto foreshadowing: $\text{GF}(2)$ is the foundation of all binary arithmetic in cryptography. AES operates over $\text{GF}(2^8)$, an extension field with 256 elements that we'll construct in Module 03. Every byte in AES is an element of this field, and the MixColumns step is literally matrix multiplication over $\text{GF}(2^8)$.

# GF(2): the smallest field
F2 = GF(2)

print("GF(2) Addition table (= XOR):")
print("  + | 0  1")
print("  ---------")
for a in F2:
    row = f"  {ZZ(a)} | {ZZ(a + F2(0))}  {ZZ(a + F2(1))}"
    print(row)

print("\nGF(2) Multiplication table (= AND):")
print("  * | 0  1")
print("  ---------")
for a in F2:
    row = f"  {ZZ(a)} | {ZZ(a * F2(0))}  {ZZ(a * F2(1))}"
    print(row)

print(f"\nThe only nonzero element is 1, and 1^(-1) = {F2(1)^(-1)}")
print(f"Is GF(2) a field? {F2.is_field()}")
print(f"Order: {F2.order()} (the smallest possible field)")

Why Fields Matter for Cryptography

In cryptography, we constantly need to divide, that is, multiply by an inverse. Here's why:

• RSA uses modular arithmetic in $\mathbb{Z}/n\mathbb{Z}$ (not a field!), but key generation requires working in the unit group. The security relies on the difficulty of factoring $n$ to find the structure of that unit group.

• Elliptic curve cryptography defines curves over prime fields $\mathbb{F}_p$. The point addition formula requires dividing by differences of coordinates, this only works if every nonzero element has an inverse.

• AES performs byte-level arithmetic in $\text{GF}(2^8)$. The SubBytes step computes multiplicative inverses in this field.

• Shamir's Secret Sharing evaluates polynomials over $\mathbb{F}_p$ and reconstructs secrets using Lagrange interpolation, which requires dividing by $(x_i - x_j)$ for distinct points.

In a ring that isn't a field, some of these divisions would fail, leading to broken cryptosystems. Fields give us the guarantee: if it's nonzero, you can divide by it.

The slogan: Rings let you add, subtract, and multiply. Fields let you do all of that and divide (by anything nonzero). Cryptography needs division, so cryptography needs fields.

Exercises

Exercise 1: Inverse Table for $\mathbb{F}_{11}$ (Fully Worked)

Task: Build the complete inverse table for $\mathbb{F}_{11} = \mathbb{Z}/11\mathbb{Z}$ and verify that every nonzero element has an inverse.

# EXERCISE 1, Fully worked solution

# Step 1: Create the field F_11
F11 = GF(11)

# Step 2: Build the inverse table
print("Inverse table for F_11 = Z/11Z:")

inverse_pairs = []
for a in range(1, 11):
    a_field = F11(a)
    inv = a_field^(-1)
    check = a_field * inv
    print(f"{a} | {ZZ(inv)} | {a} * {ZZ(inv)} = {ZZ(check)} mod 11")
    inverse_pairs.append((a, ZZ(inv)))

# Step 3: Verify completeness, every nonzero element appeared as an inverse
inverse_values = sorted(set(b for _, b in inverse_pairs))
print(f"\nAll inverses: {inverse_values}")
print(f"All nonzero elements: {list(range(1, 11))}")
print(f"Every nonzero element appears as someone's inverse: {inverse_values == list(range(1, 11))}")

# Step 4: Identify self-inverse elements (a = a^(-1), i.e., a^2 = 1)
self_inv = [a for a, b in inverse_pairs if a == b]
print(f"\nSelf-inverse elements (a^2 = 1 mod 11): {self_inv}")
print("These are the square roots of 1 in F_11.")

Exercise 2: Field Detective (Guided with TODOs)

Task: For each ring below, determine whether it is a field by checking two things:

1. Does it have zero divisors?

2. Is every nonzero element a unit?

Fill in the TODO sections.

# EXERCISE 2, Guided: fill in the TODOs

test_moduli = [6, 13, 15, 17, 21, 23]

for n in test_moduli:
    R = Zmod(n)

    # TODO 1: Count how many nonzero elements are units.
    # Hint: an element a is a unit in Z/nZ iff gcd(a, n) == 1.
    # Replace 'None' with the correct count.
    num_units = None  # TODO: compute this

    # TODO 2: Count how many nonzero elements exist.
    num_nonzero = None  # TODO: compute this

    # TODO 3: Determine if it's a field. A ring is a field iff
    # every nonzero element is a unit, i.e., num_units == num_nonzero.
    is_field = None  # TODO: compute this from num_units and num_nonzero

    print(f"Z/{n}Z: {num_units} units out of {num_nonzero} nonzero elements -> field? {is_field}")

# TODO 4: After running, answer this question in a comment:
# What is the relationship between n being prime and Z/nZ being a field?
# Your answer: ...

Exercise 3: Division in a Field (Independent)

Task: In $\mathbb{F}_{13}$, compute the following "divisions" by finding multiplicative inverses. No starter code is provided, write it from scratch.

1. Compute $7 / 5 \pmod{13}$ (i.e., find $7 \cdot 5^{-1} \bmod 13$).

2. Compute $3 / 9 \pmod{13}$.

3. Verify your answers: if $7/5 = c$, then $c \cdot 5$ should equal $7$.

4. Challenge: Can you compute $0 / 5 \pmod{13}$? What about $7 / 0$? Explain the difference.

Hint: In SageMath, if F = GF(13), then F(a) / F(b) computes the field division directly, or you can manually compute F(a) * F(b)^(-1).

# EXERCISE 3, Independent: write your solution below

Summary

Concept	Key idea
Field	A commutative ring (with $0 \neq 1$) where every nonzero element has a multiplicative inverse. Equivalently, a field has no zero divisors
$\mathbb{Z}/n\mathbb{Z}$ is a field iff $n$ is prime	When $n$ is prime, $\gcd(a, n) = 1$ for all $0 < a < n$, so every nonzero element is invertible
Familiar fields and non-fields	$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, and $\mathbb{F}_p$ are fields. $\mathbb{Z}$ (no integer inverse for 2) and $\mathbb{Z}/12\mathbb{Z}$ (zero divisors) are not
$\text{GF}(2)$, the smallest field	Just $\{0, 1\}$, where addition is XOR and multiplication is AND
Crypto needs fields	Protocols require division (multiplication by inverse) for every nonzero element. Elliptic curves, AES, and secret sharing all rely on field arithmetic

Looking ahead: We've seen that $\mathbb{F}_p$ gives us one field for each prime $p$. But AES uses a field with $2^8 = 256$ elements, and 256 is not prime! How can that be a field? The answer involves polynomial quotient rings, which we'll explore starting in the next notebook.

Next: Polynomial Division and Irreducibility