Chinese Remainder Theorem Calculator – Solve Modular Equations

This tool helps you find the smallest number that satisfies a given set of modular arithmetic conditions.

Chinese Remainder Theorem Calculator

This calculator helps you find the smallest number x such that:

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ak (mod mk)

How it works:

The Chinese Remainder Theorem states that if you have k pairwise co-prime integers (m1, m2, …, mk) and integers (a1, a2, …, ak), there exists an integer x which satisfies all the remainders simultaneously.

1. Multiply all the moduli (m1, m2, …, mk) to get the product. 2. For each remainder and modulus pair, calculate the partial product (product divided by the modulus). 3. Compute the modular inverse of the partial product with respect to the corresponding modulus. 4. Sum up the product of each remainder, its partial product, and its modular inverse. 5. Finally, the result is the sum modulo the product of the moduli.

How to use:

  • Input the moduli as a comma-separated list (e.g., 3,5,7).
  • Input the corresponding remainders as a comma-separated list (e.g., 2,3,2).
  • Click the Calculate button to see the result.

Limitations:

This calculator assumes that the given moduli are pairwise co-prime. The algorithm will not work correctly if any of the moduli share a common factor other than 1.

Other Resources and Tools