Chinese Remainder Theorem
Pillar: Fix — "Fix the remainders: \(x \equiv r_1 \pmod{m_1}\), \(x \equiv r_2 \pmod{m_2}\). The solution is forced."
Pillar: Set — "The solution lives in the intersection of two arithmetic progressions."
The Setup
You have two clocks. One cycles every 3 hours, currently showing 2. The other cycles every 5 hours, currently showing 3. What time is it?
In other words: find \(x\) such that \(x \equiv 2 \pmod{3}\) and \(x \equiv 3 \pmod{5}\).
You could brute force it. Check multiples of 3 offset by 2: \(2, 5, 8, 11, 14, \ldots\) Which of these gives remainder 3 when divided by 5? \(8 \div 5 = 1\) remainder \(3\). Done: \(x = 8\).
That worked because the moduli were tiny. Now imagine: \(x \equiv 31415 \pmod{99991}\) and \(x \equiv 27182 \pmod{99989}\). Brute force means scanning up to \(99991 \times 99989 \approx 10^{10}\) candidates. You need a formula.
The Chinese Remainder Theorem gives you one. It guarantees a unique solution modulo \(m_1 \cdot m_2\) (when the moduli are coprime), and it gives a constructive method to find it.
The Key Idea
Think of each congruence as an arithmetic progression. \(x \equiv 2 \pmod{3}\) is the set \(\{2, 5, 8, 11, 14, \ldots\}\). \(x \equiv 3 \pmod{5}\) is the set \(\{3, 8, 13, 18, 23, \ldots\}\). The solution is their intersection.
Two arithmetic progressions with coprime step sizes always intersect, and they intersect periodically with period \(\text{lcm}(m_1, m_2) = m_1 \cdot m_2\). That's the Set pillar at work — you're finding where two structured sets overlap.
The Fix pillar enters when you realize: fix the first congruence (write \(x = m_1 \cdot t + r_1\) for some integer \(t\)), then substitute into the second congruence and solve for \(t\). The value of \(t\) is forced by the modular inverse of \(m_1\) modulo \(m_2\).
Formal Statement
The Chinese Remainder Theorem (CRT): Let \(m_1, m_2\) be positive integers with \(\gcd(m_1, m_2) = 1\). For any integers \(r_1, r_2\), the system
has a unique solution modulo \(m_1 \cdot m_2\).
More generally, for pairwise coprime moduli \(m_1, m_2, \ldots, m_k\), the system \(x \equiv r_i \pmod{m_i}\) for all \(i\) has a unique solution modulo \(M = m_1 \cdot m_2 \cdots m_k\).
Constructive Proof (Two Moduli)
Fix the first congruence. Write \(x = m_1 \cdot t + r_1\). Substitute into the second:
Since \(\gcd(m_1, m_2) = 1\), the modular inverse \(m_1^{-1} \pmod{m_2}\) exists. Multiply both sides:
That pins down \(t\) modulo \(m_2\), which pins down \(x\) modulo \(m_1 \cdot m_2\):
And you get \(m_1^{-1} \pmod{m_2}\) from the Extended Euclidean algorithm (Ch3).
Worked Example
Solve: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\).
Step 1: Write \(x = 3t + 2\).
Step 2: Substitute: \(3t + 2 \equiv 3 \pmod{5}\), so \(3t \equiv 1 \pmod{5}\).
Step 3: Find \(3^{-1} \pmod{5}\). By Extended Euclidean (or just checking: \(3 \times 2 = 6 \equiv 1\)), the inverse is \(2\).
Step 4: \(t \equiv 2 \times 1 \equiv 2 \pmod{5}\).
Step 5: \(x = 3 \times 2 + 2 = 8\).
The solution is \(x \equiv 8 \pmod{15}\). Check: \(8 = 2 \times 3 + 2\) and \(8 = 1 \times 5 + 3\). Both congruences satisfied.
Iterative CRT: Combining Two at a Time
When you have \(k\) congruences, you don't need the full \(k\)-variable formula. Just combine them pairwise, left to right.
Start with \(x \equiv r_1 \pmod{m_1}\). Combine with the second congruence to get \(x \equiv r_{12} \pmod{m_1 m_2}\). Combine that with the third to get \(x \equiv r_{123} \pmod{m_1 m_2 m_3}\). And so on.
Each step uses the two-congruence formula. The modulus grows by a factor of \(m_i\) at each step.
Trace through a three-congruence system: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\).
| Step | Combine | Result |
|---|---|---|
| Init | — | \(x \equiv 2 \pmod{3}\) |
| 1 | with \(x \equiv 3 \pmod{5}\) | \(x \equiv 8 \pmod{15}\) |
| 2 | with \(x \equiv 2 \pmod{7}\) | \(x \equiv 23 \pmod{105}\) |
Check: \(23 = 7 \times 3 + 2\), \(23 = 4 \times 5 + 3\), \(23 = 3 \times 7 + 2\). All three satisfied.
The catch: the combined modulus \(m_1 m_2 \cdots m_k\) can overflow long long even when each \(m_i\) is moderate. With three moduli around \(10^6\) each, the product is \(10^{18}\) — barely fits. Four such moduli and you're past \(10^{24}\).
Garner's Algorithm: Avoiding Big Numbers
Garner's algorithm reconstructs the answer in mixed-radix representation and never forms the full product of all moduli. This makes it perfect when you need the answer modulo some output modulus (like \(10^9 + 7\)) rather than the exact value.
The idea: represent the solution \(x\) as
where \(0 \leq a_i < m_i\). These \(a_i\) are the "mixed-radix digits." Once you know them, you can evaluate \(x \bmod p\) for any output modulus \(p\) without ever computing \(x\) itself — just accumulate the terms modulo \(p\).
Finding the Mixed-Radix Digits
For \(a_0\): from \(x \equiv r_0 \pmod{m_0}\), we get \(a_0 = r_0\).
For \(a_1\): we know \(x = a_0 + a_1 m_0 + \cdots\), so \(x \equiv a_0 + a_1 m_0 \pmod{m_1}\). Since \(x \equiv r_1 \pmod{m_1}\):
For \(a_2\): strip off the first two terms and solve similarly:
The pattern: each digit is computed by subtracting contributions from earlier digits and dividing by the accumulated product of earlier moduli — all done modulo \(m_i\), so numbers stay small.
Trace: Garner on \(\{r_0=2, m_0=3\}\), \(\{r_1=3, m_1=5\}\), \(\{r_2=2, m_2=7\}\)
Digit \(a_0\): \(a_0 = r_0 = 2\).
Digit \(a_1\): \((r_1 - a_0) \cdot m_0^{-1} \pmod{m_1} = (3 - 2) \cdot 3^{-1} \pmod{5} = 1 \cdot 2 = 2\).
Digit \(a_2\): Start with \(r_2 = 2\). Subtract \(a_0 = 2\), multiply by \(m_0^{-1} \pmod{m_2} = 3^{-1} \pmod{7} = 5\) (since \(3 \times 5 = 15 \equiv 1\)). Get \((2 - 2) \times 5 = 0\). Subtract \(a_1 = 2\), multiply by \(m_1^{-1} \pmod{m_2} = 5^{-1} \pmod{7} = 3\) (since \(5 \times 3 = 15 \equiv 1\)). Get \((0 - 2) \times 3 = -6 \equiv 1 \pmod{7}\).
So \(a_2 = 1\).
Reconstruct: \(x = 2 + 2 \times 3 + 1 \times 3 \times 5 = 2 + 6 + 15 = 23\). Matches.
If you needed \(x \bmod 10^9 + 7\), you'd accumulate those terms modulo \(10^9 + 7\) — no overflow, no big integers.
The Non-Coprime Extension
Real problems don't always hand you coprime moduli. What if \(\gcd(m_1, m_2) = g > 1\)?
The system \(x \equiv r_1 \pmod{m_1}\), \(x \equiv r_2 \pmod{m_2}\) has a solution if and only if:
where \(g = \gcd(m_1, m_2)\). If this compatibility condition fails, no solution exists. If it holds, the solution is unique modulo \(\text{lcm}(m_1, m_2) = m_1 m_2 / g\).
The construction: reduce to the coprime case. Write \(m_1' = m_1 / g\) and \(m_2' = m_2 / g\). Since \(g \mid (r_2 - r_1)\), define \(\delta = (r_2 - r_1) / g\). Solve:
using the Extended Euclidean algorithm. Then \(x = m_1 \cdot t + r_1\), and the combined modulus is \(\text{lcm}(m_1, m_2)\).
This general version handles every case — coprime moduli are just the special case where \(g = 1\) and the compatibility condition is automatically satisfied.
Application: NTT Reconstruction
Number Theoretic Transforms (NTTs) work modulo a single prime. When you need the exact convolution result (which can be large), a common technique is to run the NTT modulo two or three different primes — say \(p_1 = 998244353\), \(p_2 = 985661441\), \(p_3 = 754974721\) — and reconstruct the true value using CRT.
Each NTT gives you \(c_i \equiv \text{result} \pmod{p_i}\). CRT combines them into a single value modulo \(p_1 p_2 p_3 \approx 7.4 \times 10^{26}\). If you know the true result fits in this range (or you only need it modulo some output prime), Garner's algorithm gives you the answer without big integer arithmetic.
This is exactly the setup Garner's was designed for: several congruences modulo known primes, output needed modulo a different prime.
The Code
Extended GCD
Using the Extended Euclidean algorithm from Ch3:
pair<long long, long long> extendedGCD(long long first, long long second) {
if (second == 0) return {1, 0};
auto [prevX, prevY] = extendedGCD(second, first % second);
return {prevY, prevX - (first / second) * prevY};
}
Combine Two Congruences (General Case)
This handles both coprime and non-coprime moduli. Returns \(\{-1, -1\}\) if no solution exists.
pair<long long, long long> combineCRT(long long remainder1, long long modulus1,
long long remainder2, long long modulus2) {
long long divisor = __gcd(modulus1, modulus2);
if ((remainder2 - remainder1) % divisor != 0) return {-1, -1};
long long reducedMod1 = modulus1 / divisor;
long long reducedMod2 = modulus2 / divisor;
long long combinedModulus = modulus1 / divisor * modulus2;
auto [coeffX, coeffY] = extendedGCD(reducedMod1, reducedMod2);
long long shift = (__int128)(remainder2 - remainder1) / divisor % reducedMod2 * coeffX % reducedMod2;
long long combinedRemainder = ((__int128)shift * modulus1 + remainder1) % combinedModulus;
if (combinedRemainder < 0) combinedRemainder += combinedModulus;
return {combinedRemainder, combinedModulus};
}
The __int128 casts prevent overflow in intermediate products. The variable shift is the value of \(t\) from the construction, reduced modulo \(m_2'\) to keep it small.
Iterative CRT Solver
long long solveSystemCRT(vector<long long>& remainders, vector<long long>& moduli) {
long long currentRemainder = remainders[0];
long long currentModulus = moduli[0];
for (int index = 1; index < (int)remainders.size(); index++) {
auto [nextRemainder, nextModulus] = combineCRT(currentRemainder, currentModulus,
remainders[index], moduli[index]);
if (nextModulus == -1) return -1;
currentRemainder = nextRemainder;
currentModulus = nextModulus;
}
return currentRemainder;
}
\(O(k \log M)\) time where \(k\) is the number of congruences and \(M\) is the maximum modulus (the log factor comes from each Extended GCD call). \(O(1)\) extra space.
Garner's Algorithm
Requires all moduli to be pairwise coprime primes (so that modular inverses can use Fermat's little theorem). Using modpow from Ch4 L2:
long long modpow(long long base, long long exponent, long long mod) {
long long result = 1;
base %= mod;
while (exponent > 0) {
if (exponent & 1) result = result * base % mod;
base = base * base % mod;
exponent >>= 1;
}
return result;
}
long long garnerReconstruct(vector<long long>& remainders, vector<long long>& moduli,
long long outputMod) {
int systemSize = remainders.size();
vector<long long> mixedRadixDigits(systemSize);
for (int current = 0; current < systemSize; current++) {
mixedRadixDigits[current] = remainders[current];
for (int previous = 0; previous < current; previous++) {
long long modularInverse = modpow(moduli[previous], moduli[current] - 2, moduli[current]);
mixedRadixDigits[current] = (mixedRadixDigits[current] - mixedRadixDigits[previous]
+ moduli[current]) % moduli[current];
mixedRadixDigits[current] = mixedRadixDigits[current] * modularInverse % moduli[current];
}
}
long long result = 0;
long long runningProduct = 1;
for (int index = 0; index < systemSize; index++) {
result = (result + mixedRadixDigits[index] % outputMod * (runningProduct % outputMod)) % outputMod;
runningProduct = runningProduct % outputMod * (moduli[index] % outputMod) % outputMod;
}
return result;
}
\(O(k^2 \log p)\) time where \(p\) is the largest modulus (each inverse costs \(O(\log p)\) via modpow). \(O(k)\) space for the mixed-radix digits.
Common Mistakes
-
Ignoring the non-coprime case. Many contest problems have moduli that share common factors. If you assume coprimality and skip the \(\gcd\) check, you'll get wrong answers or divide-by-zero. Always use the general
combineCRTunless you've proven the moduli are coprime. -
Overflow in the iterative solver. The combined modulus grows multiplicatively. After combining three moduli of size \(10^6\), the modulus is \(10^{18}\) — and the next multiply of
shift * modulus1will overflowlong long. Use__int128for intermediate products, or switch to Garner's when the product of moduli exceeds \(10^{18}\). -
Wrong remainder sign. In C++, the
%operator can return negative values when the dividend is negative. After computingcombinedRemainder, always check and addcombinedModulusif negative. Forgetting this is the most common source of WA on CRT problems.
Quick Recap
- CRT says a system \(x \equiv r_i \pmod{m_i}\) with pairwise coprime moduli has a unique solution modulo \(\prod m_i\).
- Constructive method: fix one congruence, substitute into the next, solve for the free variable using Extended Euclidean.
- Iterative CRT: combine congruences two at a time. Works for any number of equations.
- Garner's algorithm: reconstruct in mixed-radix form. Avoids big numbers entirely — perfect when you need the answer modulo an output prime.
- Non-coprime extension: solution exists iff \(\gcd(m_1, m_2) \mid (r_1 - r_2)\). Combined modulus is \(\text{lcm}(m_1, m_2)\).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CF 687B — Remainders Game | codeforces.com/contest/687/problem/B | Medium | Determine if CRT solution is unique given moduli |
| CSES — Chinese Remainder Theorem | cses.fi/problemset/task/2174 | Medium | Direct CRT with two congruences |
| CF 338D — GCD Table | codeforces.com/contest/338/problem/D | Hard | CRT combined with GCD structure |
| CF 1500A — Going Home | codeforces.com/contest/1500/problem/A | Medium-Hard | CRT with non-coprime moduli |
| CC — SANDWICH | codechef.com/problems/SANDWICH | Hard | Full pipeline: stars & bars → nCr with \(N\) up to \(10^{18}\) modulo composite \(m\). Factor \(m\) into prime powers, compute nCr mod each via Generalized Lucas, reassemble with CRT |
Next: Burnside's Lemma — counting objects up to symmetry, where the Fix pillar meets group theory.