← MATH 01352 · Theory of Numbers
MATH 01352 · Congruences
Chinese Remainder Theorem idea
Definition
If m,n are coprime, the system x≡a (mod m), x≡b (mod n) has a unique solution mod mn. More generally for pairwise coprime moduli.
Read this
Constructive proof: x = a n n⁻¹ + b m (m⁻¹) style combination (for two equations).
ℤ_{mn} ≅ ℤₘ × ℤₙ as rings when gcd(m,n)=1.
Used constantly in crypto and calendar/scheduling word problems.
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 x≡2 (mod 3), x≡3 (mod 5).