Congruence (Modular)
Calculus & Advanced MathTwo 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 ≡ (three lines) means "congruent," and (mod n) tells you the modulus.
Example
$17 \equiv 2 \pmod{5}$ because $17$ and $2$ both have remainder $2$ when divided by $5$. Also, $17 - 2 = 15$, and $15$ is divisible by $5$.
Key Insight
Congruence groups numbers into families. All numbers congruent mod 12 "tell the same time on a clock." The family is called a congruence class.
Definition
$a \equiv b \pmod{n}$ if $n \mid (a - b)$. Congruence is an equivalence relation: reflexive, symmetric, and transitive. It is preserved under addition and multiplication: if $a \equiv b$ and $c \equiv d \pmod{n}$, then $a+c \equiv b+d$ and $ac \equiv bd \pmod{n}$.
Example
Solve $x \equiv 3 \pmod{7}$: solutions are $x = 3, 10, 17, -4, \ldots$ (all integers $\equiv 3 \bmod 7$). Solve $3x \equiv 6 \pmod{9}$: divide by $\gcd(3,9)=3$ if it divides $6$ (yes): $x \equiv 2 \pmod{3}$. Solutions: $2, 5, 8, \ldots$
Key Insight
Linear congruences $ax \equiv b \pmod{n}$ have solutions iff $\gcd(a,n) \mid b$. When it does, there are exactly $\gcd(a,n)$ solutions mod $n$.
Definition
Congruence modulo $n$ partitions $\mathbb{Z}$ into $n$ residue classes, forming the quotient ring $\mathbb{Z}/n\mathbb{Z}$. The Chinese Remainder Theorem: a system of congruences $x \equiv a_i \pmod{n_i}$ with pairwise coprime moduli has a unique solution mod $n_1 \times \ldots \times n_k$. Euler's theorem: $a^{\phi(n)} \equiv 1 \pmod{n}$ when $\gcd(a,n) = 1$, where $\phi$ is Euler's totient.
Example
Fermat's Little Theorem (special case): $2^6 \equiv 1 \pmod{7}$, so $2^{100} = 2^{6 \times 16+4} \equiv (2^6)^{16} \times 2^4 \equiv 1 \times 16 \equiv 2 \pmod{7}$. Modular exponentiation by repeated squaring makes this efficient.
Key Insight
Modular arithmetic modulo prime powers provides the p-adic integers Z_p, a completion of Z analogous to R as a completion of Q. p-adic analysis is a rich parallel to real analysis with applications in number theory.