Chinese Remainder Theorem
Combine modular constraints into one congruence when the residue classes are compatible.
Chinese Remainder Theorem
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The Chinese remainder theorem combines several modular constraints into one. In contests it turns ``find a number that matches all these remainders'' into a constructive algorithm rather than a search.
When to Use It
Use CRT when:
a value is constrained by several congruences,
information is naturally split across different moduli,
one large-modulus computation is easier after merging smaller ones.
Core Idea
For coprime moduli, the system \[ x \equiv r_1 \pmod{m_1}, \qquad x \equiv r_2 \pmod{m_2} \] has a unique solution modulo \(m_1 m_2\).
In the generalized version, two congruences are compatible iff \[ r_1 \equiv r_2 \pmod{\gcd(m_1, m_2)}. \] If they are compatible, they can still be merged into one congruence modulo \(\mathrm{lcm}(m_1, m_2)\).
Key Insight
CRT is really an alignment problem. Each congruence describes an arithmetic progression, and the theorem tells me when those progressions overlap and how to describe the overlap compactly.
Operations / Main Technique
combine two congruences at a time,
use extended Euclid to solve the alignment step,
iterate that merge across a whole system.
Worked example.
The system \[ x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5 \] merges into \[ x \equiv 8 \pmod{15}. \]
Correctness Intuition
When the residues agree modulo the gcd of the moduli, the two arithmetic progressions are synchronized often enough to meet. Extended Euclid gives the coefficient needed to shift one progression onto the other. The merged modulus is the period of that overlap.
Complexity Analysis
Merging one pair of congruences takes \(O(\log m)\) because it relies on gcd and extended Euclid. Merging \(k\) congruences is linear in \(k\) times that gcd cost.
Implementation
The code supports the generalized pairwise merge, so it handles both coprime and merely compatible moduli. It returns a boolean success flag together with the merged congruence.
Common Pitfalls
Assuming the moduli are coprime when the statement does not say so.
Forgetting to normalize the merged residue into \([0, m-1]\).
Overflow when multiplying large moduli.
Treating an inconsistent system as if it had a solution.
Variants / Extensions
Garner's algorithm for reconstruction in mixed-radix form.
Using CRT after several independent modular computations.
Combining with modular inverse and extended Euclid in constructive number-theory problems.
Practice Problems
Find the first time two or more periodic events align.
Reconstruct a number from its residues.
Merge congruence constraints in a simulation or scheduling problem.
References
Code
Contest-ready reference implementation for the idea explained above.
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
bool combine_crt(long long r1, long long m1, long long r2, long long m2, long long& r, long long& m) {
long long x, y;
long long g = ext_gcd(m1, m2, x, y);
long long diff = r2 - r1;
if (diff % g != 0) {
return false;
}
long long lcm = m1 / g * m2;
long long step = m2 / g;
long long t = (__int128)(diff / g) * x % step;
if (t < 0) t += step;
r = (r1 + (__int128)m1 * t) % lcm;
if (r < 0) r += lcm;
m = lcm;
return true;
}
pair<long long, long long> chinese_remainder(const vector<long long>& rem, const vector<long long>& mod) {
long long r = 0;
long long m = 1;
for (int i = 0; i < (int)rem.size(); ++i) {
if (!combine_crt(r, m, rem[i], mod[i], r, m)) {
return {-1, -1};
}
}
return {r, m};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.