The Ring $\mathbb{Z}_n$

In the previous note we wrote out the addition and multiplication tables for arithmetic modulo $5$. That is enough material to sit down and start treating "the integers $\bmod 5$" as a ring in its own right, with five elements instead of infinitely many. This note does the bookkeeping, names the structure $\mathbb{Z}_n$, checks the ring axioms, and finds the criterion that decides when $\mathbb{Z}_n$ is also a field.

Definition of $\mathbb{Z}_n$

For any integer $n \ge 2$, the ring of integers modulo $n$ is the set

$$\mathbb{Z}_n \;=\; \{0,\, 1,\, 2,\, \ldots,\, n-1\}$$

together with addition and multiplication defined modulo $n$. So in $\mathbb{Z}_n$, the rule $a + b$ means "ordinary integer addition, then reduce modulo $n$", and the rule $a \cdot b$ means "ordinary integer multiplication, then reduce modulo $n$".

Some books write $\mathbb{Z}/n\mathbb{Z}$ for the same object, with the slash explicit. The two notations mean exactly the same thing. We will write $\mathbb{Z}_n$ throughout because it is shorter and matches what cryptography papers use.

For $n = 5$, the ring is $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ with the tables you saw at the end of the previous note. For $n = 4$, the ring is $\mathbb{Z}_4 = \{0, 1, 2, 3\}$. For $n = 2$, the smallest non-trivial case, the ring is $\mathbb{Z}_2 = \{0, 1\}$ and is exactly the "keep only the last bit" arithmetic from the closure note.

02.Checking the ring axioms

The ring axioms from Groups, Rings, and Fields need to be verified for $\mathbb{Z}_n$.

The additive group $(\mathbb{Z}_n, +)$. Closure holds because the rule "reduce modulo $n$" lands the answer back in $\{0, \ldots, n-1\}$ by construction. Associativity and commutativity are inherited from ordinary integer addition. The identity is $0$, since $a + 0 = a$ for every $a$. The additive inverse of $a$ is $n - a$ for $a \neq 0$, and $0$ for $a = 0$, since $a + (n - a) = n \equiv 0 \pmod n$. So every element has an additive inverse. $(\mathbb{Z}_n, +)$ is an abelian group.

Multiplication. Closure holds for the same reason. Associativity and commutativity are inherited. The identity is $1$, since $a \cdot 1 = a$. So multiplication is an associative, commutative operation with an identity.

Distributivity. Inherited from integer arithmetic and preserved by reduction.

That is all four parts of "commutative ring". $\mathbb{Z}_n$ is a commutative ring for every $n \ge 2$.

The interesting question is whether $\mathbb{Z}_n$ is a field. Recall the extra condition: every non-zero element must have a multiplicative inverse. In $\mathbb{Z}_5$, every non-zero residue does have one (read the multiplication table: every row past zero contains a $1$). In $\mathbb{Z}_4$, the residue $2$ has no inverse: $2 \cdot 0 = 0$, $2 \cdot 1 = 2$, $2 \cdot 2 = 0$, $2 \cdot 3 = 2$, none of which is $1$. So $\mathbb{Z}_4$ is a ring but not a field.

What is special about $5$ that fails for $4$?

The criterion: $\mathbb{Z}_n$ is a field if and only if $n$ is prime

A prime is a positive integer greater than $1$ whose only positive divisors are $1$ and itself. The primes start $2, 3, 5, 7, 11, 13, \ldots$. The number $4$ is not prime because $4 = 2 \cdot 2$. The number $5$ is prime.

The exact statement is: $\mathbb{Z}_n$ is a field if and only if $n$ is prime.

The intuition is short. An element $a \in \mathbb{Z}_n$ has a multiplicative inverse precisely when $\gcd(a, n) = 1$, that is, when $a$ shares no common factor with $n$ greater than $1$. If $n$ is prime, then for every $a \in \{1, 2, \ldots, n-1\}$, no such $a$ shares a factor with $n$ (since the only factors of $n$ are $1$ and $n$ itself, and $a$ is strictly less than $n$). So every non-zero residue is invertible, and $\mathbb{Z}_n$ is a field.

If $n$ is composite, say $n = ab$ with $1 < a, b < n$, then $a$ is a non-zero residue with $\gcd(a, n) = a > 1$, so $a$ has no inverse. So $\mathbb{Z}_n$ is missing inverses for at least one element, which disqualifies it from being a field.

The "if and only if" part also gives a clean way to compute inverses when $n$ is prime: use the extended Euclidean algorithm on the pair $(a, n)$. Because $\gcd(a, n) = 1$, the algorithm finds integers $u$ and $v$ such that

$$u \cdot a + v \cdot n \;=\; 1.$$

Reducing modulo $n$ kills the $v \cdot n$ term, leaving $u \cdot a \equiv 1 \pmod n$. So $u \bmod n$ is the inverse of $a$ in $\mathbb{Z}_n$.

A small worked example. Find the inverse of $3$ in $\mathbb{Z}_5$. The extended Euclidean algorithm on $(3, 5)$:

$5 = 1 \cdot 3 + 2$, then $3 = 1 \cdot 2 + 1$, then $2 = 2 \cdot 1 + 0$. Reading back: $1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (5 - 1 \cdot 3) = 2 \cdot 3 - 1 \cdot 5$. So $u = 2$ and $v = -1$, and $2 \cdot 3 \equiv 1 \pmod 5$. Therefore $3^{-1} = 2$ in $\mathbb{Z}_5$.

You can check this against the multiplication table: row $3$, column $2$ is $1$. So multiplying $3$ by $2$ gives the multiplicative identity, exactly as the algorithm predicted.

A second worked example: $\mathbb{Z}_{17}$

The next prime after $5$ that we will see in cryptographic worked examples is $17$. The ring $\mathbb{Z}_{17}$ has $17$ elements: $\{0, 1, 2, \ldots, 16\}$. It is a field because $17$ is prime.

A $17 \times 17$ multiplication table is too big to enjoy, but we can spot-check a row. Take $a = 5$ and compute $5 \cdot k \bmod 17$ for $k = 0, 1, \ldots, 16$:

Every entry from $0$ through $16$ appears exactly once, which is the same hallmark we noticed for $\mathbb{Z}_5$. So $5$ is a unit (an element with a multiplicative inverse) in $\mathbb{Z}_{17}$, and the inverse is read off the table as the value of $k$ that gives $5k \equiv 1 \pmod{17}$. Looking at the row, that is $k = 7$, since $5 \cdot 7 = 35 = 2 \cdot 17 + 1$. So $5^{-1} = 7$ in $\mathbb{Z}_{17}$.

05.Why finite fields, why now

We have just constructed an infinite family of finite fields, one for each prime $n$:

$$\mathbb{F}_2,\; \mathbb{F}_3,\; \mathbb{F}_5,\; \mathbb{F}_7,\; \mathbb{F}_{11},\; \mathbb{F}_{13},\; \mathbb{F}_{17},\; \ldots$$

The notation $\mathbb{F}_p$ (with $p$ prime) is the standard one for "the finite field with $p$ elements". The notation $\mathbb{Z}_p$ for the same object is also standard. We will use $\mathbb{Z}_q$ throughout for the cryptographic case, since that is what the post-quantum literature uses.

For Kyber, the field is $\mathbb{Z}_q$ with $q = 3329$, a prime. For Dilithium, it is $\mathbb{Z}_q$ with $q = 8\,380\,417$, also prime. The schemes work because these moduli are primes: arithmetic is invertible everywhere except at zero, and the polynomial machinery built in the next notes goes through cleanly.

For now, the takeaway is that we have moved from a casual "wrap around at $n$" picture to a rigorous structure $\mathbb{Z}_n$ that is always a ring and is a field exactly when $n$ is prime. Every later structure in this chapter will be built using $\mathbb{Z}_n$ as a starting ingredient.

06.A short exercise

In each case, decide whether the ring is a field, and if so, compute the requested inverse.

1. Is $\mathbb{Z}_6$ a field? No: $6 = 2 \cdot 3$, so $2$ has no inverse modulo $6$. The non-zero element $2$ in $\mathbb{Z}_6$ multiplied by anything gives $0, 2, 4, 0, 2, 4$, never $1$.
2. Is $\mathbb{Z}_7$ a field? Yes: $7$ is prime. Find $3^{-1}$ in $\mathbb{Z}_7$. Try multiples of $3$ modulo $7$: $3, 6, 2, 5, 1$. The fifth multiple, $3 \cdot 5 = 15 \equiv 1$, gives $3^{-1} = 5$.
3. Is $\mathbb{Z}_{10}$ a field? No: $10 = 2 \cdot 5$. The element $5$ in $\mathbb{Z}_{10}$ multiplied by anything gives $0$ or $5$, never $1$.

These cases show the criterion in action and how a single "missing inverse" is enough to disqualify a ring from being a field.

The next note moves from numbers to polynomials. Polynomials whose coefficients live in $\mathbb{Z}_q$ are the basic objects of post-quantum schemes, and they form a ring of their own.