Linear Diophantine Equations

Solve $ax+by=c$ over the integers.

Solvability

A solution exists iff $\gcd (a,b)\mid c$.

Why: every integer combination $ax+by$ is a multiple of $g=\gcd (a,b)$ (forward), and Bézout’s identity produces $ax+by=g$, which scales to any multiple of $g$ (converse).

Finding all solutions

1. Run extended Euclid to get $x_0,y_0$ with $a{x}_0+b{y}_0=g$.
2. Scale: $x_1=x_0\cdot (c/g)$, $y_1=y_0\cdot (c/g)$.
3. The general solution is
   $x=x_1+k\cdot \frac{b}{g},y=y_1-k\cdot \frac{a}{g},k\in \mathbb{Z}.$

// returns false if no solution; otherwise fills one solution and the step sizes
bool diophantine(long long a, long long b, long long c,
                 long long& x, long long& y, long long& g) {
    g = extgcd(llabs(a), llabs(b), x, y);
    if (c % g) return false;
    x *= c / g; y *= c / g;
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return true;                      // steps: x += b/g, y -= a/g
}

Constrained solutions

Most problems ask for solutions in a range, or for the count, or for an extremum. All follow from the parametrisation.

Solutions with $x\ge 0$:
$x_1+k\frac{b}{g}\ge 0⟹k\ge \lceil \frac{-x_{1}g}{b}\rceil .$

Both $x\ge 0$ and $y\ge 0$: intersect the two ranges of $k$; the number of integer $k$ in the intersection is the answer.

// count solutions with x in [xl, xr] and y in [yl, yr]
long long countSolutions(long long a, long long b, long long c,
                         long long xl, long long xr, long long yl, long long yr) {
    long long x, y, g;
    if (!diophantine(a, b, c, x, y, g)) return 0;
    long long dx = b / g, dy = a / g;
    // shift k so that x in [xl, xr] and y in [yl, yr]; intersect the two k-intervals
    // (compute k bounds with careful floor/ceil division)
    ...
}

Floor division with negatives

C++ truncates toward zero, so (-7) / 2 == -3, not $-4$. Write explicit helpers:

long long fdiv(long long a, long long b) { return a / b - ((a % b != 0) && ((a < 0) != (b < 0))); }
long long cdiv(long long a, long long b) { return a / b + ((a % b != 0) && ((a < 0) == (b < 0))); }

Nearly every wrong answer in this topic traces back to this.

Minimising $x+y$

Since $x+y=x_1+y_1+k\left(\frac{b-a}{g}\right)$, the sum is linear in $k$: push $k$ to whichever end of its feasible interval the sign of $(b-a)$ favours. Check both endpoints — the feasible $k$ range is an interval, so the extremes are the only candidates.

More variables

$a_1{x}_1+\cdots +a_n{x}_n=c$ has a solution iff $\gcd (a_1,\dots ,a_n)\mid c$. Solve iteratively: let $g_2=\gcd (a_1,a_2)$ and solve $g_{2}t+a_3{x}_3+\cdots =c$, then unwind $t$ into $x_1,x_2$.

Related: the Frobenius problem

“What is the largest $c$ not representable as a non-negative combination?”

• Two coprime coins $a,b$: the answer is $ab-a-b$ (the Chicken McNugget theorem), and exactly $\frac{(a-1)(b-1)}{2}$ values are unrepresentable.
• Three or more: no closed form; computing it is NP-hard in general. For small coin values, the “Dijkstra on residues” technique answers representability for targets up to $10^{18}$.

Where these appear

Problem	Equation
Jug pouring / measuring	$ax+by=c$
”Can I make exactly $c$ with steps of $a$ and $b$?“	with $x,y\ge 0$
Modular division	$ax\equiv b(\mathrm{mod}m)$ is $ax-my=b$
Lattice points on a line segment	$\gcd (\Delta x,\Delta y)+1$ points, from the same theory
Aligning two periodic events	CRT, which reduces to a Diophantine equation
Scheduling with two step sizes	count solutions in a range

See also: Extended Euclidean · Linear Congruence · Coin Change