Modular Arithmetic
Calculus & Advanced MathModular 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. "$17 \bmod 5$" asks: what is the remainder when $17$ is divided by $5$?
Example
$17 \bmod 5 = 2$ (since $17 = 3 \times 5 + 2$). Clock example: $10$ hours after $7$ o'clock is $5$ o'clock ($17 \bmod 12 = 5$).
Key Insight
Modular arithmetic shows up everywhere: days of the week (mod 7), AM/PM cycles (mod 12/24), checksums on barcodes and credit cards.
Definition
In modular arithmetic with modulus $n$, 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\}$ with addition and multiplication defined by remainder. If $n$ is prime, $\mathbb{Z}_n$ is a field.
Example
$7 + 8 \equiv 3 \pmod{12}$: $15 \bmod 12 = 3$. Multiplication: $5 \times 7 \equiv 11 \pmod{12}$: $35 \bmod 12 = 11$. In $\mathbb{Z}_7$ (prime), every nonzero element has a multiplicative inverse.
Key Insight
Modular arithmetic turns an infinite set (integers) into a finite ring, enabling number theory results to be applied to finite structures in cryptography and coding theory.
Definition
$\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$ is the quotient ring of integers modulo $n$. When $n = p$ is prime, $\mathbb{Z}_p$ is a field (Galois field $GF(p)$). The Chinese Remainder Theorem: if $\gcd(m,n) = 1$, then $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$. Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$ and $a$ not divisible by $p$.
Example
RSA encryption: choose primes $p, q$. Public key uses $n=pq$ and $e$. Encryption: $c = m^e \bmod n$. Decryption: $m = c^d \bmod n$, where $ed \equiv 1 \pmod{(p-1)(q-1)}$. Security relies on the difficulty of factoring $n$.
Key Insight
The structure of 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.