Chinese Remainder Theorem Solver
Solve systems of linear congruences with step-by-step solutions
Enter a system of congruences in the form: x ≡ a (mod m)
The Chinese Remainder Theorem (CRT) provides a way to solve systems of simultaneous linear congruences with pairwise coprime moduli. Given a system where x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), the CRT guarantees a unique solution modulo M = m₁ × m₂ × ... × mₙ.
The Algorithm:
- Calculate M = m₁ × m₂ × ... × mₙ (product of all moduli)
- For each i, compute Mᵢ = M / mᵢ
- Find yᵢ such that Mᵢ × yᵢ ≡ 1 (mod mᵢ) using the Extended Euclidean Algorithm
- Calculate x = Σ(aᵢ × Mᵢ × yᵢ)
- The solution is x mod M
Requirements: All moduli must be pairwise coprime (their GCD must be 1). If this condition is not met, the system may have no solution or infinitely many solutions.
Applications: The CRT is fundamental in cryptography (RSA algorithm optimization), computer science (parallel computing, hash functions), and number theory. It allows breaking down large modular arithmetic problems into smaller, more manageable pieces.
Historical Note: The theorem is named after its appearance in the 3rd-century Chinese mathematical text "Sunzi Suanjing" (The Mathematical Classic of Sun Zi), where it was used to solve problems about counting soldiers.
What is the Chinese Remainder Theorem used for?
The Chinese Remainder Theorem (CRT) is used to solve systems of simultaneous congruences. In modern applications, it's essential in RSA cryptography for faster decryption, in computer science for parallel processing, and in calendar calculations for determining dates that satisfy multiple cyclic conditions.
Why must the moduli be pairwise coprime?
The moduli must be pairwise coprime (GCD of any pair equals 1) to guarantee a unique solution modulo the product of all moduli. If moduli share common factors, the system may have no solution or infinitely many solutions, depending on whether the remainders are consistent with those factors.
How does CRT speed up RSA decryption?
In RSA, CRT allows decryption using two smaller modular exponentiations (mod p and mod q separately) instead of one large exponentiation (mod n=pq). The results are then combined using CRT. This is roughly 4 times faster than direct computation because exponentiation time grows with the cube of the modulus size.
What is the historical origin of the Chinese Remainder Theorem?
The theorem first appeared in the 3rd century Chinese text 'Sunzi Suanjing' as a problem about counting soldiers: find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. The answer is 23, and the general method became known as the Chinese Remainder Theorem.