Modular Arithmetic

Arithmetic That Wraps Around

Modular arithmetic is the mathematics of things that cycle, like clocks and days of the week. We write:

$$a \equiv b \pmod{n}$$

This means $a$ is congruent to $b$ modulo $n$, meaning they leave the same remainder when divided by $n$, or equivalently, $n \mid (a - b)$. For example, $15 \equiv 3 \pmod{12}$.

Congruence is an equivalence relation partitioning integers into $n$ residue classes for remainders $0, 1, \dots, n-1$.

Because congruence is compatible with arithmetic, you can reduce as you go. To find $17 \cdot 17 \bmod 5$, use $17 \equiv 2$ to get $2 \cdot 2 = 4 \pmod 5$, avoiding 289.

The Division Exception

Division is the exception in modular arithmetic. You cannot freely divide congruences or cancel common factors as you do in standard algebra.

Common pitfall: Cancelling common factors blindly. For example, $6 \equiv 2 \pmod 4$, but cancelling 2 gives the false statement $3 \equiv 1 \pmod 4$.

Valid division mod $n$ relies entirely on multiplicative inverses, which only exist for numbers coprime to $n$.