What does this Chinese Remainder Theorem calculator do?

This calculator solves systems of congruences written as x ≡ aᵢ (mod mᵢ) and returns a combined result in the form x ≡ r (mod M). The solution family is x = r + k × M, where k is any integer.

Unlike many basic CRT tools, this calculator is not limited to pairwise coprime moduli. It uses a general pairwise merge algorithm, so non-coprime moduli are allowed when the compatibility condition is satisfied.

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a number theory method for combining several remainder conditions into one modular solution.

For example, the system x ≡ 2 (mod 3) and x ≡ 3 (mod 5) becomes x ≡ 8 (mod 15). This means 8, 23, 38 and every number obtained by adding or subtracting multiples of 15 satisfies both original conditions.

• Remainder aᵢ: the value left when x is divided by mᵢ.
• Modulus mᵢ: the modular base; in this calculator it must be an integer at least 2.
• Solution family: the final result represents infinitely many integers, not only one number.
• Compatibility: for non-coprime moduli, the gcd must divide the difference between the remainders.

Classic CRT vs general CRT

The classic CRT statement usually assumes that every pair of moduli is coprime. General CRT removes that restriction and checks whether the non-coprime system is compatible.

For example, x ≡ 1 (mod 6) and x ≡ 3 (mod 8) has non-coprime moduli because gcd(6, 8) = 2. The difference between remainders is 2, which is divisible by 2, so the system is compatible and the calculator returns x ≡ 19 (mod 24).

How the calculation works

The calculator merges congruences one pair at a time. At each step, it checks compatibility, uses the extended Euclidean algorithm when needed, and produces a new combined congruence.

1. Each remainder is first normalized with Euclidean modulo, so negative remainders are converted to their standard representatives.
2. For two congruences, the calculator computes g = gcd(m1, m2) and diff = a2 − a1.
3. If diff is not divisible by g, that merge step has no solution.
4. If compatible, the algorithm uses a modular inverse from the extended Euclidean algorithm.
5. The merged modulus is M = lcm(m1, m2), and the merged remainder is normalized into that modulus.

All arithmetic is integer-based. The calculator uses BigInt internally, but the input fields still require integer remainders and integer moduli.

How are negative remainders handled?

Negative remainders are accepted and normalized automatically. Normalization means rewriting the same congruence using a remainder in the range from 0 to m − 1.

For example, x ≡ −1 (mod 5) is the same condition as x ≡ 4 (mod 5). The calculator shows a normalization note when the value you entered changes in this way.

Example 1: pairwise coprime moduli

The system x ≡ 2 (mod 3), x ≡ 3 (mod 5) is a classic CRT example because 3 and 5 are coprime.

1. The first congruence says x leaves remainder 2 when divided by 3.
2. The second says x leaves remainder 3 when divided by 5.
3. The smallest non-negative combined representative is 8.
4. The final result is x ≡ 8 (mod 15).
5. The solution family is x = 8 + k × 15, k ∈ ℤ.

Example 2: non-coprime but compatible moduli

The system x ≡ 1 (mod 6), x ≡ 3 (mod 8) is not pairwise coprime, but it is still solvable.

1. gcd(6, 8) = 2.
2. The remainder difference is 3 − 1 = 2.
3. Because 2 divides 2, the two congruences are compatible.
4. The calculator returns x ≡ 19 (mod 24).

This is the key reason the general CRT algorithm is useful: it does not reject non-coprime moduli automatically.

Example 3: no solution

The system x ≡ 1 (mod 6), x ≡ 2 (mod 4) has no solution, because the two remainder conditions are incompatible.

1. gcd(6, 4) = 2.
2. The remainder difference is 2 − 1 = 1.
3. 1 is not divisible by 2.
4. Therefore no integer can satisfy both congruences at the same time.

How to use the calculator

Enter one remainder and one modulus on each row. The calculator starts with two equations, and you can add rows until you have up to four congruences.

• Use the remainder field for aᵢ. Negative integer remainders are allowed.
• Use the modulus field for mᵢ. It must be an integer of at least 2.
• Do not enter decimals, fractions or symbolic expressions.
• If a remainder is outside the usual range, the calculator normalizes it before solving.
• If the system is incompatible, the result area explains the failed merge step.

Where CRT is useful

The Chinese Remainder Theorem is used in number theory, modular arithmetic, algorithm design and competitive programming.

• In university mathematics, it helps solve systems of congruences.
• In competitive programming, it appears in problems with several modular conditions.
• In modular arithmetic, it connects gcd, lcm and modular inverses.
• In advanced examples, it helps express a large solution set through a smaller modular representative.

Common mistakes

A common mistake is assuming that non-coprime moduli always make CRT impossible. They only make the compatibility test necessary.

• Forgetting that x ≡ r (mod M) represents a whole family of integer solutions.
• Rejecting negative remainders instead of normalizing them.
• Entering modulus 0 or 1 even though this calculator requires m ≥ 2.
• Expecting symbolic or polynomial congruence solving from a numeric CRT tool.
• Saying the solution is always unique without adding “modulo M”.

Limitations of this calculator

This calculator solves 2–4 integer congruences. It does not solve more than four congruences, negative moduli, modulus 1 edge cases, decimal inputs, symbolic congruences or polynomial congruences.

• Remainders and moduli must be integers.
• Moduli must be at least 2.
• The result is unique modulo M, not as a single isolated integer.
• The algorithm is pairwise merge, not matrix algebra or Gaussian elimination.
• No external data or official table is involved; this is a pure mathematical computation.