Chinese remainder theorem in code

Why this matters when you build with AI

A congruence is a condition of the form x ≡ a (mod m), which means that x leaves remainder a when divided by m. A system is a list of such conditions, and the task is to find an x that meets all of them. Contest problems and some production code, such as scheduling jobs on cycles or splitting a counter across moduli, use this kind of system.

An AI tool often writes the combination step for the easy case only. The common version multiplies the moduli, computes an inverse with extended Euclid, and adds the terms. That works when the moduli share no factor. When two moduli share a factor, the inverse does not exist, and the code keeps going with a wrong value.

We ran a naive two-congruence merge on x ≡ 2 (mod 4) and x ≡ 3 (mod 6). These two conditions cannot both hold. An x that leaves remainder 2 when divided by 4 is even, and an x that leaves remainder 3 when divided by 6 is odd. The naive merge takes the inverse of 4 modulo 6, which does not exist. The inverse function returned -1, and the merge carried on with that value. It printed x = 22, and 22 leaves remainder 4 when divided by 6, not 3. Nothing failed, and nothing printed a warning. The bug only shows if someone checks the answer against the original conditions.

A second risk is size. The combined modulus is the lcm of all the moduli, which grows fast. Three moduli near 10^9 give an lcm near 10^27. That does not fit in 64 bits. We multiplied the lcm of the first two moduli, 999999866000004473, by the third modulus 999999893 in 64-bit unsigned arithmetic. The result was 10323537015488757869, which is the true product 999999759000018810999521389 taken modulo 2^64, so the high digits are gone. The value looks like a number, and it is wrong.

This lesson builds the merge step that handles both cases. It detects a conflict, computes the combined congruence, and stops before the lcm can overflow. The examples are C++17, compiled with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2. Results below are from our runs on that setup.

The idea: merge two conditions into one

Start with one condition, x ≡ a1 (mod m1). Add a second, x ≡ a2 (mod m2). The set of x that meet both is either empty or a single residue class modulo L, where L is the lcm of m1 and m2. So the two conditions can always be written as one new condition, x ≡ a (mod L), or they conflict. A list of N conditions is handled by merging the first two, then merging the result with the third, and so on. This is why the code needs only one merge function.

Let g be the gcd of m1 and m2. The lcm is L = m1 / g × m2. The merge has three parts.

Check the conflict. Any x that meets both conditions has x - a1 divisible by m1 and x - a2 divisible by m2. Subtracting, a2 - a1 is a combination of m1 and m2, so it must be divisible by g. If it is not, the two conditions conflict, and no x exists.
Find the shift. Write x = a1 + m1 × k. We need m1 × k ≡ a2 - a1 (mod m2). Divide everything by g. This gives (m1 / g) × k ≡ (a2 - a1) / g (mod m2 / g). The number m1 / g and m2 / g now share no factor, so the inverse of m1 / g modulo m2 / g exists.
Build the new residue. Take k as the solution in the range 0 to m2 / g - 1. Then a = a1 + m1 × k is a solution, and reducing it modulo L gives the smallest non-negative one.

Worked example: merging by hand

Merge x ≡ 2 (mod 4) with x ≡ 4 (mod 6).

The gcd of 4 and 6 is g = 2. The difference a2 - a1 is 4 - 2 = 2, which is divisible by 2, so the system is consistent. The lcm is L = 4 / 2 × 6 = 12.

Next we solve 4k ≡ 2 (mod 6). Divide by 2: 2k ≡ 1 (mod 3). The inverse of 2 modulo 3 is 2, because 4 leaves 1. So k ≡ 2 (mod 3), and we take k = 2. Then a = 2 + 4 × 2 = 10. Check: 10 leaves remainder 2 when divided by 4, and remainder 4 when divided by 6. Both conditions hold. The residue modulo 12 is 10, so the merged condition is x ≡ 10 (mod 12).

The program below does the same steps, with the inverse found by extended Euclid. We traced the three sample conditions from the exercise. Starting from no condition, the first merge gave x ≡ 2 (mod 4), the second gave x ≡ 10 (mod 12), and the third, x ≡ 1 (mod 3), agreed with 10, so the final answer was x ≡ 10 (mod 12).

The library

The library has ext_gcd, which we used in the inverse lesson, a norm function for negative values, and crt_merge. The merge reports one of three outcomes: the new condition, a conflict, or an overflow. The LIMIT constant is 10^18. A lcm above this is reported as an overflow, not computed.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll LIMIT = 1000000000000000000LL;  // 1e18: the largest lcm we allow
 
// Returns g = gcd(a, b) and sets x, y so that a*x + b*y = g. Needs a, b >= 0.
ll ext_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}
 
// Value in [0, m) congruent to a. Works for negative a. Needs m >= 1.
ll norm(ll a, ll m) {
    ll r = a % m;
    return r < 0 ? r + m : r;
}
 
enum class Status { OK, INCONSISTENT, OVERFLOW_LCM };
 
struct Merged {
    Status status;
    ll a;  // residue of the combined congruence, in [0, m) when status is OK
    ll m;  // lcm of the moduli so far
};
 
// Combines x = a1 (mod m1) with x = a2 (mod m2). Needs m1, m2 >= 1.
// Every product below is smaller than the new lcm, which is at most LIMIT,
// so the calculation stays inside 64 bits.
Merged crt_merge(ll a1, ll m1, ll a2, ll m2) {
    ll x, y;
    ll g = ext_gcd(m1, m2, x, y);        // m1*x + m2*y = g
    ll diff = a2 - a1;
    if (diff % g != 0) return {Status::INCONSISTENT, 0, 0};
    ll m1g = m1 / g;
    ll m2g = m2 / g;
    if (m1g > LIMIT / m2) return {Status::OVERFLOW_LCM, 0, 0};  // m1g * m2 would exceed LIMIT
    ll L = m1g * m2;                      // the new lcm, <= LIMIT
    // Need m1 * k = diff (mod m2). Dividing by g gives m1g * k = diff/g (mod m2g).
    // From m1*x + m2*y = g we get m1g * x = 1 (mod m2g), so x is the inverse of m1g.
    ll k = norm(diff / g, m2g) * norm(x, m2g) % m2g;   // both factors < m2g, so the product fits
    ll a = norm(a1, m1) + m1 * k;         // m1 * k < m1 * m2g = L
    return {Status::OK, a % L, L};
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ll a = 0, m = 1;                     // no congruence yet: every x works
    for (int i = 0; i < n; i++) {
        ll ai, mi;
        cin >> ai >> mi;
        Merged r = crt_merge(a, m, ai, mi);
        if (r.status == Status::INCONSISTENT) { cout << "NO\n"; return 0; }
        if (r.status == Status::OVERFLOW_LCM) { cout << "OVERFLOW\n"; return 0; }
        a = r.a;
        m = r.m;
    }
    cout << a << ' ' << m << '\n';
    return 0;
}

Three points in the code matter. The conflict check comes before anything else, so an inconsistent pair is never merged. The overflow check compares m1g with LIMIT / m2 before the multiplication. Integer division rounds down, so m1g > LIMIT / m2 holds exactly when m1g * m2 would be above LIMIT. The last one is the reduction a % L at the end, which gives the smallest non-negative solution.

The product m1 * k is safe because k is less than m2g. So m1 * k is less than m1 * m2g, which is L, and L is at most 10^18. The sum norm(a1, m1) + m1 * k is below 2 × 10^18, which fits in a signed 64-bit integer, whose largest value is about 9.2 × 10^18. If you raise LIMIT above about 4 × 10^18, this sum can overflow, and you need __int128 for it. That is a GCC and Clang extension, and it is not part of the C++ standard.

Testing the merge

We wrote a separate test program, with the same crt_merge included, and ran it on four kinds of input.

Tiny systems against brute force. We generated 60000 random systems of one to four conditions. Each modulus was from 1 to 12 and each residue from -20 to 20. For each system the brute force tried every x from 0 to L - 1 and kept the first that met all conditions. The merge loop agreed on all 60000.
Planted solutions. We picked a random x0 below 10^15, and built conditions from it, so that every system is consistent. The merge never reported a conflict, and for all 50000 systems the final residue equalled x0 modulo the lcm, and the lcm equalled the exact value computed with __int128.
Conflicts against a pairwise rule. A system of conditions has a solution exactly when every pair of them has a solution. This is a standard result, and we used it as a check. For 50000 random systems of up to three conditions, the merge reported NO exactly when some pair conflicted.
Overflow against exact arithmetic. For 20000 random systems, the merge reported OVERFLOW exactly when the exact lcm of a prefix of the system passed 10^18.

All checks passed. These tests use small moduli for the brute force, and the rule in check 3 is a known result, so the checks are strong for small inputs and only sample the large ones.

Exercise: merge a list of congruences

The problem. The first line has N, with 1 at most N at most 100000. Each of the next N lines has two integers a and m, with |a| at most 10^9 and 1 at most m at most 10^9. Each line states x ≡ a (mod m). Process the lines in order, starting with no condition. Stop at the first line that makes the system inconsistent, and print NO. Stop at the first line that makes the lcm of all moduli so far exceed 10^18, and print OVERFLOW. If all N lines are processed, print the smallest non-negative x and the lcm of the moduli, separated by one space.

Stopping at the first failure is part of the rule. It gives one clear answer for every input, because a later line cannot change an earlier result.

Your plan. Start with a = 0 and m = 1. For each line, call crt_merge with the current pair and the new pair. Stop on the first status that is not OK. Use the program above as the solution.

The program. It is the program in the library section. Here is the sample input, and the real output of our run.

10 12

Here is a second sample, where the first two lines conflict.

2
2 4
3 6

NO

Here is a third sample, where the lcm passes 10^18 on the third line. The first two moduli are primes near 10^9, and their product is 999999866000004473, which is below 10^18.

3
1 999999937
1 999999929
1 999999893

OVERFLOW

We ran the program on these three inputs. The random tests described above used the same crt_merge function. The Python version below gives the exact combined residue for the first sample. Python integers do not overflow, so it does not stop at 10^18, and it shows the true lcm for the third sample.

Python · editable

The real output of our run was:

(10, 12)
NO
(1, 999999759000018810999521389)
True

The third line is the exact lcm, about 10^27, which the C++ version reports as OVERFLOW. Both answers are right for their own rules.

How to check your own version. Feed it random small systems and compare with a brute-force search over x from 0 to L - 1. Then build a system from a known x0, so it must be consistent, and check that your residue is x0 modulo the lcm.

Complexity

ext_gcd takes O(log m) steps for each merge.
crt_merge takes O(log m) time, with a constant number of operations after that.
The full merge over N lines takes O(N log M) time, where M is the largest modulus.
The program stores two 64-bit numbers and the lcm, so the memory is O(1).

Common mistakes

Multiplying the moduli when they share a factor. The symptom is a value that fails a condition, such as 22 for x ≡ 3 (mod 6). Use the gcd and the conflict check in crt_merge.
Using an inverse that does not exist. The symptom is a value of -1 from the inverse function, carried into the arithmetic with no error. Divide by g first, so the inverse is of m1 / g modulo m2 / g, which always exists.
Checking for conflict with the wrong test. Testing whether a2 - a1 is divisible by m1 or by m2 is wrong. The test is divisibility by g, the gcd of the two moduli.
Letting the lcm overflow silently. The symptom is a small or negative lcm after many merges. Compare m1g with LIMIT / m2 before the product.
Forgetting the sign of a2 - a1. C++ returns a negative remainder for a negative dividend. Use norm for residues and compare the remainder with 0, which works for both signs.
Returning a residue that is not reduced. The symptom is an answer equal to a plus a multiple of the lcm, such as 22 where 10 is the smallest. Reduce the residue modulo the new lcm.

A prompt to check AI output

Give this prompt to an AI tool with your merge code. A good answer names the case where the gcd is greater than 1, gives a pair of conditions that conflict, and shows what the code returns for them.

Here is my C++ function that merges x = a1 (mod m1) with x = a2 (mod m2) by computing
the inverse of m1 modulo m2 with extended Euclid. Do not rewrite it yet. Tell me what it
returns for (a1, m1) = (2, 4) and (a2, m2) = (3, 6), and whether the true answer exists.
Then say how the function behaves when m1 and m2 share a factor, and what it does when an
inverse does not exist. Point to the line where a check is missing, if there is one.

A correct answer says that no x exists, because the two conditions conflict. It says that the inverse of 4 modulo 6 does not exist, and that the code must check the gcd first. If the AI says the answer is 22 and calls it correct, check 22 modulo 6 yourself.

Checklist

Compute g = gcd(m1, m2) before anything else.
Reject the pair when (a2 - a1) is not divisible by g.
Divide by g before inverting, so the inverse exists.
Check the lcm against the limit before the multiplication, not after.
Reduce the residue modulo the new lcm before you print or store it.
Test with moduli that share a factor, such as 4 and 6, and with a conflicting pair.
Test with a value of a that is negative, and a modulus of 1.

Practice

Each practice problem has a hint. Try each one before you read the answer under the line "Show the answer".

Solve x ≡ 1 (mod 4) and x ≡ 2 (mod 3) by hand. Hint: the moduli share no factor, so the answer is unique modulo 12. Try the values 1, 5, 9 for the first condition.

Show the answer The value 5 leaves remainder 1 when divided by 4, and remainder 2 when divided by 3. So x ≡ 5 (mod 12). Check: 5 mod 4 is 1, and 5 mod 3 is 2.

Decide whether x ≡ 0 (mod 6) and x ≡ 5 (mod 9) have a common solution. Hint: the gcd of 6 and 9 is 3, and the difference of the residues must be divisible by it.

Show the answer They do not. The gcd is 3, and 5 - 0 = 5 is not divisible by 3. Any x that is a multiple of 6 is a multiple of 3, so its remainder modulo 9 is a multiple of 3, which cannot be 5.

Merge x ≡ 3 (mod 8) with x ≡ 5 (mod 12). Hint: the gcd is 4, and 5 - 3 = 2 is not divisible by 4.

Show the answer They conflict. The gcd of 8 and 12 is 4, and the difference 2 is not a multiple of 4, so the program prints NO.

Merge x ≡ 1 (mod 6) with x ≡ 3 (mod 4). Hint: the gcd is 2, and the difference 2 is divisible by 2. Divide the equation by 2 before you look for the inverse.

Show the answer Let x = 1 + 6k. Then 6k ≡ 2 (mod 4), which gives 3k ≡ 1 (mod 2), so k is odd. Take k = 1, giving x = 7. Check: 7 mod 6 is 1, and 7 mod 4 is 3. The lcm is 12, so the answer is x ≡ 7 (mod 12).

Explain why the overflow check m1g > LIMIT / m2 is exact. Then explain why a single merge of two moduli up to 10^9 can never overflow, while a list of three can. Hint: compare the largest possible product of two moduli with 10^18.

Show the answer The check is exact because integer division rounds down. If m1g is greater than the floor of LIMIT / m2, then m1g is at least that floor plus one, and the product is at least LIMIT plus m2, which is above LIMIT. If m1g is at most the floor, the product is at most LIMIT. A single merge cannot overflow, because m1g is at most 10^9 and m2 is at most 10^9, so the product is at most 10^18, which is LIMIT. The lcm after one merge is therefore within the limit. A third modulus can multiply that lcm by up to 10^9 again, which is how the third sample passes 10^18.

Summary

Merge congruences one at a time. Divide by the gcd before you invert, reject any pair whose residues differ by a number that the gcd does not divide, and check the lcm against the limit before you multiply. Reduce the residue modulo the lcm before you print it. Test on small systems against brute force, and on systems built from a known answer.