Modular arithmetic and residue classes

Mod wraps every integer into a fixed range, and the remainder is never negative

Every cryptographic scheme in this unit computes inside a fixed-size set of numbers. RSA ciphertexts stay below the modulus $n$, and Diffie-Hellman keys stay below a prime $p$. Without a boundary, encrypting even a short message would produce numbers thousands of digits long. The boundary is enforced by one operation, mod: values wrap around like a clock instead of growing forever.

For an integer $a$ and a positive integer $n$, $a \bmod n$ is the remainder when $a$ is divided by $n$. It is the 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, whatever 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$.

Pitfall

$q = \lfloor a/n \rfloor$ rounds toward negative infinity, not toward zero. For $a = -11$, truncating toward zero gives $q = -1$ and a remainder of $-4$, which is negative and outside the required range $0 \le r < n$. The two rounding rules agree for non-negative $a$ and disagree the moment $a$ goes negative. Every mod result on this site, and every mod result the exam expects, is non-negative.

Recall

Why does -11 mod 7 give 3, and not -4?

Because the definition requires $0 \le r < n$. $q$ must be $\lfloor -11/7 \rfloor = -2$, the floor, not $-1$, the truncation toward zero. $-11 - (-2 \times 7) = 3$, which satisfies the range; $-11 - (-1 \times 7) = -4$ does not.

Congruent numbers share a remainder, so you can reduce before you combine

Two integers $a$ and $b$ are congruent modulo $n$ if they leave the same remainder: $(a \bmod n) = (b \bmod n)$. This is written $a \equiv b \pmod{n}$. Congruence does not require $a$ and $b$ to be close, equal, or both positive, only that dividing each by $n$ leaves the same remainder. One 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. Checking congruence never requires comparing $a$ and $b$ directly, only their two remainders.

Formula

Congruence modulo n

$$a \equiv b \pmod{n} \iff (a \bmod n) = (b \bmod n)$$

$a, b$

any integers

$n$

the modulus

a ≡ 0 (mod n) if and only if n divides a.

Ordinary arithmetic properties carry over. 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$

Reducing first and then combining gives the same answer as combining first and then reducing. This is what lets 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.

Try it — worked example

With a = 11, b = 9, n = 8, check that modular addition, subtraction and multiplication give the same result whether you reduce first or last.

Show answer and steps

AnswerAll three properties hold for a = 11, b = 9, n = 8

The lecture verifies each property with the same pair, $a = 11$, $b = 9$, $n = 8$. First, $11 \bmod 8 = 3$ and $9 \bmod 8 = 1$.

1. Addition. LHS: $[(11 \bmod 8) + (9 \bmod 8)] \bmod 8 = [3 + 1] \bmod 8 = 4 \bmod 8 = 4$. RHS: $(11 + 9) \bmod 8 = 20 \bmod 8 = 4$. LHS = RHS.
2. Subtraction. LHS: $[(11 \bmod 8) - (9 \bmod 8)] \bmod 8 = [3 - 1] \bmod 8 = 2$. RHS: $(11 - 9) \bmod 8 = 2 \bmod 8 = 2$. LHS = RHS.
3. Multiplication. LHS: $[(11 \bmod 8) \times (9 \bmod 8)] \bmod 8 = [3 \times 1] \bmod 8 = 3$. RHS: $(11 \times 9) \bmod 8 = 99 \bmod 8 = 3$, since $8 \times 12 = 96$ and $99 - 96 = 3$. LHS = RHS.

Z_n holds one representative per residue class, and powers are built by reducing as you go

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 the smallest non-negative member of each class, which is why $a \bmod n$ always lands inside $\mathbb{Z}_n$. Arithmetic on $\mathbb{Z}_n$ is 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 the power through smaller modular multiplications instead of computing the full power first. This one calculation is the basis of Diffie-Hellman key exchange in Module 6.

Try it — worked example

Compute 11^7 mod 13 without calculating 11^7 in full.

Show answer and steps

Answer11^7 mod 13 = 2

1. $11^2 = 121$. $121 \bmod 13 = 4$, since $13 \times 9 = 117$ and $121 - 117 = 4$.
2. $11^4 = (11^2)^2 \equiv 4^2 = 16 \pmod{13}$. $16 \bmod 13 = 3$.
3. Write $11^7$ as $11^1 \times 11^2 \times 11^4$, since $1 + 2 + 4 = 7$.
4. $11^7 \equiv 11 \times 4 \times 3 \pmod{13}$. $11 \times 4 = 44$, and $44 \times 3 = 132$.
5. $132 \bmod 13$: $13 \times 10 = 130$, and $132 - 130 = 2$. So $11^7 \equiv 2 \pmod{13}$.

Pitfall

The Week 4 abstract-algebra supplement uses $\mathbb{Z}_8$ to show that $2$ has no multiplicative inverse modulo $8$, and its printed working states $2 \cdot 2 \bmod 8 = 0$. That line is wrong: $2 \times 2 = 4$, and $4 \bmod 8 = 4$, not $0$. The corrected table of $2 \cdot k \bmod 8$ for $k = 0, \ldots, 7$ is $0, 2, 4, 6, 0, 2, 4, 6$. Every result is even, so none is $1$, and the conclusion (no inverse exists) still holds. 04-06 returns to this table as the counter-example for why $\mathbb{Z}_8$ is a commutative ring but not a field.