Modular Arithmetic
Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a modulus, like hours on a clock.
Formula
a \bmod n = \text{remainder when } a \text{ is divided by } n
Definition
Modular arithmetic is clock arithmetic: when you reach the modulus (like $12$ on a clock), you wrap back to zero, and "$17 \bmod 5$" asks what the remainder is when $17$ is divided by $5$. Two integers $a$ and $b$ are congruent ($a \equiv b \pmod{n}$) if $n$ divides $(a - b)$; the integers mod $n$ form a ring $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ under this remainder arithmetic, and if $n$ is prime, $\mathbb{Z}_n$ is a field (Galois field $GF(p)$). The Chinese Remainder Theorem states that if $\gcd(m,n) = 1$, then $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$, and Fermat's Little Theorem gives $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$ and $a$ not divisible by $p$.
Example
$17 \bmod 5 = 2$ (since $17 = 3 \times 5 + 2$); on a clock, $10$ hours after $7$ o'clock is $5$ o'clock ($17 \bmod 12 = 5$). Arithmetic works mod $n$ too: $7 + 8 \equiv 3 \pmod{12}$ and $5 \times 7 \equiv 11 \pmod{12}$; in $\mathbb{Z}_7$ (prime), every nonzero element has a multiplicative inverse. RSA encryption relies on this: choose primes $p, q$, set $n=pq$, encrypt with $c = m^e \bmod n$ and decrypt with $m = c^d \bmod n$ where $ed \equiv 1 \pmod{(p-1)(q-1)}$, with security resting on the difficulty of factoring $n$.
Key Insight
Modular arithmetic shows up everywhere: days of the week (mod 7), AM/PM cycles (mod 12/24), and checksums on barcodes and credit cards, turning an infinite set (integers) into a finite ring that enables number theory results to be applied to finite structures in cryptography and coding theory. The structure of $\mathbb{Z}_n^*$ (units modulo $n$) underlies not just RSA but the entire theory of elliptic curve cryptography and the AKS primality test, making modular arithmetic foundational to modern computer security.