Chinese Remainder Theorem

Solve simultaneous congruences

Comma-separated, e.g. 2, 3, 2

Comma-separated, e.g. 3, 5, 7

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
Smallest solution x
23
Repeats every (modulus N)
105
General solution
x = 23 + 105·k, k ∈ ℤ
System of congruences
  • x ≡ 2 (mod 3)
  • x ≡ 3 (mod 5)
  • x ≡ 2 (mod 7)

The moduli are pairwise coprime, so there is a unique solution modulo their product (the classic theorem).

Chinese Remainder TheoremSieve diagram: one lane per congruence marks the values satisfying it; the highlighted column at x = 23 is the value satisfying every congruence.mod 3mod 5mod 70105x = 23

À propos de cette calculatrice

The Chinese Remainder Theorem Calculator solves a system of simultaneous congruences x ≡ aᵢ (mod nᵢ). It returns the smallest non-negative solution and the modulus over which the solution repeats, works even when the moduli are not pairwise coprime (returning the least common multiple), and reports when no solution exists. A number-line and sieve visual show how the per-congruence solution sets line up at the answer.

Exemples courants

  • x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23 (mod 105)
  • x ≡ 1 (mod 4), x ≡ 2 (mod 5) → x = 17 (mod 20)
  • x ≡ 2 (mod 6), x ≡ 8 (mod 10) → x = 8 (mod 30), moduli not coprime
  • x ≡ 1 (mod 2), x ≡ 0 (mod 4) → no solution (incompatible)
  • x ≡ 0 (mod 3), x ≡ 0 (mod 4), x ≡ 0 (mod 5) → x = 0 (mod 60)