Modular Arithmetic

Arithmetic That Wraps Around

Modular arithmetic is arithmetic with remainders — the mathematics of things that cycle, like clocks, days of the week, and digital registers. We say $a$ is congruent to $b$ modulo $n$, written $$a \equiv b \pmod{n},$$ when $a$ and $b$ leave the same remainder on division by $n$ — equivalently, when $n \mid (a - b)$. On a 12-hour clock, $15 \equiv 3 \pmod{12}$: 15:00 shows as 3 o'clock.

Congruence modulo $n$ is an equivalence relation (Unit 1): it partitions the integers into $n$ residue classes, one per possible remainder $0, 1, \dots, n-1$. All integers in a class are interchangeable for mod-$n$ purposes.

The power of the notation is that congruence is compatible with arithmetic. If $a \equiv b$ and $c \equiv d \pmod n$, then: $$a + c \equiv b + d, \qquad a \cdot c \equiv b \cdot d \pmod{n}.$$ You may add, subtract, and multiply congruences just like equations — which means you can reduce as you go, replacing any number by its remainder at any step. To find $17 \cdot 17 \bmod 5$, note $17 \equiv 2$, so $17 \cdot 17 \equiv 2 \cdot 2 = 4 \pmod 5$ — no need to compute 289. This is what makes modular arithmetic computationally tame even for huge numbers.

Division is the exception. You cannot freely divide congruences: $a \equiv b \pmod n$ does not always let you cancel a common factor. Division mod $n$ works only via multiplicative inverses, which exist only when the number is coprime to $n$ — the reason coprimality (Lesson 4) matters here.

Common pitfall: assuming you can divide or cancel in congruences as freely as you add and multiply. Addition, subtraction, and multiplication respect congruence, but cancellation does not in general: $6 \equiv 2 \pmod 4$ but you cannot cancel the common factor 2 to get $3 \equiv 1 \pmod 4$ (which is false). Division mod $n$ requires a multiplicative inverse, available only for numbers coprime to $n$.