Fields

Fields

A field $(F, +, \cdot)$ is a commutative ring with unity where every nonzero element has a multiplicative inverse. Equivalently:

1. $(F, +)$ is an abelian group with identity $0$
2. $(F \setminus \{0\}, \cdot)$ is an abelian group with identity $1$
3. Multiplication distributes over addition

$\mathbb{Z}_p$ is a Field

When $p$ is prime, $\mathbb{Z}_p$ is a field. Every nonzero element $a$ has a multiplicative inverse, computable by:

$a^{-1} \equiv a^{p-2} \pmod{p}$

This follows from Fermat's little theorem: $a^{p-1} \equiv 1 \pmod{p}$.

def mod_inverse(a, p):
    # Using Fermat's little theorem
    return pow(a, p - 2, p)

Why Composites Don't Work

$\mathbb{Z}_6$ is not a field because $2 \cdot 3 = 0$ — zero divisors exist. An element has a multiplicative inverse if and only if it is coprime to $n$.

Field Multiplication Table

For $\mathbb{Z}_5$:

Every row is a permutation of $\{1,2,3,4\}$ — this is a hallmark of a field.

Your Task

Implement is_field(n) that checks if $\mathbb{Z}_n$ is a field, mod_inverse(a, p) computing $a^{-1}$ in $\mathbb{Z}_p$, and mul_table(p) returning the multiplication table for the nonzero elements of $\mathbb{Z}_p$.