How to use the chinese remainder theorem solver
- Enter each condition as a remainder and a modulus, meaning x leaves that remainder when divided by the modulus. The example uses 2 mod 3, 3 mod 5 and 2 mod 7.
- Add as many rows as you need, up to 12. Remainders can be negative, and numbers can have up to 30 digits.
- The moduli do not have to be coprime, but the remainders must then agree on the shared factors.
- Read the smallest non-negative solution, how often solutions repeat, and the check of each remainder.
Formula
combine x = r (mod m) and x = a (mod n): let g = gcd(m, n)
a solution exists when g divides a - r
x = r + m t, where t = ((a - r) / g) x inverse of (m / g) modulo (n / g)
the result is a single congruence modulo lcm(m, n); repeat with the next condition
The inverse comes from the extended Euclidean algorithm. All arithmetic uses exact whole numbers of any size, so large moduli are handled without rounding.
The classic remainders 2, 3 and 2
Find x with remainder 2 mod 3, 3 mod 5 and 2 mod 7. The moduli are coprime, so a solution exists and repeats every 3 x 5 x 7 = 105. The smallest is 23, since 23 = 7 x 3 + 2, 23 = 4 x 5 + 3 and 23 = 3 x 7 + 2. The next is 128.
With moduli that share factors, x = 2 mod 4, 4 mod 6 and 1 mod 9 has the solution 10 mod 36. The pair x = 1 mod 4 and x = 3 mod 6 gives 9 mod 12. The pair x = 0 mod 12 and x = 8 mod 18 has no solution, because the shared factor 6 divides 0 but not 8, so the remainders disagree.
Where the theorem helps
The Chinese remainder theorem says that when the moduli are pairwise coprime, a system of congruences always has exactly one solution below their product. It appears in puzzles about counting by different groupings, in calendars and cycle problems, and in cryptography and fast arithmetic with large numbers.
For single congruences, powers and inverses, use the Modular Arithmetic Calculator, and for common factors and multiples the GCF and LCM Calculator.
No solution
When two conditions disagree about a shared factor, no number satisfies both and the tool reports it. The page names the first conflict it finds. Check the remainders and the moduli, and remember that a remainder is reduced modulo m, so a negative remainder like -1 mod 7 is the same as 6 mod 7.
More logic and number tools
For related logic, chemistry and number problems, try the Continued Fraction Calculator, Boolean Expression Simplifier and Chemical Equation Balancer.
Assumptions and limits
- Each modulus is a whole number of 2 or more, and each remainder is a whole number.
- Numbers have up to 30 digits, and arithmetic is exact.
- The smallest solution is the smallest non-negative number.
- At least two conditions are needed.
Frequently asked questions
What is the Chinese remainder theorem?
It says that if the moduli have no common factors, a system of congruences has exactly one solution below the product of the moduli. All other solutions differ by multiples of that product.
Can the moduli share factors?
Yes, but a solution then exists only if the remainders agree on the shared factors. The tool checks this and reports a conflict if they do not.
How is the answer found?
Conditions are merged two at a time with the extended Euclidean algorithm, giving one congruence modulo the least common multiple, then the next condition is merged in.
What does the smallest solution mean?
It is the smallest non-negative number meeting every condition. Adding any multiple of the combined modulus gives all other solutions.