Congruences – Modular Equations Explained
Two integers a and b are congruent modulo n, written a ≡ b (mod n), if n divides exactly into their difference (a − b) – equivalently, if a and b leave the same remainder when divided by n. Congruences turn modular arithmetic from a way of computing remainders into a full system of equations that can be solved just like ordinary algebra.
The “≡” notation was invented by Carl Friedrich Gauss in his 1801 Disquisitiones Arithmeticae, but the idea of solving systems of remainder conditions is far older. The classic puzzle “there are certain things whose number is unknown” – find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7 – appears in the Chinese text Sunzi Suanjing (3rd–5th century CE). The general method for solving such systems was worked out in full by the Song dynasty mathematician Qin Jiushao in his 1247 treatise, and is known today as the Chinese Remainder Theorem.
Congruence as an Equivalence Relation
Congruence modulo n behaves like equality in three key ways:
- Reflexive: a ≡ a (mod n) for every a.
- Symmetric: if a ≡ b (mod n), then b ≡ a (mod n).
- Transitive: if a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).
Linear Congruences
A linear congruence has the form ax ≡ b (mod n). It has a solution exactly when gcd(a, n) divides b, and when gcd(a, n) = 1 that solution is unique modulo n.
Since gcd(3, 5) = 1, a unique solution exists mod 5. Testing x = 0, 1, 2, 3, 4:
3×3 = 9, and 9 mod 5 = 4. ✓
So x ≡ 3 (mod 5).
The Chinese Remainder Theorem
The Chinese Remainder Theorem says that a system of congruences with pairwise coprime moduli always has a unique solution modulo the product of those moduli.
Numbers that are 2 more than a multiple of 3: 2, 5, 8, 11, …
Checking which of these is 3 more than a multiple of 5: 8 mod 5 = 3. ✓
Since 3 and 5 are coprime, the solution is unique modulo 3×5 = 15: x ≡ 8 (mod 15).
Key Takeaways
- a ≡ b (mod n) means n divides (a − b) exactly.
- Congruence is reflexive, symmetric, and transitive – it behaves like an equation.
- A linear congruence ax ≡ b (mod n) has a unique solution mod n when gcd(a, n) = 1.
- The Chinese Remainder Theorem solves systems of congruences with coprime moduli.