Solve systems of linear congruences using the Chinese Remainder Theorem. Useful for number theory, modular arithmetic, and cryptography.
Enter integer remainders and positive integer moduli. Moduli must be pairwise coprime.
The Chinese Remainder Theorem states that if you have a system of congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ aₖ (mod nₖ), and the moduli n₁, n₂, ..., nₖ are pairwise coprime, then there is a unique solution modulo M = n₁ × n₂ × ... × nₖ.
This theorem is a central result in number theory and is widely used in modular arithmetic, cryptography, fast arithmetic algorithms, and computational mathematics.
The calculator here uses modular inverses and the extended Euclidean algorithm to construct the solution directly.
For each congruence x ≡ a (mod n), enter the remainder a and modulus n. All moduli must be positive integers and pairwise coprime.
Use Add Congruence to extend the system. You can remove entries as long as at least two remain.
The calculator shows the smallest nonnegative solution x and the combined modulus M.
Once one solution is found, all solutions are given by x = solution + Mk for integer k.
If moduli are not pairwise coprime, the standard CRT formula does not apply directly.
Ancient Counting Problem
The smallest solution is 23, and all solutions are 23 + 105k.
It means every pair of moduli has greatest common divisor 1.
Then the standard CRT may not apply directly. The system may have no solution or require a generalized method.
No. Reordering the congruences does not change the final solution modulo M.
A modular inverse of a mod m is a number b such that ab ≡ 1 (mod m).
CRT is used in cryptography, modular computation, computer algebra, and fast arithmetic algorithms.
The classical form applies to linear congruences. Nonlinear cases need other methods.
The theorem traces back to ancient Chinese mathematics, especially Sunzi’s work.
A modulus should be taken as a positive integer in standard modular arithmetic notation.
Related Tools