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.
Work each congruence in this order. First check the gcd rule for solvability and count the solutions. When a and n are coprime, invert with Euclid run backwards to isolate x. Only combine moduli that are coprime, and state the answer modulo their product.
Check inverses by multiplying out. 4 times 7 is 28, and 28 is 3 times 9 plus 1, so 7 inverts 4 mod 9. Trying 2 gives 8 and trying 5 gives 20, neither leaving 1.
Run Euclid backwards to invert by hand. First divide repeatedly to get the gcd, then rewrite each remainder from the line above. When the gcd is 1 the coefficient of a is its inverse.
Check the gcd for solvability, invert with Euclid run backwards, and multiply coprime moduli into one.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
This opens up
16 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.