Chinese Remainder Theorem (CRT)

CRT combines conditions x≡rᵢ (mod mᵢ) into a single residue class. For pairwise coprime positive moduli a solution always exists and is unique modulo their product. With shared factors, conditions may conflict; the generalized version tests compatibility and uses the LCM as the combined period. Our complete program merges equations one at a time, supports negative remainders, and explicitly limits combined period size to avoid overflow.

Prerequisites: Extended Euclid; modular inverses; LCM.

Build the idea

1. 1. Understand the coprime theorem

   For moduli 3 and 5, x≡2 (mod 3), x≡3 (mod 5) has answer x≡8 (mod 15). The 15 residue classes correspond bijectively to pairs of residues because coprimality prevents two distinct classes from sharing both remainders. For several pairwise coprime moduli, repeated merging gives a unique class modulo their product.

2. 2. Reduce a generalized merge to an equation

   Suppose current class is x=R+M·t, and the next requires x≡r (mod m). Then M·t≡r−R (mod m). Let g=gcd(M,m). Compatibility is exactly g dividing r−R. Divide by g and use Extended Euclid to invert M/g modulo m/g. This yields t modulo m/g, and the new period is M·(m/g)=lcm(M,m).

   $$\mathrm{Mt}\equiv r-R\left(\mathrm{mod}m\right)$$

3. 3. Follow a shared-factor example

   Merge x≡2 (mod 6) and x≡8 (mod 9). GCD is 3 and the difference 6 is divisible by 3, so reduce to 2t≡2 (mod 3). Thus t≡1, giving x=2+6=8 and combined modulus 18. In contrast x≡1 (mod 2), x≡0 (mod 4) conflicts because the difference is not divisible by gcd 2.

4. 4. Keep arithmetic within a documented domain

   The program permits individual and combined moduli up to 10^12. Before multiplying M by m/g, check the bound by division. The inverse coefficient times a difference may be much larger than 64 bits even when its residue is small, so multiply that pair by repeated doubling modulo m/g. Because the modulus is ≤10^12, each addition/doubling is safely below 2×10^12. After t is reduced, M·t is below the checked combined modulus.

5. 5. Distinguish incompatibility from implementation limits

   NO SOLUTION certifies an incompatible merge. LIMIT EXCEEDED means this bounded implementation cannot represent the required combined period; it does not imply the mathematical system is inconsistent. Modulus one adds no restriction. Starting with R=0,M=1 represents all integers, so k=0 prints 0 1. Canonical residues always satisfy 0≤R<M.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
using ll=long long;
ll extended(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1,g=extended(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1; // Substitute the smaller equation back into a,b.
    return g;
}
ll normalize(ll x,ll m){
    x%=m;
    if(x<0){
        x+=m;
    }
    return x;
}
ll multiplyMod(ll a,ll b,ll m){
    ll answer=0;
    a=normalize(a,m); // m<=10^12, so doubling stays below 2*10^12.
    while(b>0){
        if(b&1){
            answer=(answer+a)%m;
        }
        a=(a+a)%m;
        b/=2;
    }
    return answer;
}
int main(){
    int k;
    std::cin>>k;
    ll residue=0,modulus=1;
    const ll LIMIT=1000000000000LL;
    for(int i=0;i<k;++i){
        ll r,m;
        std::cin>>r>>m;
        r=normalize(r,m);
        ll x,y,g=extended(modulus,m,x,y),difference=r-residue;
        if(difference%g!=0){
            std::cout<<"NO SOLUTION\n";
            return 0;
        }
        ll quotient=m/g;
        if(modulus>LIMIT/quotient){
            std::cout<<"LIMIT EXCEEDED\n";
            return 0;
        }
        ll combined=modulus*quotient;
        ll step=multiplyMod(normalize(difference/g,quotient),normalize(x,quotient),quotient);
        residue=(residue+modulus*step)%combined; // Product is < combined<=LIMIT.
        modulus=combined;
    }
    std::cout<<residue<<' '<<modulus<<'\n';
}

Complexity analysis

O(k log L) machine-arithmetic work under L=10^12: each merge uses logarithmic Euclid plus logarithmic repeated-doubling multiplication. O(log L) recursion stack and O(1) stored system state; input is processed incrementally. This bound is for the explicit bounded integers, not arbitrary-precision CRT.

Example input and output

Read k≥0 then k pairs remainder modulus, |remainder|≤10^18 and 1≤modulus≤10^12. Print smallest nonnegative combined residue and period, NO SOLUTION, or LIMIT EXCEEDED when a merged period exceeds 10^12.

Input

2
2 6
8 9

Output

8 18

8 has remainders 2 modulo 6 and 8 modulo 9; every solution differs by lcm(6,9)=18.

Practical applications

Use for reconstructing periodic positions, combined modular conditions and multi-modulus arithmetic. Pairwise-coprime direct formulas are simpler when their assumptions and products fit. Generalized merging handles shared factors. Huge exact periods require a big-integer representation or another problem-specific strategy.

Check your understanding

When can x≡R (mod M) and x≡r (mod m) be merged?

Put it into practice

Test compatible, incompatible, modulus-one and period-limit cases.