Congruences

Computing modulo n: compatibility with sums, products and powers, modular inverse, divisibility rules, casting out nines and the Luhn check digit.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

a ≡ b (mod n): what is it?
Show the answer
The integers a and b leave the same remainder when divided by n; equivalently, n divides a − b.
38 ≡ 14 (mod 12), since 38 − 14 = 24 and 38 = 12 × 3 + 2, 14 = 12 × 1 + 2. Integers congruent modulo n behave identically for sums and products.
What does this program print?

```python
print((123456789 * 987654321) % 10)
`
- 9
- 1
- 0
- 8
Show the answer
9
Only the last digit of each factor matters modulo 10: 9 × 1 = 9. There is no need to compute the 18-digit product.
If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ … and a × c ≡ … (mod n).
Show the answer
If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d and a × c ≡ b × d (mod n).
So you can reduce modulo n at every step of a calculation, without handling a large number: this is what makes check digits, hashing and cycles tractable.
Residue class modulo n: what is it?
Show the answer
The set of integers that leave the same remainder r when divided by n; there are exactly n classes, represented by 0, 1, …, n − 1.
Modulo 5, the class of 2 contains …, −8, −3, 2, 7, 12, …: computing modulo n amounts to computing on these n classes.