Helpful context:

A clock is the simplest example of modular arithmetic: after 12 comes 1, not 13. But calling this “clock arithmetic” undersells the structure. Modular arithmetic is a complete algebraic system with addition, multiplication, inverses, and deep theorems. The integers modulo $n$ form a ring, and when $n$ is prime, that ring becomes a field where every nonzero element is invertible. This field structure is what makes cryptography work.

The passage from the ordinary integers to $\mathbb{Z}/n\mathbb{Z}$ is a process of identification: we declare two integers equivalent if their difference is divisible by $n$. That identification preserves addition and multiplication - these operations on residue classes are well-defined - but it does something surprising: it can create finite fields. The rationals form an infinite field. $\mathbb{Z}/7\mathbb{Z}$ is a finite field with exactly 7 elements. Both satisfy the same field axioms. This kind of finite field is the arithmetic backbone of RSA, Diffie-Hellman, and elliptic curve cryptography.

Congruence

Definition. For a positive integer $n$, integers $a$ and $b$ are congruent modulo $n$, written $a \equiv b \pmod{n}$, if $n \mid (a - b)$.

Examples. $17 \equiv 5 \pmod{12}$ because $12 \mid 12$. $-1 \equiv n - 1 \pmod{n}$ because $n \mid (-1 - (n-1)) = -n$. $100 \equiv 1 \pmod{99}$.

Congruence modulo $n$ is an equivalence relation:

  • Reflexive: $a \equiv a \pmod{n}$ since $n \mid 0$.
  • Symmetric: if $n \mid (a-b)$, then $n \mid (b-a)$.
  • Transitive: if $n \mid (a-b)$ and $n \mid (b-c)$, then $n \mid (a-c)$.

The equivalence classes are called residue classes. The residue class of $a$ is $[a] = \{a + kn : k \in \mathbb{Z}\} = \{\ldots, a-n, a, a+n, a+2n, \ldots\}$. There are exactly $n$ residue classes: $[0], [1], \ldots, [n-1]$, and they partition $\mathbb{Z}$.

The set of residue classes is denoted $\mathbb{Z}/n\mathbb{Z}$ (read: “the integers mod $n$"). We usually write its elements as $0, 1, \ldots, n-1$, with the understanding that these represent the full equivalence classes.

Arithmetic in $\mathbb{Z}/n\mathbb{Z}$

Theorem. Addition and multiplication on residue classes are well-defined:

$$[a] + [b] = [a + b], \quad [a] \cdot [b] = [ab].$$

Proof (well-definedness). Suppose $a \equiv a' \pmod{n}$ and $b \equiv b' \pmod{n}$. Then $n \mid (a - a')$ and $n \mid (b - b')$. We need $[a + b] = [a' + b']$, i.e., $n \mid (a + b - a' - b')$. Indeed, $a + b - a' - b' = (a - a') + (b - b')$, which is divisible by $n$. Similarly, $ab - a’b' = a(b - b') + b'(a - a')$ is divisible by $n$. $\square$

Reduction at each step. The key computational rule: $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$, and similarly for multiplication. This means we can reduce intermediate results at any point in a computation. For example, $99 \cdot 100 \bmod 7$: we have $99 \equiv 1$ and $100 \equiv 2 \pmod{7}$, so $99 \cdot 100 \equiv 1 \cdot 2 = 2 \pmod 7$. Without reduction, $99 \cdot 100 = 9900$, and $9900 \bmod 7 = 2$. Same answer, but the reduction-first path avoids working with large numbers.

$\mathbb{Z}/n\mathbb{Z}$ is a ring. Under these operations, $\mathbb{Z}/n\mathbb{Z}$ satisfies all ring axioms: it is an abelian group under addition (with identity $0$ and additive inverse $-a \equiv n - a$), multiplication is associative, and multiplication distributes over addition.

Multiplicative Inverses

An element $a \in \mathbb{Z}/n\mathbb{Z}$ has a multiplicative inverse (i.e., an element $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod{n}$) if and only if $\gcd(a, n) = 1$.

Proof. If $\gcd(a, n) = 1$, Bezout’s identity gives integers $x, y$ with $ax + ny = 1$. Reducing mod $n$: $ax \equiv 1 \pmod{n}$, so $x = a^{-1}$.

Conversely, if $ax \equiv 1 \pmod{n}$, then $ax - ny = 1$ for some $y$, so $\gcd(a, n) \mid 1$, giving $\gcd(a, n) = 1$. $\square$

Computing inverses. Use the extended Euclidean algorithm. To find $7^{-1} \pmod{31}$: apply extended Euclidean to $\gcd(7, 31)$:

$$31 = 4 \cdot 7 + 3$$ $$7 = 2 \cdot 3 + 1$$

Back-substitute: $1 = 7 - 2 \cdot 3 = 7 - 2(31 - 4 \cdot 7) = 9 \cdot 7 - 2 \cdot 31$.

So $7^{-1} \equiv 9 \pmod{31}$. Check: $7 \cdot 9 = 63 = 2 \cdot 31 + 1 \equiv 1$. $\square$

$\mathbb{Z}/n\mathbb{Z}$ as a Ring and Field

When $n$ is composite. $\mathbb{Z}/n\mathbb{Z}$ has zero divisors: nonzero elements whose product is zero. For example, in $\mathbb{Z}/6\mathbb{Z}$: $2 \cdot 3 = 6 \equiv 0$, yet $2 \neq 0$ and $3 \neq 0$. An element $a$ with $\gcd(a, n) > 1$ is a zero divisor - it cannot be inverted.

When $n = p$ is prime. Every nonzero element $a \in \{1, 2, \ldots, p-1\}$ satisfies $\gcd(a, p) = 1$ (since $p$ is prime), so every nonzero element has a multiplicative inverse. This makes $\mathbb{Z}/p\mathbb{Z}$ a field, usually written $\mathbb{F}_p$ or $\text{GF}(p)$.

In a field, addition, subtraction, multiplication, and division by nonzero elements are all possible. This is the complete arithmetic we expect from $\mathbb{Q}$ or $\mathbb{R}$, but now in a finite set with $p$ elements.

Modulus $n$ Structure of $\mathbb{Z}/n\mathbb{Z}$ Example
$n$ prime Field: every nonzero element invertible $\mathbb{Z}/7\mathbb{Z}$ - inverses $1^{-1}=1, 2^{-1}=4, 3^{-1}=5, \ldots$
$n = p^k$ Ring: units are elements coprime to $n$ $\mathbb{Z}/4\mathbb{Z}$ - only $1, 3$ are units; $2$ is a zero divisor
$n = pq$, $p \neq q$ Ring: units coprime to $n$; structure via CRT $\mathbb{Z}/15\mathbb{Z}$ - units are elements coprime to 15

Fast Modular Exponentiation

Computing $a^k \bmod n$ by repeated multiplication takes $O(k)$ multiplications, which is infeasible for cryptographic sizes (e.g., $k \approx 2^{2048}$). The square-and-multiply algorithm does it in $O(\log k)$ multiplications.

Algorithm. Write $k$ in binary: $k = \sum_{i=0}^{m} b_i 2^i$. Then

$$a^k = a^{b_m 2^m + \cdots + b_1 2 + b_0} = \prod_{i : b_i = 1} a^{2^i}.$$

The values $a, a^2, a^4, a^8, \ldots, a^{2^m}$ can be computed by repeated squaring (each $a^{2^{i+1}} = (a^{2^i})^2$). Then multiply together those where $b_i = 1$.

Example. Compute $3^{13} \bmod 7$. Write $13 = 1101_2$.

$$3^1 \equiv 3$$ $$3^2 \equiv 2$$ $$3^4 \equiv 4$$ $$3^8 \equiv 2$$ $$3^{13} = 3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod{7}.$$

Cost. The number of squarings is $\lfloor \log_2 k \rfloor$, and the number of multiplications is at most $\lfloor \log_2 k \rfloor$ more. Total: $O(\log k)$ multiplications mod $n$. For $k \approx 2^{2048}$, this is 2048 multiplications - entirely feasible.

The Chinese Remainder Theorem

Theorem (CRT). Let $n = p_1 p_2 \cdots p_k$ where $p_1, \ldots, p_k$ are pairwise coprime. Then

$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1\mathbb{Z} \times \mathbb{Z}/p_2\mathbb{Z} \times \cdots \times \mathbb{Z}/p_k\mathbb{Z}.$$

The isomorphism is the map $a \bmod n \mapsto (a \bmod p_1, a \bmod p_2, \ldots, a \bmod p_k)$.

Consequence. Any system of congruences $x \equiv a_i \pmod{p_i}$ for $i = 1, \ldots, k$ has a unique solution modulo $n = p_1 \cdots p_k$. The solution can be constructed explicitly.

Construction. Let $N_i = n / p_i$. Since $\gcd(N_i, p_i) = 1$, there exists $M_i = N_i^{-1} \bmod p_i$. The solution is

$$x \equiv \sum_{i=1}^k a_i N_i M_i \pmod{n}.$$

Example. Solve $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$.

Here $n = 15$, $N_1 = 5$, $N_2 = 3$. Find $M_1 = 5^{-1} \bmod 3 = 2$ (since $5 \cdot 2 = 10 \equiv 1 \pmod 3$) and $M_2 = 3^{-1} \bmod 5 = 2$ (since $3 \cdot 2 = 6 \equiv 1 \pmod 5$).

$$x \equiv 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 = 20 + 18 = 38 \equiv 8 \pmod{15}.$$

Check: $8 \equiv 2 \pmod 3$ and $8 \equiv 3 \pmod 5$. $\square$

Application to RSA

RSA encryption is modular arithmetic. The public key is $(n, e)$ where $n = pq$ is a product of two large primes and $e$ is chosen with $\gcd(e, \varphi(n)) = 1$. Encryption of a message $m$:

$$c = m^e \bmod n.$$

Decryption uses the private key $d = e^{-1} \bmod \varphi(n)$:

$$c^d = m^{ed} \bmod n.$$

Why does $c^d \equiv m \pmod{n}$? Because $ed \equiv 1 \pmod{\varphi(n)}$, so $ed = 1 + k\varphi(n)$ for some integer $k$, and by Euler’s theorem $m^{\varphi(n)} \equiv 1 \pmod{n}$ (when $\gcd(m, n) = 1$), giving

$$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod{n}.$$

Every step here is modular arithmetic: the fast exponentiation computes $m^e \bmod n$ and $c^d \bmod n$; the correctness proof uses congruences and Euler’s theorem. The structure of $\mathbb{Z}/n\mathbb{Z}$ - specifically the ring homomorphism property that lets us reduce at each step - is what makes this all work efficiently.

Summary

Concept Definition Key property
Congruence $a \equiv b \pmod n$ $n \mid (a - b)$ Equivalence relation; partitions $\mathbb{Z}$ into $n$ classes
$\mathbb{Z}/n\mathbb{Z}$ Set of residue classes mod $n$ Ring under $+$ and $\cdot$
Inverse of $a$ mod $n$ $ax \equiv 1 \pmod n$ Exists iff $\gcd(a, n) = 1$; computed by extended GCD
$\mathbb{Z}/p\mathbb{Z}$ for prime $p$ All nonzero elements invertible Field; no zero divisors
Zero divisors $ab \equiv 0$ with $a, b \not\equiv 0$ Occur when $n$ is composite
Square-and-multiply $a^k \bmod n$ in $O(\log k)$ steps Essential for RSA/DH
Chinese Remainder Theorem $\mathbb{Z}/n\mathbb{Z} \cong \prod \mathbb{Z}/p_i\mathbb{Z}$ Unique solution to coprime systems

Read next: