Non Coprime CRT Solution

The Chinese Remainder Theorem merges congruences x ≡ r_i (mod m_i) into one solution mod lcm(m_i) when compatible.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Pairwise merge two congruences using extended GCD. Non-coprime moduli need checking (r2-r1) % gcd(m1,m2)==0. Generalized CRT iterates merges.

Try this in Python

def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def crt_two(r1: int, m1: int, r2: int, m2: int) -> int:
    g, x, _ = ext_gcd(m1, m2)
    if (r2 - r1) % g != 0:
        raise ValueError("no solution")
    lcm = m1 // g * m2
    t = ((r2 - r1) // g * x) % (m2 // g)
    return (r1 + t * m1) % lcm


print(crt_two(2, 3, 3, 5))

Common mistakes

• Assuming coprime moduli without check.
• Forgetting to normalize final answer into [0, lcm).
• Wrong lcm when merging many moduli.

Key takeaways

• Solve two-modulus CRT on paper before coding.
• For many equations, merge incrementally or use Garner’s algorithm.