Congruence (Modular)
Two integers are congruent modulo n if they have the same remainder when divided by n, written a ≡ b (mod n).
Formula
a \equiv b \pmod{n} \text{ iff } n \mid (a - b)
Definition
Two numbers are congruent modulo $n$ if they have the same remainder when divided by $n$; the symbol $\equiv$ means "congruent," and $\pmod{n}$ tells you the modulus. Formally, $a \equiv b \pmod{n}$ if $n \mid (a - b)$; congruence is an equivalence relation (reflexive, symmetric, transitive) that is preserved under addition and multiplication, so $a \equiv b$ and $c \equiv d \pmod{n}$ implies $a+c \equiv b+d$ and $ac \equiv bd \pmod{n}$. Congruence modulo $n$ partitions $\mathbb{Z}$ into $n$ residue classes, forming the quotient ring $\mathbb{Z}/n\mathbb{Z}$; the Chinese Remainder Theorem gives a unique solution mod $n_1 \times \ldots \times n_k$ to a system of congruences with pairwise coprime moduli, and Euler's theorem states $a^{\phi(n)} \equiv 1 \pmod{n}$ when $\gcd(a,n) = 1$.
Example
$17 \equiv 2 \pmod{5}$ because both have remainder $2$ when divided by $5$, and indeed $17 - 2 = 15$ is divisible by $5$. Solving $3x \equiv 6 \pmod{9}$: dividing by $\gcd(3,9)=3$ (which divides $6$) gives $x \equiv 2 \pmod{3}$, with solutions $2, 5, 8, \ldots$; linear congruences $ax \equiv b \pmod{n}$ have solutions iff $\gcd(a,n) \mid b$. Fermat's Little Theorem lets you compute $2^{100} \bmod 7$ efficiently: since $2^6 \equiv 1 \pmod 7$, $2^{100} = (2^6)^{16} \times 2^4 \equiv 16 \equiv 2 \pmod{7}$, using modular exponentiation by repeated squaring.
Key Insight
Congruence groups numbers into families: all numbers congruent mod 12 "tell the same time on a clock," and when it does have solutions, a linear congruence has exactly $\gcd(a,n)$ solutions mod $n$. Modular arithmetic modulo prime powers provides the p-adic integers $\mathbb{Z}_p$, a completion of $\mathbb{Z}$ analogous to $\mathbb{R}$ as a completion of $\mathbb{Q}$, with p-adic analysis a rich parallel to real analysis in number theory.