CRT Problem Examples

Number Theory · Axiom Academy

Solving a classic Chinese Remainder Theorem problem step-by-step Excellent work! You've successfully solved a Chinese Remainder Theorem problem. Here's what we learned: System of Congruences: The CRT allows us to solve systems where we know remainders for different moduli, as long as the moduli are pairwise coprime. Product of Moduli: We calculate M = m₁ × m₂ × m₃ and then M_i = M/m_i for each modulus. These M_i values are key to the construction. Modular Inverses: Finding y_i such that M_i · y_i ≡ 1 (mod m_i) is crucial. The Extended Euclidean Algorithm helps us find these inverses. CRT Formula: The solution is x = Σ(a_i · M_i · y_i) mod M, which combines all the constraints into a single answer. Verification: Always check your answer by testing it against each original congruence to ensure correctness. The Chinese Remainder Theorem is powerful for solving systems of congruences and appears in cryptography, computer science, and many areas of mathematics. Practice with different moduli to master this technique!

This is the written version of the interactive lesson above. See the full Number Theory course.