Chinese Remainder Theorem Calculator
≡
(mod
)
Result
About Chinese Remainder Theorem
Definition
The Chinese Remainder Theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
Mathematical Notation
Given a system of congruences:
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)
where m₁, m₂, ..., mₙ are pairwise coprime, there exists a unique solution modulo M = m₁ × m₂ × ... × mₙ.
Properties
- The moduli must be pairwise coprime
- The solution is unique modulo the product of the moduli
- Used in cryptography and number theory
- Efficient for solving large systems of congruences
Example Problems
Example 1: Simple System
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Solution: x ≡ 23 (mod 105)
Example 2: Larger System
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 4 (mod 7)
Solution: x ≡ 53 (mod 210)
Advertisement Space