Counting & Number Theory

Chinese Remainder & Compatible Congruences Calculator

Solve multiple integer remainder conditions, including compatible non-coprime moduli.

How the calculation works

Merge x=r modulo M with x=a modulo m. Let g=gcd(M,m); compatibility requires a−r divisible by g. Extended Euclid solves (M/g)k=(a−r)/g modulo (m/g). Update r to r+Mk and period to lcm(M,m), then normalize the residue. Repeat for all conditions.

Worked example

Example inputs — Remainders in matching order: 2 3 2; Positive moduli in matching order: 3 5 7. Expected results — Least nonnegative simultaneous solution: 23; Period of all simultaneous solutions: 105.

Assumptions and limits

Exact integer arithmetic is used for counts and integer results. Computation limits keep this browser tool responsive. Specify whether objects/groups are distinguishable and whether order matters; different conventions count different outcomes. One to one hundred congruences, each decimal integer at most 200 characters. Modulus one imposes no restriction. Non-coprime conditions are accepted only when compatible; inconsistent conditions are rejected. All solutions equal the reported residue plus an integer multiple of the period.

Reference and further reading

Read the underlying subject reference. Calculith is an independent implementation; the reference does not endorse or certify this tool.

Related calculators

Browse all 1000 calculators →

Example values are editable. Results are estimates where assumptions apply. Calculations run in your browser. Updated 2026-11-16.