← MATH 01352 · Theory of Numbers
MATH 01352 · Congruences
Linear congruences
Definition
ax ≡ b (mod n) solvable iff gcd(a,n) divides b. Then there are d=gcd distinct solutions mod n. Solve via extended EA finding inverse when d=1.
Read this
When d>1, divide equation and modulus by d carefully to get an invertible coefficient.
Systems of congruences lead to CRT when moduli cooperate.
Practice small moduli by testing — then upgrade to inverses.
Drill with flashcards
Flip through these until you can say the answer before revealing it.
Flashcards · 1 / 3
Click the card to flip
Try this
Attempt each problem first, then open the worked solution.
1.Solve 6x ≡ 3 (mod 9) and interpret multiple solutions.