Solve two modular congruences and combine them into one result
x = a mod m
mod m
x = b mod n
mod n
Result
Answer
Step-by-Step Derivation
Chinese Remainder Theorem Formula
x ≡ a (mod m)
x ≡ b (mod n)
Solution exists if a - b is divisible by gcd(m, n)
The Chinese remainder theorem combines separate remainder conditions into a single congruence. When the moduli are coprime, the solution is unique modulo mn; with shared factors, compatibility must be checked first.
⚠This page solves two congruences at a time. Moduli must be greater than 1, and non-coprime moduli require compatible remainders.
How the Chinese Remainder Theorem Works
The Chinese remainder theorem finds numbers that satisfy multiple remainder rules at once. It is especially useful when a large modular problem can be split into smaller modular pieces.
Congruence System
The input describes two remainder rules for the same unknown x.
Compatibility
For non-coprime moduli, the remainders must agree modulo the gcd.
Combined Modulus
The final answer repeats every lcm(m,n).
Verification
The computed x is checked against both original congruences.
Example: For x ≡ 2 mod 3 and x ≡ 3 mod 5, the smallest solution is x = 8. All solutions are x ≡ 8 mod 15.
Applications of Chinese Remainder Theorem
CRT ProblemsModular ArithmeticCryptographyContest MathRemainder Systems
Frequently Asked Questions
What is a Chinese remainder theorem calculator?▼
A CRT calculator solves systems of modular congruences and returns the smallest nonnegative solution and the combined modulus.
What is the Chinese remainder theorem formula?▼
For two congruences x≡a mod m and x≡b mod n, a solution exists when a-b is divisible by gcd(m,n).
How do I use this CRT solver?▼
Enter two remainders and two moduli, then calculate. The tool checks compatibility and gives the combined congruence.
Do the moduli have to be coprime?▼
Coprime moduli always give a unique solution modulo mn, but non-coprime moduli can also work if the remainders are compatible.
Where is the Chinese remainder theorem used?▼
CRT is used in modular arithmetic, cryptography, calendar problems, coding contests, and fast computations with large integers.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.