Modular Arithmetic and Congruences

What is modular arithmetic?

Modular arithmetic is "clock arithmetic" — numbers wrap around after reaching a certain value (the modulus). When we write $a \mod n$, we mean the remainder when $a$ is divided by $n$.

Step-by-step: Compute $37 \mod 5$

Step 1 — Divide: $37 \div 5 = 7$ remainder $2$.

Step 2 — The remainder is the answer: $37 \mod 5 = 2$.

Alternatively: $37 = 5 \times 7 + 2$, so the remainder is $2$.

Interpretation: On a clock with 5 positions (0, 1, 2, 3, 4), counting to 37 lands you at position 2.

Step-by-step: Compute $123 \mod 7$

$123 \div 7 = 17$ remainder $4$. So $123 \mod 7 = 4$.

Check: $7 \times 17 = 119$, and $123 - 119 = 4$ ✓.

Congruence notation

We write $a \equiv b \pmod{n}$ (read "$a$ is congruent to $b$ mod $n$") when $a$ and $b$ have the same remainder when divided by $n$. Equivalently, $n$ divides $(a - b)$.

Examples: $37 \equiv 2 \pmod{5}$, $37 \equiv 12 \pmod{5}$, $37 \equiv -3 \pmod{5}$.

Arithmetic with mods

You can add, subtract, and multiply before or after taking the mod — the result is the same:

• $(a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n$
• $(a \times b) \mod n = [(a \mod n) \times (b \mod n)] \mod n$

Example: $37 \times 123 \mod 5 = (2 \times 4) \mod 5 = 8 \mod 5 = 3$.

Check: $37 \times 123 = 4551$. $4551 / 5 = 910$ remainder $1$... let me recalculate. $37 \times 123 = 4551$. $4551 = 5 \times 910 + 1$. So $4551 \mod 5 = 1$. And $(2 \times 4) \mod 5 = 8 \mod 5 = 3$. Wait — $123 \mod 5 = 3$ (not 4, that was mod 7). Let me redo: $123 \mod 5 = 3$ because $123 = 5 \times 24 + 3$. So $(2 \times 3) \mod 5 = 6 \mod 5 = 1$ ✓.

Real-world uses

• Clock time: Hours are mod 12 (or 24). 15:00 = 3:00 PM = $15 \mod 12 = 3$.
• Days of the week: mod 7. If today is Wednesday (day 3), what day is it in 100 days? $(3 + 100) \mod 7 = 103 \mod 7 = 5$ = Friday.
• ISBN check digits, credit card validation (Luhn algorithm), cryptography (RSA).

Try it in the visualization

Enter a number and modulus. The "number wheel" shows positions 0 to $n-1$, and an arrow points to $a \mod n$. Animate counting around the wheel to see the wrapping. Toggle arithmetic operations to see how mod distributes over addition and multiplication.