Arithmetic mod n
The power of congruence
is that you can compute with it. Remainders can be added, subtracted and multiplied just
like ordinary numbers — the answers always agree modulo n. This turns
the infinite world of integers into a small, closed system with only
n elements: \mathbb{Z}_n = \{0, 1, \dots, n-1\}.
The rules that make it work
If a \equiv a' and b \equiv b' \pmod n, then
- a + b \equiv a' + b' \pmod n,
- a - b \equiv a' - b' \pmod n,
- a \, b \equiv a' \, b' \pmod n.
The practical upshot: reduce early and often. You never have to carry big
numbers — replace anything by its remainder whenever you like. To find
17 \cdot 14 \bmod 5, don't compute 238;
reduce first:
17 \cdot 14 \equiv 2 \cdot 4 = 8 \equiv 3 \pmod 5.
Taming huge powers
This is how we tame quantities that would otherwise be unimaginable. What is the last digit of
7^{100}? "Last digit" means modulo 10. The
powers of 7 cycle:
7^1 \equiv 7,\quad 7^2 \equiv 9,\quad 7^3 \equiv 3,\quad 7^4 \equiv 1 \pmod{10},
then repeat every four. Since 100 = 4 \cdot 25, we land on
7^{100} \equiv (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}. The last digit is
1 — found without ever writing the
85-digit number.
A warning: division is different
Addition, subtraction and multiplication all transfer cleanly. Division does
not. From 2 \cdot 3 \equiv 2 \cdot 0 \pmod 6 you cannot cancel
the 2 to get 3 \equiv 0 — that's false. Why
cancellation sometimes works and sometimes fails, and how to "divide" properly, is the subject of
modular inverses.