Chinese Remainder Theorem Calculator screenshot

Chinese Remainder Theorem Calculator

Solve x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂), including the non-coprime case, with the gcd and lcm printed.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Exact where arithmetic allows

Chinese Remainder Theorem Calculator

Solve x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂), including the non-coprime case, with the gcd and lcm printed.

What the page prints, and what it refuses

Every figure is printed with the rule or formula that produced it, and any numerical tolerance is stated on the result rather than implied. The page refuses an input the formula does not define and names the value it read; it prints no answer it cannot support.

The calculation runs entirely in this browser tab; nothing is uploaded.

The page solves two simultaneous congruences. With x ≡ 2 (mod 3) and x ≡ 3 (mod 5), every solution is x ≡ 8 (mod 15), and the page prints that class together with both checks.

When the moduli share a factor the system may still have a solution: x ≡ 1 (mod 4) and x ≡ 3 (mod 6) gives x ≡ 9 (mod 12). When the gcd does not divide the residue gap there is no solution, and the page says so instead of inventing one.

The condition for a solution

Let g be the gcd of the two moduli. The system has a solution exactly when g divides a₂ − a₁. Then the solution is unique modulo the lcm, and the page prints that class.

The arithmetic is the extended Euclidean inverse applied on the coprime parts, so it is exact for moduli far beyond a double's safe range. The check line reduces the answer modulo each modulus and compares it with the residue you typed.

How to use Chinese Remainder Theorem Calculator

Enter the first residue and modulus, then the second residue and modulus, then press Run.

The first line is the answer as a residue class. The gcd, the lcm and both checks follow.

What to Expect

Best for

  • Solving a pair of congruences exactly
  • Checking a CRT step in a cryptography exercise
  • Seeing why a non-coprime system has no solution

Not ideal for

  • Three or more congruences, which need the theorem applied repeatedly
  • A modulus of zero
  • Reading the answer as one integer rather than a class

What this tool keeps

  • Both residues and both moduli exactly

What may need cleanup

  • Nothing: the class is exact

Common errors

  • An unsolvable pair is refused with the gcd named
  • A non-positive modulus is refused by name

Example use cases

  • Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5)
  • See a non-coprime system resolve to one class
  • Check a CRT construction

Sample input

a₁ = 2, m₁ = 3, a₂ = 3, m₂ = 5

Sample output

x ≡ 8 (mod 15), with gcd 1 and lcm 15

Who this is for

  • Number theory students
  • Readers checking a CRT example

Frequently asked questions

Why is the answer a class rather than a number?

Any member of the class satisfies both congruences, and adding the lcm returns another member. Printing one integer would hide that every multiple of the lcm is equally correct.

When is there no solution?

When the gcd of the moduli does not divide the difference of the residues. The page prints the gcd and the difference so the failure is checkable.

Can the moduli be large?

Yes, up to 200 digits each. The inverse is computed with BigInt, so nothing is rounded.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.