The point of congruences is that you can calculate with them almost like equations. Adding, subtracting and multiplying all respect congruence, so you may replace any number by anything congruent to it, usually something small, before you compute.
Theorem. If $a \equiv a'$ and $b \equiv b' \pmod{n}$, then $$a + b \equiv a' + b', \qquad a - b \equiv a' - b', \qquad ab \equiv a'b' \pmod{n}.$$ Applying the last rule again and again, $a^{k} \equiv (a')^{k}$ for every $k \ge 1$.
Why it works
Worked example: Reduce first
- $1234 = 9 \cdot 137 + 1$, so $1234 \equiv 1$. $5678 = 9 \cdot 630 + 8$, so $5678 \equiv 8$.
- $1234 \cdot 5678 \equiv 1 \cdot 8 = 8 \pmod{9}$.
- Check: $1234 \cdot 5678 = 7{,}006{,}652 = 9 \cdot 778{,}516 + 8$.
Answer: $8$.
Worked example: Negative residues are handy
- $2^{5} = 32 = 33 - 1 \equiv -1 \pmod{11}$.
- $2^{10} = (2^{5})^{2} \equiv (-1)^{2} = 1 \pmod{11}$.
Answer: $1$.
Worked example: Mixed signs
- Reduce each number: $-4 \equiv 5$, $17 \equiv 8$, $23 \equiv 5 \pmod{9}$.
- $5 \cdot 8 + 5 = 45 \equiv 0 \pmod{9}$.
- Check: $-68 + 23 = -45 = 9 \cdot (-5)$.
Answer: $0$.
What you may not do: cancel freely
Division is different. $2 \cdot 3 \equiv 2 \cdot 1 \pmod{4}$ (both sides are $\equiv 2$), yet $3 \not\equiv 1 \pmod{4}$. Cancelling the $2$ fails because $2$ shares a factor with the modulus $4$. The picture shows why: multiplying by $2$ mod $4$ sends both $1$ and $3$ to the same place, so you cannot tell afterward where you started.
The rule that does hold: if $ca \equiv cb \pmod{n}$ and $\gcd(c, n) = 1$, then $a \equiv b \pmod{n}$. (Here $n \mid c(a - b)$ with no common factor in $c$, so $n \mid (a - b)$.) In general you may only conclude $a \equiv b \pmod{n/\gcd(c, n)}$. Modular inverses make this precise.
| $\times$ | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
Common mistake
Key idea