Chinese Remainder Theorem (CRT): The Modular Arithmetic Superpower

Algorithm/Topic Statement#

The Chinese Remainder Theorem (CRT) is a foundational result in number theory that lets you reconstruct a unique integer from its remainders against several pairwise coprime moduli. Given a system of simultaneous congruences such as x is congruent to a1 modulo m1, x is congruent to a2 modulo m2, and so on up to mk, CRT guarantees exactly one solution x in the range from zero to M minus one, where M is the product of all the moduli. The theorem is older than algebra as we know it, going back to the 3rd century Chinese mathematician Sun Tzu, but it powers astonishingly modern technology like RSA optimization, secret sharing, and large-integer arithmetic in competitive programming.

Why This Topic Matters#

CRT might look like a niche curiosity, but it shows up everywhere once you start looking. In cryptography, RSA decryption is roughly four times faster when the private key is split into two halves modulo p and modulo q and recombined using CRT. In competitive programming, you often need to compute combinatorial quantities modulo a non-prime number like 10 to the 6th. By splitting that modulus into prime power factors, computing each piece independently, and stitching the result together with CRT, you turn an impossible problem into a tractable one. Interviewers at companies that emphasize math, such as Jane Street, Two Sigma, Google Brain, and security teams at Amazon and Apple, lean on CRT-flavored questions to filter candidates who really understand modular arithmetic versus those who only memorize shortcuts. Beyond interviews, CRT is the secret sauce behind digital signal processing, error-correcting codes, and even calendar algorithms that match cycles of different lengths.

The Core Insight (math intuition + proof sketch)#

The math intuition is simpler than it looks. If you know the remainder of an unknown number x when divided by 3 and by 5, you essentially know x modulo 15 because 3 and 5 are coprime. The Chinese Remainder Theorem generalizes this observation: as long as the moduli share no common factor, every combination of remainders corresponds to exactly one residue modulo the product. The proof sketch uses construction. For each i, define M as the full product of all moduli and Mi as M divided by mi. Because mi is coprime to every other modulus, Mi has a multiplicative inverse modulo mi. Call that inverse yi. Now form x as the sum, over every i, of ai times Mi times yi, all reduced modulo M. The trick is that Mi is divisible by every mj except mi, so the entire sum collapses to ai modulo mi for the i-th congruence. Plug it in and the residues match exactly. Uniqueness follows because if two solutions both satisfy the same system, their difference is divisible by every mi and therefore by their product M, forcing them to be equal modulo M.

When the moduli are not coprime, CRT still works in a softer form. A pair of congruences x congruent to a1 modulo m1 and x congruent to a2 modulo m2 has a solution if and only if a1 minus a2 is divisible by the gcd of m1 and m2. If that compatibility condition holds, you can merge the two into a single congruence modulo the lcm of m1 and m2 using the extended Euclidean algorithm. This generalized CRT is what you actually use in practice, because real-world moduli are rarely all prime.

Visual Dry Run / Worked Example#

Let us solve the classic puzzle: find x with x congruent to 2 modulo 3, x congruent to 3 modulo 5, and x congruent to 2 modulo 7. The moduli are pairwise coprime, so M is 3 times 5 times 7 which equals 105.

Compute M1 as 105 divided by 3 which gives 35, M2 as 105 divided by 5 which gives 21, and M3 as 105 divided by 7 which gives 15. Now find inverses. The inverse of 35 modulo 3 is the inverse of 35 mod 3, which is the inverse of 2 mod 3, which is 2 since 2 times 2 is 4 and 4 mod 3 is 1. The inverse of 21 modulo 5 is the inverse of 1 mod 5 which is 1. The inverse of 15 modulo 7 is the inverse of 1 mod 7 which is 1.

Stitch them together: x equals 2 times 35 times 2 plus 3 times 21 times 1 plus 2 times 15 times 1, which is 140 plus 63 plus 30, totaling 233. Reduce 233 modulo 105 to get 23. Sanity check: 23 mod 3 is 2, 23 mod 5 is 3, 23 mod 7 is 2. Every congruence is satisfied. This is the unique answer in the range zero to 104.

Solution / Implementation#

Python (with extended GCD and generalized CRT)#

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y
 
def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for a, m in zip(remainders, moduli):
        Mi = M // m
        _, yi, _ = ext_gcd(Mi, m)
        x = (x + a * Mi * yi) % M
    return x % M
 
def crt_pair(a1, m1, a2, m2):
    g, p, q = ext_gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return None
    lcm = m1 // g * m2
    diff = (a2 - a1) // g
    x = (a1 + m1 * (diff * p % (m2 // g))) % lcm
    return x, lcm
 
print(crt([2, 3, 2], [3, 5, 7]))

JavaScript#

function extGcd(a, b) {
  if (b === 0n) return [a, 1n, 0n];
  const [g, x1, y1] = extGcd(b, a % b);
  return [g, y1, x1 - (a / b) * y1];
}
 
function crt(remainders, moduli) {
  let M = 1n;
  for (const m of moduli) M *= BigInt(m);
  let x = 0n;
  for (let i = 0; i < remainders.length; i++) {
    const a = BigInt(remainders[i]);
    const m = BigInt(moduli[i]);
    const Mi = M / m;
    const [, yi] = extGcd(Mi, m);
    x = (x + a * Mi * yi) % M;
  }
  return ((x % M) + M) % M;
}
 
console.log(crt([2, 3, 2], [3, 5, 7]).toString());

Time complexity is order k log of the largest modulus due to the extended GCD calls. Space is order one beyond the input. Always use BigInt in JavaScript when products approach 2 to the 53.

Common Mistakes#

A frequent bug is forgetting to handle negative results from extended GCD. The inverse may come back negative; you must add the modulus to wrap it back into the canonical range. Another trap is assuming moduli are always coprime. Real interview prompts often slip in two moduli sharing a factor, and naive CRT silently returns garbage. Always verify pairwise gcd or use the generalized merging form. Programmers also overflow when computing ai times Mi times yi in fixed-width integers; either use 128-bit arithmetic, Python big integers, or mulmod helpers. Finally, do not forget to mod the final answer by M before returning, because intermediate sums grow well past M.

Interview Tips#

When CRT pops up in an interview, do not jump straight to the formula. Walk through a tiny example out loud first, like remainders 2 modulo 3 and 3 modulo 5, to demonstrate that you understand why coprimality matters. Mention that you would prefer the iterative pairwise merging approach in production code because it handles non-coprime moduli and avoids one giant extended GCD. If the interviewer asks about cryptography, bring up RSA and how CRT speeds up decryption. If they push on edge cases, acknowledge that incompatible systems must return no solution rather than wrong answers, and describe the gcd divides difference test that detects them.

Follow-up Questions#

How would you adapt CRT when one of the moduli is one? What if you only need x modulo a particular prime power and the input system is huge? How does CRT relate to polynomial interpolation, and could you explain Lagrange interpolation as an analogue over polynomial rings? Could you implement RSA decryption with CRT optimization end-to-end and compare it to the naive approach on a 2048-bit key?

Key Takeaways#

• CRT reconstructs an integer from remainders against pairwise coprime moduli, returning a unique answer modulo their product.
• The construction uses Mi as M divided by mi and the modular inverse of Mi modulo mi, both obtainable via extended GCD.
• Generalized CRT merges two congruences when their gcd divides the difference of remainders, replacing the system with one congruence modulo the lcm.
• The theorem powers RSA, large-integer modular arithmetic, secret sharing, and competitive programming counting tricks.
• Always guard against negative inverses, overflow in the product, and silently failing on non-coprime moduli.
• Practicing CRT sharpens broader fluency in modular arithmetic, which is required for almost every number theory interview question.