Linear Congruences and the Chinese Remainder Theorem
Solve a single linear congruence, say exactly when it is solvable, and combine congruences with coprime moduli into one.
What a learner can do afterwards
- Decide when a linear congruence has a solution and count the solutions modulo n
- Find a modular inverse using the extended Euclidean algorithm
- Solve a system of congruences with coprime moduli and state the modulus of the combined answer
1 · Read
A linear congruence a x is b mod n asks which remainder family x must come from. It has a solution exactly when the gcd of a and n divides b. So 2x is 3 mod 6 is impossible, since gcd 2 skips 3. When the gcd does divide b, there are exactly that many solutions mod n: 6x is 9 mod 15 has 3, since gcd(6, 15) is 3 and 3 divides 9.
An inverse of a mod n is a number u with a times u is 1 mod n, and it exists exactly when a and n are coprime. The inverse of 3 mod 7 is 5, since 15 leaves remainder 1. The inverse of 4 mod 9 is 7, since 28 leaves remainder 1. Euclid finds the gcd fast by repeated division, and running it backwards writes the gcd as a combination of a and n, which is exactly how you compute an inverse by hand.
The Chinese remainder theorem combines congruences with coprime moduli into one. Mod 4 and mod 9 merge into mod 36, and mod 5 with mod 7 merges into mod 35. The smallest x that is 1 mod 4 and 2 mod 5 is 17: candidates 1, 5, 9, 13 reduce mod 5 to 1, 0, 4, 3, and 17 is the first to give 2. The proof builds its solution out of one inverse per modulus.
Work each congruence in this order. First check the gcd rule for solvability and count the solutions. Then invert with Euclid run backwards to isolate x. Only combine moduli that are coprime, and state the answer modulo their product.
Check the gcd for solvability, invert with Euclid run backwards, and multiply coprime moduli into one.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.