Linear Diophantine Equations
Pillar: Fix — "Fix that solutions must be integers. The divisibility condition on \(\gcd(a,b)\) either forces a solution to exist or proves none can."
The Setup
You have \(23\) cents. You have an unlimited supply of \(3\)-cent and \(5\)-cent coins. Can you make exactly \(23\) cents?
Written as an equation: find integers \(x\) and \(y\) such that \(3x + 5y = 23\), where \(x\) is the number of \(3\)-cent coins and \(y\) is the number of \(5\)-cent coins. Not real numbers — integers. That constraint changes everything. The line \(3x + 5y = 23\) contains infinitely many real points, but only a few of those points have integer coordinates. Finding those lattice points, counting them, and characterizing all of them — that's the problem.
This type of equation — \(ax + by = c\) where \(a\), \(b\), \(c\) are given integers and you need integer solutions — is called a linear Diophantine equation, named after Diophantus of Alexandria, who studied equations with integer constraints back in the 3rd century.
The tool you need is sitting in the previous lesson. Extended Euclidean gave you \(x_0, y_0\) satisfying \(ax_0 + by_0 = \gcd(a,b)\). Scale that, and you get a solution to \(ax + by = c\). But whether a solution exists at all depends on a single divisibility check.
When Do Solutions Exist?
The equation \(ax + by = c\) has integer solutions if and only if \(\gcd(a,b) \mid c\).
The reasoning is short and airtight. Let \(g = \gcd(a,b)\). Since \(g \mid a\) and \(g \mid b\), the left-hand side \(ax + by\) is a multiple of \(g\) for ANY integers \(x, y\). So if \(g \nmid c\), the left side can never equal \(c\). No solution exists. Period.
Going the other direction: if \(g \mid c\), then Extended Euclidean gives you integers \(x_0, y_0\) with \(ax_0 + by_0 = g\). Multiply both sides by \(c/g\) (an integer, since \(g \mid c\)), and you get \(a(x_0 \cdot c/g) + b(y_0 \cdot c/g) = c\). A concrete solution, constructed from Extended GCD output.
Three quick checks:
- \(6x + 10y = 15\). \(\gcd(6,10) = 2\). Does \(2 \mid 15\)? No. No solutions.
- \(6x + 10y = 14\). \(\gcd(6,10) = 2\). Does \(2 \mid 14\)? Yes. Solutions exist.
- \(3x + 5y = 23\). \(\gcd(3,5) = 1\). Does \(1 \mid 23\)? Always. Solutions exist. (When \(\gcd(a,b) = 1\), every value of \(c\) works.)
Finding One Solution
The recipe is three steps.
Step 1. Run Extended Euclidean on \(a\) and \(b\). Get \(x_0, y_0\) such that \(ax_0 + by_0 = g\) where \(g = \gcd(a,b)\).
Step 2. Check that \(g \mid c\). If not, return "no solution."
Step 3. Scale: set \(x = x_0 \cdot (c/g)\) and \(y = y_0 \cdot (c/g)\).
That's it. The result satisfies \(ax + by = c\) because:
All Solutions: The Parametric Family
One solution isn't enough. You typically need all of them — or at least a description compact enough to count or search through.
Suppose \((x_p, y_p)\) is one particular solution to \(ax + by = c\). Then every solution has the form:
for any integer \(t\), where \(g = \gcd(a,b)\).
Why this works. Plug it in:
The \(\frac{ab}{g} t\) terms cancel perfectly. So for every integer \(t\), the pair \((x, y)\) is a valid solution.
Why these are ALL the solutions. Suppose \((x', y')\) is any solution. Then \(ax' + by' = c = ax_p + by_p\), so \(a(x' - x_p) = -b(y' - y_p)\). Dividing both sides by \(g\): \(\frac{a}{g}(x' - x_p) = -\frac{b}{g}(y' - y_p)\). Since \(\gcd(a/g, b/g) = 1\), the number \(b/g\) must divide \(x' - x_p\). So \(x' - x_p = (b/g) \cdot t\) for some integer \(t\), and then \(y' - y_p = -(a/g) \cdot t\). Every solution fits the parametric form. Nothing is missed.
The parameter \(t\) indexes an infinite family of solutions on a lattice. Increasing \(t\) by \(1\) shifts \(x\) by \(+b/g\) and \(y\) by \(-a/g\). You're walking along the line \(ax + by = c\), hopping from one lattice point to the next.
Worked Example: \(3x + 5y = 23\)
This is the centerpiece. Trace every step.
Step 1: Check Existence
\(\gcd(3, 5) = 1\), and \(1 \mid 23\). Solutions exist.
Step 2: Extended GCD
Find \(x_0, y_0\) such that \(3x_0 + 5y_0 = 1\).
Run the Extended Euclidean algorithm:
| \(a\) | \(b\) | \(q = \lfloor a/b \rfloor\) | \(r = a - qb\) |
|---|---|---|---|
| \(3\) | \(5\) | \(0\) | \(3\) |
| \(5\) | \(3\) | \(1\) | \(2\) |
| \(3\) | \(2\) | \(1\) | \(1\) |
| \(2\) | \(1\) | \(2\) | \(0\) |
Back-substitution:
So \(x_0 = 2\), \(y_0 = -1\). Verify: \(3(2) + 5(-1) = 6 - 5 = 1\). Correct.
Step 3: Scale by \(c/g = 23/1 = 23\)
Verify: \(3(46) + 5(-23) = 138 - 115 = 23\). Correct.
Step 4: Write the General Solution
With \(g = 1\), \(b/g = 5\), \(a/g = 3\):
for any integer \(t\).
Step 5: Find Non-Negative Solutions
For a coin problem, you need \(x \geq 0\) and \(y \geq 0\).
From \(x \geq 0\): \(46 + 5t \geq 0 \Rightarrow t \geq -46/5 = -9.2\). So \(t \geq -9\).
From \(y \geq 0\): \(-23 - 3t \geq 0 \Rightarrow t \leq -23/3 = -7.67\). So \(t \leq -8\).
Combining: \(t \in \{-9, -8\}\). Two solutions.
| \(t\) | \(x = 46 + 5t\) | \(y = -23 - 3t\) | Check: \(3x + 5y\) |
|---|---|---|---|
| \(-9\) | \(46 + 5(-9) = 1\) | \(-23 - 3(-9) = 4\) | \(3(1) + 5(4) = 23\) |
| \(-8\) | \(46 + 5(-8) = 6\) | \(-23 - 3(-8) = 1\) | \(3(6) + 5(1) = 23\) |
Both check out. You can pay \(23\) cents with either one \(3\)-cent and four \(5\)-cent coins, or six \(3\)-cent and one \(5\)-cent coin. No other non-negative combinations exist.
Counting Solutions in a Range
The worked example found non-negative solutions by hand. The general task: given \(ax + by = c\) and bounds \(x \in [x_{lo}, x_{hi}]\), how many valid integer pairs \((x, y)\) exist?
From the parametric form \(x = x_p + (b/g) \cdot t\), solve for \(t\):
For \(x\) to range over \([x_{lo}, x_{hi}]\), the parameter \(t\) must range over:
The number of integers in that interval is the answer. But watch the details:
- If \(b/g > 0\), the direction of the inequalities is preserved. Take \(t_{lo} = \lceil (x_{lo} - x_p) / (b/g) \rceil\) and \(t_{hi} = \lfloor (x_{hi} - x_p) / (b/g) \rfloor\).
- If \(b/g < 0\), the direction flips. Take \(t_{lo} = \lceil (x_{hi} - x_p) / (b/g) \rceil\) and \(t_{hi} = \lfloor (x_{lo} - x_p) / (b/g) \rfloor\).
The count is \(\max(0, t_{hi} - t_{lo} + 1)\).
The trap here is ceiling and floor with negative numbers. In C++, integer division truncates toward zero, not toward negative infinity. So \(-7 / 3 = -2\) in C++, but \(\lfloor -7/3 \rfloor = -3\). You need a correct floor-division function:
long long floorDiv(long long numerator, long long denominator) {
return numerator / denominator - (numerator % denominator != 0 && (numerator ^ denominator) < 0);
}
long long ceilDiv(long long numerator, long long denominator) {
return numerator / denominator + (numerator % denominator != 0 && (numerator ^ denominator) >= 0);
}
These handle all sign combinations correctly. The XOR trick checks whether the numerator and denominator have different signs (meaning the true quotient is negative, and C++ truncation goes the wrong way).
Two Variables to One Variable
There's a slick reduction. Fix \(x\) in \(ax + by = c\), and then \(y = (c - ax)/b\). This \(y\) is an integer exactly when \(b \mid (c - ax)\), which means:
So finding integer solutions to the Diophantine equation is the same as solving a modular equation. This is the bridge to Ch4's modular arithmetic. The two viewpoints — "find lattice points on a line" and "solve a congruence" — are the same problem in different clothes.
Extension to Three or More Variables
The equation \(ax + by + cz = d\) with three unknowns reduces to two steps:
Step 1. Let \(g_1 = \gcd(a, b)\). Use Extended Euclidean to express \(g_1 = ax' + by'\).
Step 2. Now solve \(g_1 \cdot w + cz = d\) as a standard two-variable Diophantine equation. This has solutions iff \(\gcd(g_1, c) \mid d\), i.e., \(\gcd(a, b, c) \mid d\).
Step 3. Once you have \(w\) and \(z\), expand \(w\) back: \(x = w \cdot x'\), \(y = w \cdot y'\), and add the parametric freedom from both steps.
The same telescoping works for any number of variables. Each new variable adds one more layer of Extended GCD.
Applications
Smallest non-negative \(x\). From the parametric form \(x = x_p + (b/g) \cdot t\), the smallest \(x \geq 0\) corresponds to the smallest valid \(t\): \(t = \lceil -x_p / (b/g) \rceil\) (adjusting for sign of \(b/g\)). One formula, no search.
Minimum \(|x| + |y|\). The sum \(|x_p + (b/g)t| + |y_p - (a/g)t|\) is piecewise linear in \(t\). The minimum occurs near \(t\) where the two terms balance. Check a constant number of candidates around that point. This shows up in problems asking for the "cheapest" solution.
Coin problems. Can you pay exactly \(c\) cents using coins of value \(a\) and \(b\)? That's \(ax + by = c\) with \(x, y \geq 0\). The Chicken McNugget theorem (Frobenius) says: when \(\gcd(a,b) = 1\), the largest value that CANNOT be represented is \(ab - a - b\). Every integer \(\geq ab - a - b + 1\) can be represented. For \(3\)-cent and \(5\)-cent coins, that threshold is \(3 \cdot 5 - 3 - 5 = 7\), so every amount \(\geq 8\) is payable.
The Code
Solve a Linear Diophantine Equation
Using the extendedGCD function from Ch3 L3:
bool solveDiophantine(long long first, long long second, long long target,
long long &solX, long long &solY) {
if (first == 0 && second == 0) return target == 0;
long long divisor = extendedGCD(abs(first), abs(second), solX, solY);
if (target % divisor != 0) return false;
solX *= target / divisor;
solY *= target / divisor;
if (first < 0) solX = -solX;
if (second < 0) solY = -solY;
return true;
}
The function returns true if a solution exists, and sets solX, solY to one particular solution. It handles negative coefficients by running Extended GCD on absolute values and flipping signs afterward.
Count Solutions with \(x\) in a Range
long long floorDiv(long long numerator, long long denominator) {
return numerator / denominator - (numerator % denominator != 0 && (numerator ^ denominator) < 0);
}
long long ceilDiv(long long numerator, long long denominator) {
return numerator / denominator + (numerator % denominator != 0 && (numerator ^ denominator) >= 0);
}
long long countSolutionsInRange(long long first, long long second, long long target,
long long xLow, long long xHigh) {
long long solX, solY;
long long divisor = extendedGCD(abs(first), abs(second), solX, solY);
if (target % divisor != 0) return 0;
solX *= target / divisor;
if (first < 0) solX = -solX;
long long stepSize = second / divisor;
if (stepSize < 0) stepSize = -stepSize;
if (stepSize == 0) {
return (solX >= xLow && solX <= xHigh) ? 1 : 0;
}
long long tLow = ceilDiv(xLow - solX, stepSize);
long long tHigh = floorDiv(xHigh - solX, stepSize);
return max(0LL, tHigh - tLow + 1);
}
\(O(\log(\min(a,b)))\) time for both functions — dominated by the Extended GCD call. \(O(1)\) space.
The stepSize is always positive (we take the absolute value). This simplifies the ceiling/floor logic since we always divide by a positive number. The key invariant: \(x = \text{solX} + \text{stepSize} \cdot t\), so the valid \(t\) range maps directly to the valid \(x\) range.
Common Mistakes
-
Forgetting the \(\gcd(a,b) \mid c\) check. If you skip it and go straight to scaling, you compute \(c/g\) with a non-zero remainder, silently producing a wrong "solution." Always check divisibility first.
-
Integer overflow when scaling. If \(x_0\) is around \(10^9\) and \(c/g\) is around \(10^9\), then \(x_0 \cdot (c/g)\) overflows
long long(which holds up to about \(9.2 \times 10^{18}\)). In the worst case, Extended GCD on inputs up to \(10^{18}\) can return coefficients near \(10^{18}\), and scaling by \(c/g\) near \(10^{18}\) causes overflow. Use__int128for intermediate products when inputs are large, or reduce the particular solution modulo \(b/g\) before scaling. -
Floor/ceiling errors when counting \(t\) values. C++ truncates integer division toward zero. For negative dividends, this gives the wrong ceiling or floor. Use the
floorDiv/ceilDivhelpers above, or switch to floating-pointceil()/floor()with care for precision near exact integer boundaries. -
Ignoring the sign of \(b/g\) in the step. If \(b/g\) is negative, increasing \(t\) decreases \(x\) instead of increasing it. Taking the absolute value of the step size (as in the code above) avoids this confusion entirely.
Quick Recap
- \(ax + by = c\) has integer solutions iff \(\gcd(a,b) \mid c\). The left side is always a multiple of \(\gcd(a,b)\), so \(c\) must be too.
- One solution comes from scaling Extended GCD output: \(x_p = x_0 \cdot c/g\), \(y_p = y_0 \cdot c/g\).
- All solutions form a parametric family: \(x = x_p + (b/g)t\), \(y = y_p - (a/g)t\) for integer \(t\).
- Counting solutions in a range reduces to counting integers in an interval for \(t\) — one ceiling, one floor, subtract.
- The connection to modular arithmetic: \(ax + by = c\) is equivalent to \(ax \equiv c \pmod{b}\).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| SPOJ — Crucial Equation | spoj.com/problems/CEQU | Easy | Existence check: does \(\gcd(a,b) \mid c\)? |
| LC 365 — Water and Jug Problem | leetcode.com/problems/water-and-jug-problem | Medium | Classic Diophantine: can you measure exactly \(z\) liters with jugs of \(x\) and \(y\)? |
| CF 633A — Ebony and Ivory | codeforces.com/problemset/problem/633/A | Medium | Find non-negative solutions to \(ax + by = c\) |
Next chapter: Modular Arithmetic — where the Diophantine viewpoint meets congruences, and solving \(ax \equiv c \pmod{m}\) becomes a one-liner.