Modular Arithmetic

If you add eight hours to nine o'clock, you get five o'clock, not seventeen o'clock. The clock face has only twelve numbers on it, so anything that goes past twelve "wraps around" and starts again from one. That kind of arithmetic, where the answer cycles back to the start once it gets too big, is called modular arithmetic. It is the engine that runs almost every modern cryptosystem. This note builds it up properly.

01.The clock face

The clock face has the numbers $1$ through $12$ arranged in a circle. Walking around the circle and counting hours has a built-in wrap-around: every twelve hours brings you back to where you started. So the answer to "what time is it eight hours after nine?" is $5$, not $17$, because the hand has gone past $12$ and is now four steps further on.

A cleaner way to describe what is happening: take the ordinary integer answer ($9 + 8 = 17$) and subtract $12$ until the result lands in the range $\{1, 2, \ldots, 12\}$. One subtraction is enough here, giving $5$.

Mathematically, it is even cleaner to use the range $\{0, 1, \ldots, 11\}$ instead of $\{1, 2, \ldots, 12\}$: it makes the arithmetic uniform, and matches what computers do. With that convention, "$5$" on a $12$-clock means "$5$ steps past noon" and "$0$" means "noon" or "midnight". The wrap-around point is the modulus $12$, which is identified with $0$. This convention is what mathematicians use everywhere, and we will use it from here on.

02.The mod operator

For any integer $a$ and any positive integer $n$, the expression

$$a \bmod n$$

is the remainder you get when you divide $a$ by $n$. The remainder is the unique number in the range $\{0, 1, 2, \ldots, n - 1\}$ that you can subtract from $a$ to land on a multiple of $n$.

Some examples with $n = 5$:

• $7 \bmod 5 = 2$, because $7 = 1 \cdot 5 + 2$.
• $13 \bmod 5 = 3$, because $13 = 2 \cdot 5 + 3$.
• $20 \bmod 5 = 0$, because $20 = 4 \cdot 5 + 0$.
• $0 \bmod 5 = 0$, because $0 = 0 \cdot 5 + 0$.

For negative integers, the rule is the same: the remainder must be non-negative and strictly less than $n$. So you keep adding $n$ to the negative number until it falls into the right range.

• $-3 \bmod 5 = 2$, because $-3 + 5 = 2$, which is in $\{0, 1, 2, 3, 4\}$.
• $-7 \bmod 5 = 3$, because $-7 + 5 + 5 = 3$.
• $-10 \bmod 5 = 0$, because $-10 + 5 + 5 = 0$.

It is worth doing a few of these by hand. The convention "remainder is in $\{0, 1, \ldots, n-1\}$" is the only thing that distinguishes the mathematician's $\operatorname{mod}$ from what some programming languages do. Some languages return negative remainders for negative inputs. Whenever the math says $a \bmod n$, take it to mean the non-negative remainder.

03.The five-clock, in full

Let $n = 5$. Every integer falls into exactly one of five categories, depending on its remainder modulo $5$:

Every integer is somewhere in this table. No integer appears in more than one row. The five rows partition $\mathbb{Z}$ into five disjoint pieces, called residue classes modulo $5$. The names for the classes are simply $0, 1, 2, 3, 4$. Working "modulo $5$" means treating each whole row as a single thing, and only caring about which row a number belongs to.

This is the right picture: not five numbers, but five classes of numbers, each class containing infinitely many integers that all behave identically once we agree to ignore everything except the remainder.

04.Congruence: the symbol $\equiv$

Two integers $a$ and $b$ are congruent modulo $n$, written

$$a \equiv b \pmod{n},$$

if they have the same remainder when divided by $n$. Equivalently (and often more useful), $a \equiv b \pmod{n}$ exactly when $n$ divides their difference, $n \mid (a - b)$.

Examples with $n = 5$:

• $7 \equiv 2 \pmod 5$, because both $7$ and $2$ have remainder $2$, or equivalently because $5 \mid (7 - 2) = 5$.
• $13 \equiv 3 \pmod 5$, because $5 \mid (13 - 3) = 10$.
• $-3 \equiv 2 \pmod 5$, because $5 \mid (-3 - 2) = -5$.
• $7 \equiv -3 \pmod 5$, because $5 \mid (7 - (-3)) = 10$.

The relation $\equiv$ is the right way to write "is in the same residue class as". It behaves like equality in many ways: it is reflexive ($a \equiv a$), symmetric ($a \equiv b \Rightarrow b \equiv a$), and transitive ($a \equiv b$ and $b \equiv c$ imply $a \equiv c$). For that reason it is called an equivalence relation. The residue classes are exactly its equivalence classes.

The notation "$\bmod n$" sits at the end of the line because it modifies the entire equation. It is not part of either side. The line $a \equiv b \pmod n$ is read as "$a$ and $b$ are in the same residue class, where the residue is taken modulo $n$".

05.Reduction commutes with arithmetic

This is the most important fact in the whole note, and it is what makes modular arithmetic computationally cheap. The fact is:

If $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$, then

$$a + b \;\equiv\; a' + b' \pmod{n}, \qquad a \cdot b \;\equiv\; a' \cdot b' \pmod{n}.$$

Said in plain language: if you replace any number in an arithmetic expression by another number in the same residue class, the answer is in the same residue class as before. So when you only care about the answer modulo $n$, you can reduce your inputs modulo $n$ at any point, in any order, without changing the result.

A worked example with $n = 5$. Compute $(17 + 38) \cdot 23 \bmod 5$.

The slow, honest way: $17 + 38 = 55$, then $55 \cdot 23 = 1265$, then $1265 \bmod 5 = 0$.

The fast way, using the commute-with-reduction fact: reduce each input modulo $5$ first.

• $17 \bmod 5 = 2$,
• $38 \bmod 5 = 3$,
• $23 \bmod 5 = 3$.

So $(17 + 38) \cdot 23 \equiv (2 + 3) \cdot 3 \equiv 5 \cdot 3 \equiv 15 \equiv 0 \pmod 5$.

Same answer. Far smaller intermediate values. In hardware, this is the difference between a $32$-bit multiplier and a much narrower one. In ML-KEM, $q = 3329$ and the natural data path is $12$ bits wide, even though the polynomial coefficients in intermediate calculations could in principle grow much larger.

The proof of the commute-with-reduction property is short and clean. If $a \equiv a' \pmod n$, then $a = a' + k \cdot n$ for some integer $k$. Similarly, $b = b' + \ell \cdot n$ for some integer $\ell$. Then

$$a + b \;=\; (a' + b') + (k + \ell) \cdot n \;\equiv\; a' + b' \pmod n.$$

For multiplication,

$$a \cdot b \;=\; (a' + kn) \cdot (b' + \ell n) \;=\; a' b' + a' \ell n + b' k n + k \ell n^2,$$

and the last three terms are all multiples of $n$, so they vanish modulo $n$. So $a \cdot b \equiv a' \cdot b' \pmod n$. That is the entire argument.

Tables for $n = 5$

Because the residues mod $5$ are just $\{0, 1, 2, 3, 4\}$, we can write the entire addition and multiplication tables explicitly.

Addition modulo $5$:

Multiplication modulo $5$:

Read entries off the tables to convince yourself the answers match the rules. For instance, $3 \cdot 4 \bmod 5$: the ordinary product is $12$, and $12 \bmod 5 = 2$, which matches the entry in row $3$, column $4$. The bottom-right of the multiplication table is $4 \cdot 4 \bmod 5 = 16 \bmod 5 = 1$, again matching.

A small thing worth noticing in the multiplication table: every row past the zero row contains every non-zero residue exactly once. That is a property special to prime moduli, and it is the property that makes $\mathbb{Z}_5$ a field rather than only a ring.

07.What you carry forward

Three things from this note will appear constantly.

The mod operator $a \bmod n$ produces the remainder in the range $\{0, 1, \ldots, n - 1\}$. The congruence symbol $\equiv$ says "in the same residue class". And the commute-with-reduction property lets you reduce inputs modulo $n$ at any stage of an arithmetic computation without changing the final answer modulo $n$.

The next note packages all of this into a named structure: $\mathbb{Z}_n$, the ring of integers modulo $n$. The $n = 5$ tables you have just looked at are the addition and multiplication tables of $\mathbb{Z}_5$.