Modular arithmetic and residue classes

For an integer $a$ and a positive integer $n$, $a \bmod n$ is the remainder when $a$ is divided by $n$: the same division algorithm from the previous page, $a = qn + r$ with $0 \le r < n$ and $q = \lfloor a/n \rfloor$, now extended to integers $a$ that can be negative. The remainder is always non-negative, regardless of the sign of $a$.

For $a = 11$, $n = 7$: $q = \lfloor 11/7 \rfloor = 1$, so $11 \bmod 7 = 11 - 7 = 4$.

For $a = -11$, $n = 7$: $q = \lfloor -11/7 \rfloor = \lfloor -1.571\ldots \rfloor = -2$, so $-11 \bmod 7 = -11 - (-2 \times 7) = -11 + 14 = 3$.

Two integers $a$ and $b$ are congruent modulo $n$ if they leave the same remainder: $(a \bmod n) = (b \bmod n)$. Written $a \equiv b \pmod{n}$, read ”$a$ is congruent to $b$ modulo $n$.” Congruence does not require $a$ and $b$ to be close, or equal, or even both positive — only that dividing each by $n$ leaves the same remainder. One direct consequence: $a \equiv 0 \pmod{n}$ exactly when $n \mid a$.

$73 \equiv 4 \pmod{23}$, because $73 = 3 \times 23 + 4$ and $4 < 23$. $21 \equiv 31 \pmod{10}$, because $21 \bmod 10 = 1$ and $31 \bmod 10 = 1$ — the same remainder, even though $21$ and $31$ are ten apart.

Ordinary arithmetic properties carry over into modular arithmetic. For any integers $a$, $b$ and modulus $n$:

$[(a \bmod n) + (b \bmod n)] \bmod n = (a + b) \bmod n$ $[(a \bmod n) - (b \bmod n)] \bmod n = (a - b) \bmod n$ $[(a \bmod n) \times (b \bmod n)] \bmod n = (a \times b) \bmod n$

In plain terms: reducing first and then combining gives the same answer as combining first and then reducing. This is what lets cryptographic implementations keep every intermediate value small — reduce mod $n$ at every step instead of computing the full-size result and reducing once at the end.

Define $\mathbb{Z}_n$ as the set of non-negative integers less than $n$: $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$. Every integer, not only the ones in this range, falls into one of these $n$ residue classes. The class $[r]$ is the set of every integer congruent to $r$ modulo $n$: $[r] = \{a : a \text{ is an integer}, \ a \equiv r \pmod{n}\}.$ $\mathbb{Z}_n$ lists one representative from each class — specifically the smallest non-negative one, which is why $a \bmod n$ always lands inside $\mathbb{Z}_n$. Arithmetic on $\mathbb{Z}_n$ is exactly the modular arithmetic above: add, subtract or multiply the representatives and reduce mod $n$ to land back inside the set.

Exponentiation is repeated multiplication, so the same reduce-as-you-go idea applies: compute $a^k \bmod n$ by building up the power through smaller modular multiplications instead of computing the (potentially huge) full power first. This one calculation is the basis of Diffie-Hellman key exchange in Module 6.