Chinese Remainder Theorem Calculator

Solve systems of congruences.

FreeNo accountOn your device

Runs in your browser. How to verify

Loading tool…

About this tool

Enter remainders and moduli to find the smallest x that satisfies every congruence. x ≡ 2 mod 3, x ≡ 3 mod 5 and x ≡ 2 mod 7 gives x = 23, Sunzi's classic puzzle.

How to use

1
Step 1
Enter the remainders separated by commas.
2
Step 2
Enter the moduli in the same order.
3
Step 3
Press Calculate.

How it works

When the moduli are pairwise coprime, the solution is unique modulo their product. Here 3 × 5 × 7 = 105, so every solution is 23 + 105k. The tool builds the answer from modular inverses.

x ≡ aᵢ (mod mᵢ)  →  x unique mod M = m₁m₂…mₖ

Worked example

Two congruences

Input
remainders 3, 4; moduli 5, 7
Output
18
Walkthrough
18 = 3×5 + 3 so 18 ≡ 3 mod 5, and 18 = 2×7 + 4 so 18 ≡ 4 mod 7. The moduli product is 35, so 18 is the smallest answer.

Limitations

  • The moduli must be pairwise coprime. Moduli 4 and 6 return an error even if a solution exists.
  • Give one remainder for each modulus.

Questions

What is x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7)?
x = 23, repeating every 105.
What is x ≡ 3 (mod 5) and 4 (mod 7)?
18.
Why does moduli 4 and 6 fail?
They share the factor 2, so the tool requires coprime moduli and reports that no inverse exists.

Features

  • Any number of congruences
  • Smallest non-negative solution
  • Runs in your browser

Related resources

Guides and videos from around the web—opens on YouTube or the publisher’s site.

  • Derivative as a concept

    Khan Academy

    When general calculators hand off to calculus tools.

    Watch on YouTube
  • Scientific notation examples

    Khan Academy

    Worked examples to compare with calculator output.

    Watch on YouTube
  • Percentages

    Math is Fun

    Percent of / percent change patterns for everyday calculators.

  • Data Index

    Math is Fun

    Stats and probability explainers for data tools.