ii. Linear Congruences and CRT

Everything here is extended Euclid (GCD and Extended Euclid) plus careful division. Modular inverses: $a^{- 1} mod m$ exists iff $g cd (a, m) = 1$ (invMod); for primes and batch inverses see Modular Arithmetic.

Linear congruences and the CRT

$a x \equiv b (mod m)$ is solvable iff $g = g cd (a, m)$ divides $b$ , and then the solutions form one class modulo $m / g$ (that is, $g$ classes modulo $m$ — forgetting there are $g$ of them, not one, is the usual mistake when a problem asks for a count or the smallest positive solution). A system $x \equiv r_{i} (mod m_{i})$ is solvable iff $r_{i} \equiv r_{j} (mod g cd (m_{i}, m_{j}))$ for all pairs, and the solution is unique modulo $lcm (m_{i})$ .

Related equation	Method
$a x + b y = c$ over $Z$	linear Diophantine, below
$x^{2} \equiv a (mod p)$	quadratic residues, Tonelli–Shanks (Modular Square Roots)
$a^{x} \equiv b (mod m)$	discrete logarithm (Primitive Roots and Discrete Log)
$x^{k} \equiv a (mod m)$	discrete root (same note)
$f (x) \equiv 0 (mod p^{k})$	solve mod $p$ , then Hensel lift (Modular Square Roots)

pair<ll, ll> linearCongruence(ll a, ll b, ll m) {          // {x0, step}: solutions x0 + k*step; {-1, -1} if none
    a = ((a % m) + m) % m; b = ((b % m) + m) % m;
    ll x, y, g = extgcd(a, m, x, y);
    if (b % g) return {-1, -1};
    ll md = m / g, x0 = (ll)((__int128)((x % md + md) % md) * (b / g) % md);
    return {x0, md};
}
pair<ll, ll> crtMerge(ll r1, ll m1, ll r2, ll m2) {        // x = r1 (m1), x = r2 (m2) -> {r, lcm}; {-1, -1} if inconsistent
    ll p, q, g = extgcd(m1, m2, p, q);
    if ((r2 - r1) % g) return {-1, -1};
    ll l = m1 / g * m2;                                     // assumes lcm fits in ll
    ll t = (ll)((__int128)((r2 - r1) / g) * p % (m2 / g));
    ll r = (ll)(((__int128)m1 * t + r1) % l); if (r < 0) r += l;
    return {r, l};
}
pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) {
    pair<ll, ll> cur{0, 1};
    for (int i = 0; i < sz(r) && cur.second != -1; i++) cur = crtMerge(cur.first, cur.second, ((r[i] % m[i]) + m[i]) % m[i], m[i]);
    return cur;
}
ll garner(const vector<ll>& r, const vector<ll>& m, ll mod) {   // pairwise coprime m_i; x mod `mod` (x < prod m_i)
    int k = sz(r); vector<ll> M = m; M.push_back(mod);
    vector<ll> coef(k + 1, 1), cst(k + 1, 0);              // for each modulus: value of prod_{j<i} m_j and of the partial sum
    for (int i = 0; i < k; i++) {
        ll t = ((r[i] - cst[i]) % m[i] + m[i]) % m[i];
        t = (ll)((__int128)t * invMod(coef[i], m[i]) % m[i]);   // the i-th mixed-radix digit
        for (int j = i + 1; j <= k; j++) cst[j] = (ll)((cst[j] + (__int128)t * coef[j]) % M[j]), coef[j] = (ll)((__int128)coef[j] * m[i] % M[j]);
    }
    return cst[k];
}

Garner is the tool when the true value exceeds 64 bits but is wanted modulo something: combining NTTs over three primes into a result modulo $1 0^{9} + 7$ , or reconstructing big integers digit by digit.

Proof: congruences, CRT and Garner

Linear congruence: $a x \equiv b (mod m) ⟺ a x + m y = b$ for some $y$ , solvable iff $g ∣ b$ (Bézout). Dividing by $g$ gives $\frac{a}{g} x \equiv \frac{b}{g} (mod \frac{m}{g})$ with $g cd (\frac{a}{g}, \frac{m}{g}) = 1$ , so $x \equiv \frac{b}{g} (\frac{a}{g})^{- 1}$ is unique modulo $m / g$ ; the coefficient $x$ from extended Euclid on $(a, m)$ is that inverse modulo $m / g$ .

Merging two congruences: we need $r_{1} + m_{1} t \equiv r_{2} (mod m_{2})$ , i.e. $m_{1} t \equiv r_{2} - r_{1} (mod m_{2})$ , solvable iff $g ∣ r_{2} - r_{1}$ ; then $t \equiv \frac{r _{2} - r _{1}}{g} p (mod m_{2} / g)$ where $m_{1} p + m_{2} q = g$ . Two solutions differ by a common multiple of $m_{1}$ and $m_{2}$ , so the solution is unique modulo $lcm$ . Pairwise consistency suffices for a whole system by induction (the merged modulus is the lcm, and consistency with the next congruence reduces to the pairwise conditions prime by prime).

Garner: write $x = t_{0} + t_{1} m_{0} + t_{2} m_{0} m_{1} + \dots$ with $0 \leq t_{i} < m_{i}$ (mixed radix). Reducing modulo $m_{i}$ , the terms after $t_{i}$ vanish, so $t_{i} \equiv (r_{i} - \sum_{j < i} t_{j} \prod_{l < j} m_{l}) \cdot (\prod_{j < i} m_{j})^{- 1} (mod m_{i})$ , invertible by pairwise coprimality. The arrays cst[j], coef[j] hold the partial sum and the running product reduced modulo $M_{j}$ , which is all that is needed to compute later digits and the final value modulo mod. $O (k^{2})$ operations.

Linear Diophantine equations

$a x + b y = c$ has integer solutions iff $g = g cd (a, b) ∣ c$ ; from one solution $(x_{0}, y_{0})$ all are $x = x_{0} + k \frac{b}{g}$ , $y = y_{0} - k \frac{a}{g}$ . Constrained versions (count in a box, smallest non-negative $x$ , minimise $x + y$ ) intersect intervals of $k$ with exact floor / ceiling division: $x \geq 0 ⟺ k \geq ⌈ - x_{0} g / b ⌉$ (and symmetrically for $y \geq 0$ , or both at once by intersecting); since $x + y = (x_{0} + y_{0}) + k \frac{b - a}{g}$ is linear in $k$ , minimising $x + y$ over a feasible range of $k$ means pushing $k$ to whichever end of its interval the sign of $b - a$ favours and checking both endpoints.

Floor division with negatives

C++ truncates toward zero, so (-7) / 2 == -3, not $- 4$ . Use explicit floorDiv/ceilDiv helpers for every $k$ -range computation above — nearly every wrong answer in this topic traces back to plain / on a negative numerator.

bool diophantine(ll a, ll b, ll c, ll& x, ll& y, ll& g) {   // one solution of a x + b y = c (a, b not both 0)
    g = extgcd(a, b, x, y);                                // extgcd keeps signs: a x + b y = g
    if (c % g) return false;
    x = (ll)((__int128)x * (c / g)); y = (ll)((__int128)y * (c / g));
    return true;
}
ll countSolutions(ll a, ll b, ll c, ll xl, ll xr, ll yl, ll yr) {   // a, b != 0; x in [xl, xr], y in [yl, yr]
    ll x, y, g; if (!diophantine(a, b, c, x, y, g)) return 0;
    ll dx = b / g, dy = -a / g;                            // x + k dx, y + k dy
    auto range = [&](ll v, ll d, ll lo, ll hi, ll& kl, ll& kr) {   // lo <= v + k d <= hi
        if (d > 0) kl = ceilDiv(lo - v, d), kr = floorDiv(hi - v, d);
        else kl = ceilDiv(hi - v, d), kr = floorDiv(lo - v, d);
    };
    ll a1, b1, a2, b2; range(x, dx, xl, xr, a1, b1); range(y, dy, yl, yr, a2, b2);
    return max(0LL, min(b1, b2) - max(a1, a2) + 1);
}

Fact	Value
several variables	$\sum a_{i} x_{i} = c$ solvable iff $g cd (a_{i}) ∣ c$ ; solve by folding two coefficients into their gcd
Frobenius number of coprime $a, b$ (the Chicken McNugget theorem)	the largest non-representable $n \geq 0$ (with $x, y \geq 0$ ) is $ab - a - b$
non-representable count	exactly $\frac{( a - 1 ) ( b - 1 )}{2}$
non-negative solutions of $a x + b y = n$ ( $a, b$ coprime)	$⌊ n / ab ⌋$ or $⌊ n / ab ⌋ + 1$
many coins (Frobenius in general)	no closed form, and computing the Frobenius number is NP-hard — use shortest paths on residues modulo the smallest coin instead, which answers representability for targets up to $1 0^{18}$ (Shortest Path Techniques)

Proof: general solution, and the two-coin Frobenius facts

General solution: if $a x + b y = c = a x^{'} + b y^{'}$ then $a (x - x^{'}) = b (y^{'} - y)$ ; dividing by $g$ , $\frac{a}{g}$ and $\frac{b}{g}$ are coprime, so $\frac{b}{g} ∣ x - x^{'}$ by Euclid’s lemma, giving the parametrisation; conversely every member solves the equation. Counting: each constraint confines $k$ to an interval whose ends are exact floor/ceiling quotients (the direction flips when the step is negative); the answer is the length of the intersection.

Frobenius: for coprime $a, b$ , every $n$ has a unique representation $n = a x + b y$ with $0 \leq x < b$ (choose $x \equiv n a^{- 1} (mod b)$ ). $n$ is representable with non-negative coefficients iff that $y \geq 0$ . The largest $n$ with $y = - 1$ is $a (b - 1) - b = ab - a - b$ , and every larger $n$ has $y \geq 0$ . Count: the map $n \mapsto ab - a - b - n$ sends representable numbers in $[0, ab - a - b]$ to non-representable ones and vice versa (if both $n$ and $ab - a - b - n$ were representable, so would be their sum $ab - a - b$ ; if neither, the representations with $0 \leq x < b$ have $y = - y_{1}$ and $y = - y_{2}$ with $y_{1}, y_{2} \geq 1$ , and adding gives $ab - a - b = a (x_{1} + x_{2}) - b (y_{1} + y_{2})$ with $0 \leq x_{1} + x_{2} < 2 b$ , forcing $x_{1} + x_{2} = b - 1$ and $y_{1} + y_{2} = 1$ , impossible). So exactly half of the $(a - 1) (b - 1)$ numbers in that range are non-representable. Number of representations: with $0 \leq x < b$ fixed by the residue, the others are $x + k b, y - k a$ ; the count of $k \geq 0$ with $y - k a \geq 0$ is $⌊ y / a ⌋ + 1$ when $y \geq 0$ , which is $⌊ n / ab ⌋$ or one more.

Where these show up

Problem framing	Reduces to
jug pouring / measuring, “can I make exactly $c$ with steps of $a$ and $b$ ?”	$a x + b y = c$ , non-negative for the measuring version
modular division $b / a mod m$	$a x \equiv b (mod m)$ , i.e. $a x - m y = b$
lattice points on a line segment	$g cd (Δ x, Δ y) + 1$ points, from the same Bézout theory
two events repeating every $m_{1}, m_{2}$ steps, when do they coincide	CRT, which itself reduces to a Diophantine equation
scheduling / cyclic constraints with two step sizes	count solutions of $a x + b y = c$ in a range

whoashish's cp notes

Directory

ii. Linear Congruences and CRT

Linear congruences and the CRT

Linear Diophantine equations

Where these show up

Graph View

Table of Contents