Chinese Remainder Theorem: Explained with Examples

The Chinese Remainder Theorem answers a simple question: is there a number that leaves prescribed remainders when divided by several different moduli? For example, can you find a number x such that x leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7? The theorem says that when the moduli are pairwise coprime — no two of them share a common factor larger than 1 — such a number always exists, and it is unique modulo the product of the moduli.

The CRT matters because it lets us break a hard problem modulo a big number into easy problems modulo small numbers. It is used in fast computer arithmetic, in the RSA cryptosystem (where it speeds up decryption), and in scheduling problems where several repeating cycles must line up. Any time remainders from different divisors have to be reconciled, the CRT is the tool.

Key Concepts

• System of congruences: x ≡ a1 (mod m1), x ≡ a2 (mod m2), and so on up to x ≡ ak (mod mk).
• Pairwise coprime: gcd(mi, mj) = 1 for every i ≠ j; the standard condition for the theorem.
• Combined modulus: M = m1·m2·…·mk; the solution is unique modulo M.
• Partial products: Mi = M/mi, the product of all the moduli except mi.
• Modular inverses: yi is the inverse of Mi modulo mi; it exists because gcd(Mi, mi) = 1.
• General case: when moduli share factors, a solution exists only if ai ≡ aj (mod gcd(mi, mj)) for every pair.

Formulas

• CRT solution: x ≡ a1·M1·y1 + a2·M2·y2 + … + ak·Mk·yk (mod M), where M is the product of all mi, Mi = M/mi, and yi is the inverse of Mi modulo mi.
• Uniqueness: any two solutions differ by a multiple of M, so there is exactly one solution modulo M.
• Two-congruence shortcut: for x ≡ a (mod m) and x ≡ b (mod n) with gcd(m, n) = 1, one solution is x = a + m·((b − a)·m^−1 mod n).
• Compatibility condition (non-coprime moduli): solvable exactly when ai ≡ aj (mod gcd(mi, mj)) for all i and j.

Worked Example

Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Step 1: check the moduli 3, 5 and 7 are pairwise coprime — yes. Step 2: M = 3·5·7 = 105. Step 3: M1 = 105/3 = 35; its inverse mod 3: 35 ≡ 2 (mod 3), and 2·2 = 4 ≡ 1, so y1 = 2. M2 = 105/5 = 21 ≡ 1 (mod 5), so y2 = 1. M3 = 105/7 = 15 ≡ 1 (mod 7), so y3 = 1. Step 4: x = 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233. Step 5: reduce modulo 105: 233 − 210 = 23. Verification: 23 ÷ 3 = 7 remainder 2 ✓; 23 ÷ 5 = 4 remainder 3 ✓; 23 ÷ 7 = 3 remainder 2 ✓. Every solution is x ≡ 23 (mod 105).

Common Misconceptions

• "The moduli must always be coprime." Coprime moduli guarantee a solution, but the theorem has a wider form: with shared factors the system can still be solved, provided the remainders agree modulo each shared factor. For instance x ≡ 1 (mod 4) and x ≡ 3 (mod 6) is solvable because 1 ≡ 3 (mod 2).
• "The solution is just the product of the remainders." No — the formula weights each remainder ai by Mi·yi. Multiplying the remainders directly gives a meaningless number.
• "There is only one solution among all integers." The solution is unique only modulo M. Adding or subtracting multiples of M gives infinitely many integer solutions, all congruent to each other modulo M.

Real-World Applications

• RSA decryption speedup: instead of computing c^d mod n with a huge n = pq, servers compute the result mod p and mod q separately and combine them with the CRT, which is much faster.
• Parallel computer arithmetic: large integers are represented by their remainders modulo several small primes, allowing addition and multiplication to run in parallel on the pieces.
• Calendar and scheduling: finding a day when several cycles (shifts, maintenance windows, festivals) coincide is a CRT problem.
• Secret sharing: some cryptographic secret-sharing schemes split a secret into remainder-shares that the CRT recombines.

The Chinese Remainder Theorem says that compatible remainder conditions always have a simultaneous solution, unique modulo the product of the moduli. The constructive formula builds it from the partial products Mi and their inverses yi, and the worked example shows every step: compute M, the Mi, the yi, form the weighted sum, and reduce. Whenever remainders come from different divisors, check coprimality first, then let the formula do the rest.