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.

A row of cells numbered 0 to 14. Cells 2, 5 and 8, three apart, are marked, with brackets showing each jump of 3; above them their remainders when divided by 5 are 2, 0 and 3. Cell 8, the one that leaves 3, is green.

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.

A table with 3 rows for the remainder when divided by 3 and 5 columns for the remainder when divided by 5; the numbers 0 to 14 appear one by one, each one row down and one column right of the previous, wrapping around, until every cell holds exactly one number and the cell in row 2, column 3 holding 8 turns green.

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.

A table with rows 0 to 3 for the remainder when divided by 4 and columns 0 to 5 for the remainder when divided by 6; the numbers 0 to 11 fill only 12 of the 24 cells in a checkerboard pattern, the cell in row 1, column 3 holding 9 is green, and the empty cell in row 1, column 2 is red because no number leaves 1 when divided by 4 and 2 when divided by 6.

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.

Three conditions, remainder 2 for divisor 3, 3 for 5 and 4 for 7, are merged two at a time; jumps of 3 go 2, 5, 8 and jumps of 15 go 8, 23, 38, 53, ending with remainder 53 for divisor 105.

Start with the first condition: the number leaves 2 when divided by 3, like 2, 5, 8 and every 3 after.

1/7

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:

  1. Gap: find how far the remainder of x is from a, as a number from 0 to m - 1: d = ((a - x) % m + m) % m. The extra + m is there because in C++ -4 % 7 is -4.

  2. Jumps: each jump adds M, which changes the remainder by M % m. The number of jumps is k = d * inverse(M % m, m) % m.

  3. Merge: x += M * k and M *= 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.

A table with 3 rows for the remainder when divided by 3 and 5 columns for the remainder when divided by 5; all cells are empty except the green cell in row 2, column 3, which holds both 8 and 23.

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 a is 0, the next answer after 0 is M. Shift by multiples of M to 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

Was this page helpful?