Modulo arithmetic and congruence

The essentials

When an integer a is divided by a positive integer n, we can write a = qn + r with 0 ≤ r < n. The remainder r is written a mod n. For example, 47 = 9 × 5 + 2, so 47 mod 5 = 2. For a negative number, the remainder is still taken between 0 and n − 1: −17 = (−4) × 5 + 3, so −17 mod 5 = 3.

Two integers a and b are congruent modulo n, written a ≡ b (mod n), if n divides a − b; equivalently, a and b leave the same remainder when divided by n. For example, 23 ≡ 2 (mod 7) because 23 − 2 = 21 is a multiple of 7. Congruence modulo n is an equivalence relation, and it splits the integers into n classes.

Key points

• Modular addition: (a + b) mod n = [(a mod n) + (b mod n)] mod n.
• Modular multiplication: (a × b) mod n = [(a mod n) × (b mod n)] mod n.
• If a ≡ b (mod n), then aᵏ ≡ bᵏ (mod n) for every positive integer k.
• Clock and calendar problems use mod 12 (or 24) and mod 7. For example, 100 days after a Wednesday: 100 mod 7 = 2, so it is a Friday.
• To find a large power mod n, look for a small power that is ≡ 1. Since 2³ = 8 ≡ 1 (mod 7), 2⁵⁰ = (2³)¹⁶ × 2² ≡ 4 (mod 7).

Exam tips

• Reduce numbers mod n before multiplying; it keeps the arithmetic small.
• Check a congruence by subtracting and testing divisibility.

Common mistakes

• Giving a negative remainder, such as −2 for −17 mod 5.
• Counting the starting day as day 1 in calendar problems.