Chinese remainder theorem
Given the remainders of an unknown number when divided by several numbers, for example 2 when divided by 3 and 3 when divided by 5, this algorithm finds the smallest such number by merging the conditions two at a time. The Chinese remainder theorem says that when no two divisors have a common factor, exactly one such number is below their product. When that product is only a few million, trying every number is enough (brute force).
Explanation
Which number leaves 2 when divided by 3 and 3 when divided by 5? Start at 2 and jump by 3: every number on the way, 2, 5, 8, leaves 2 when divided by 3. Check each against 5: 2 leaves 2, 5 leaves 0, and 8 leaves 3. The answer is 8.
Fig. 1. Jumping by 3 from 2 visits only numbers that leave 2 when divided by 3. The first one that leaves 3 when divided by 5 is 8.
The next answer is 23 = 8 + 15: adding 15 changes neither remainder. So the two conditions say one thing: the number leaves 8 when divided by 15.
Exactly one number from 0 to 14 works. Put each of them into a table, with a row for its remainder when divided by 3 and a column for its remainder when divided by 5. The 15 numbers fill all 3 · 5 = 15 cells, each exactly once, so every pair of remainders belongs to exactly one number below 15.
Fig. 2. The numbers 0 to 14 fill each cell of the table exactly once.
The same happens for any two coprime numbers in place of 3 and 5. With 4 and 6, which share the factor 2, it fails: the numbers 0 to 11 fill only half of the 4 · 6 = 24 cells and then repeat. No number leaves 1 when divided by 4 and 2 when divided by 6, because it would be odd and even at once.
Fig. 3. With divisors 4 and 6, the numbers 0 to 11 fill only half of the 24 cells and then repeat. The red cell is a pair of remainders no number has.
Divisors in contests are much larger. Which number leaves 1 when divided by 10^9 + 7 and 2 when divided by 10^9 + 9? The table would have about 10^{18} cells.
Do what worked before: start at 1 and jump by 10^9 + 7 until the remainder when divided by 10^9 + 9 is 2. This finds the answer, 500000007500000029, after 500000004 jumps. By the rule of thumb of about 10^8 simple steps per second, that is about 5 seconds for two conditions.
Count the jumps without making them. Go back to 3 and 5. Each jump adds 3, so it adds 3 to the remainder when divided by 5. Starting from 2, the remainder must go up by 1, the gap. Two jumps add 6, which leaves 1, so 2 jumps close a gap of 1. That 2 is the modular inverse of 3 modulo 5: 3 times it leaves 1. A gap of 2 would take 2 · 2 = 4 jumps, since 4 jumps add 12, which leaves 2. So the number of jumps is the gap times the inverse of the jump.
The large example works the same way. The extended Euclidean algorithm finds the inverse of 10^9 + 7 modulo 10^9 + 9 in 4 division steps: it is 500000004. The gap is 1, so 1 · 500000004 = 500000004 jumps, the count the walk found.
After the jumps, the two conditions have become one: the number leaves 500000007500000029 when divided by the product of the two divisors. The algorithm merges each next condition into it the same way, and each merge costs one inverse, O(\log m) steps.
Start with the first condition: the number leaves 2 when divided by 3, like 2, 5, 8 and every 3 after.
Fig. 4. Step through the merges with the buttons or the arrow keys. Green cards are merged, the blue card is being merged.
The final condition, leaves 53 when divided by 105, describes every answer: 53, 158, 263 and so on.
Implementation
Each condition is a pair: the number leaves a when divided by m. The merged condition so far is a pair too: the answer leaves x when divided by M. Every number leaves 0 when divided by 1, so the program starts with x = 0, M = 1, and the first merge copies the first condition.
For each next condition a, m:
Gap: find how far the remainder of
xis froma, as a number from 0 tom - 1:d = ((a - x) % m + m) % m. The extra+ mis there because in C++-4 % 7is-4.Jumps: each jump adds
M, which changes the remainder byM % m. The number of jumps isk = d * inverse(M % m, m) % m.Merge:
x += M * kandM *= m.
The functions ext_gcd and inverse come from the extended Euclidean algorithm page; inverse(a, m) returns a number from 0 to m - 1, or −1 if there is no inverse.
The input is n, then n lines a m with pairwise coprime m; the output is the smallest non-negative answer. The three conditions above:
3
2 3
3 5
4 7#include <iostream>
using namespace std;
// returns gcd(a, b) and writes x, y with a * x + b * y == gcd(a, b)
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
long long xa = 1, ya = 0;
long long xb = 0, yb = 1;
while (b != 0) {
long long q = a / b, r = a % b;
long long xr = xa - q * xb, yr = ya - q * yb;
a = b; xa = xb; ya = yb;
b = r; xb = xr; yb = yr;
}
x = xa;
y = ya;
return a;
}
// the inverse of a modulo m, or -1 if gcd(a, m) != 1
long long inverse(long long a, long long m) {
long long x, y;
if (ext_gcd(a, m, x, y) != 1) return -1;
return (x % m + m) % m;
}
int main() {
int n;
cin >> n;
// start: every number leaves 0 when divided by 1
long long x = 0, M = 1;
for (int i = 0; i < n; i++) {
long long a, m;
cin >> a >> m;
// gap
long long d = ((a - x) % m + m) % m;
// jumps
long long k = d * inverse(M % m, m) % m;
// merge
x += M * k;
M *= m;
}
// if the answer must be positive and x == 0, print M
cout << x << '\n';
}Each merge calls inverse once: O(n \log m) time, memory.
Divisors that are not coprime
When M and m are not coprime, inverse(M % m, m) returns −1. Let g be their GCD. M and m are both multiples of g, so jumps change the remainder only by multiples of g. If the gap d is not divisible by g, there is no answer, like the red cell in Fig. 3. Otherwise divide the gap, M and m by g and count the jumps modulo m / g. The new M is M * (m / g), the least common multiple. Leaves 1 when divided by 4 and 3 when divided by 6 has the answer 9, and the answers repeat every 12, not every 24.
Replace the loop body with these lines, add #include <numeric> for gcd, set bool ok = true; before the loop and print −1 after it if ok is false.
long long g = gcd(M, m);
// gap
long long d = ((a - x) % m + m) % m;
if (d % g != 0) { ok = false; break; } // no answer
// jumps
long long mg = m / g;
long long k = d / g * inverse(M / g % mg, mg) % mg;
// merge
x += M * k;
M *= mg;It prints 9 for 1 when divided by 4 and 3 when divided by 6, and −1 for 1 when divided by 4 and 2 when divided by 6.
Correctness proof
Merge "leaves when divided by " with "leaves when divided by ", where and are coprime.
An answer exists. Since \gcd(M, m) = 1, has an inverse modulo . jumps add k \cdot M, and with equal to the gap times the inverse, k \cdot M leaves the gap when divided by . So x + k \cdot M leaves when divided by , and still when divided by .
Only one answer is below M \cdot m. Take any two numbers that satisfy both conditions. Their difference is divisible by and by , and since they are coprime, by M \cdot m. So two different answers are at least M \cdot m apart, and only one of them is below M \cdot m. All answers differ by multiples of M \cdot m, like 8 and 23 for the divisors 3 and 5.
Fig. 5. 8 and 23 have the same remainders, so their difference is divisible by 15. Below 15 there is room for only one of them.
So after each merge, the merged condition describes exactly the answers to all conditions so far. The product of pairwise coprime divisors is coprime to the next divisor, so every merge has the inverse it needs.
Common mistakes
Assuming the divisors are coprime when they are not. On 1 when divided by 4 and 3 when divided by 6,
inverse(4, 6)returns −1 and the program prints −7 instead of 9.Printing 0 when the problem wants a positive answer, or the first one after a given day. If every
ais 0, the next answer after 0 isM. Shift by multiples ofMto where the problem asks.
Similar algorithms
The modular inverse undoes one multiplication modulo one number. Each merge needs one, modulo a divisor that is often not prime, so the shortcut that works only for prime divisors doesn't apply in general.
The least common multiple tells when two repeating events that start together meet again. The Chinese remainder theorem is for events that start at different offsets.
Brute force is enough for the first practice problem, where the product of the divisors is 21252.
Practice
Very easy · Chinese remainder theorem · Number theory · Brute force
Very easy · Chinese remainder theorem
Very easy · Number theory · Math
Very hard · Number theory
Very hard · Math · Number theory · Probabilities · Chinese remainder theorem