Chinese Remainder Theorem Calculator
Enter two or three congruences to find the unique solution modulo the product of the moduli.
Result
How it is calculated
You enter two or three congruences x ≡ ri (mod mi). Each modulus must be a whole number of at least 2, each remainder a whole number (a negative one is reduced into the range 0 to m − 1), and every pair of moduli must share no common factor. Let M = m1 × m2 × m3 and Mi = M ÷ mi. The tool finds the inverse yi of Mi modulo mi with the extended Euclidean algorithm, then x = Σ ri × Mi × yi mod M. It shows x and M only, not the working. A pair left completely blank is skipped, but a half-filled pair, a product above 1012 or non-coprime moduli give no result.
Worked example
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). The moduli 3, 5 and 7 are pairwise coprime, so M = 3 × 5 × 7 = 105. Then M1 = 35, M2 = 21, M3 = 15, with inverses 2, 1 and 1 respectively. Sum: 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233, and 233 mod 105 = 23. Result: x = 23, unique modulo 105. Check: 23 leaves 2 on division by 3, 3 by 5 and 2 by 7.
Common mistakes
- Using moduli that share a factor, such as 4 and 6. The tool requires pairwise coprime moduli and returns no result for them, even if a solution happens to exist.
- Reading the answer as the only solution. x is unique only modulo M, so 23 + 105 = 128 solves the system as well.
- Swapping a remainder and its modulus. In the congruence x ≡ 2 (mod 3) the 3 goes in the modulus field, and the 2 in the remainder field.
- Entering a remainder that is not smaller than the modulus and expecting it to be rejected. A value like 5 with modulus 3 is simply reduced to 2.
- Leaving one field of a pair empty. A pair must be filled in completely or left entirely blank, otherwise nothing is calculated.
About this calculator
The Chinese Remainder Theorem says that if you know the remainder of an unknown number x when divided by several moduli that are pairwise coprime (no two of them share a common factor), then there is exactly one value of x, modulo the product of all those moduli, that satisfies every congruence x ≡ r (mod m) simultaneously. The theorem takes its name from an old Chinese mathematics text that posed the puzzle of counting a group of soldiers using their remainders when lined up in rows of different sizes.
Beyond the classic puzzle, CRT is genuinely load-bearing in modern computing: RSA implementations use it to speed up private-key decryption by working modulo each prime factor separately and recombining the results, and it underlies calendar arithmetic, certain error-detecting codes, and hashing schemes that split a large modulus into smaller coprime pieces.
This calculator takes two or three congruences x ≡ r (mod m), checks that the moduli are pairwise coprime, and returns the unique solution x together with the modulus it holds under (the product of your moduli). It shows the result only, not the step-by-step working.
Was this helpful?
You can pick up to 3 reactions.
Popular calculators
Loan Calculator
Monthly payment, total interest and full amortization schedule.
Percentage Calculator
Percent change, percent of, and ratio calculations.
Discount Calculator
Calculate final price, savings, and discount amount.
BMI Calculator
Body mass index from height and weight (metric or imperial).
Age Calculator
Compute your exact age in years, months and days from a birth date.
Compound Interest Calculator
Calculate the final amount and interest earned with compounding.
All Calculators
No calculators found
Comments (0)