Intuition, Vocabulary and Foundations
A linear Diophantine equation asks for integer solutions to $ax+by=c$. Think of two package sizes: if items arrive only in boxes of $a$ and $b$, then $x$ and $y$ describe how many boxes of each type produce a target total $c$. Negative variables can model returns or credits; bounds such as $0\le x\le X$ turn the unrestricted equation into a practical allocation problem.
If $g=\gcd(a,b)$, every integer combination $ax+by$ is divisible by $g$. Bézout’s identity supplies integers $u,v$ satisfying $au+bv=g$. Therefore the equation has an integer solution exactly when $g\mid c$. Multiplying the identity by $c/g$ gives $x_0=u(c/g)$ and $y_0=v(c/g)$.
One solution generates every solution. With $s_x=b/g$ and $s_y=-a/g$, the complete family is $x=x_0+s_xt$ and $y=y_0+s_yt$ for $t\in\mathbb Z$. Bounds on $x$ and $y$ become integer intervals for $t$. A linear objective $px+qy$ becomes $(px_0+qy_0)+t(ps_x+qs_y)$, so its slope determines which feasible endpoint is optimal.
Once one solution is known, a two-variable Diophantine problem becomes a one-dimensional integer-interval problem. Correctness rests on $g\mid c$, the complete affine parameterization, and signed floor and ceiling operations that translate bounds without reversing inequalities incorrectly.
| Concept | Definition or invariant | Concrete example | Non-example or boundary | Question answered |
|---|---|---|---|---|
| Bézout coefficients | $au+bv=\gcd(a,b)$ | $15(3)+21(-2)=3$ | Coefficients are not generally unique | How is one constructive gcd identity obtained? |
| Solvability | $\gcd(a,b)\mid c$ | $15x+21y=84$ is solvable | $15x+21y=85$ has no integer solution | Does any integer solution exist? |
| Particular solution | One pair $(x_0,y_0)$ satisfying the equation | Scale Bézout coefficients by $c/g$ | A real solution need not be integral | Where does the affine family begin? |
| Homogeneous step | $(s_x,s_y)=(b/g,-a/g)$ | For $15x+21y=84$, the step is $(7,-5)$ | Using $(b,-a)$ skips solutions when $g\gt1$ | How do consecutive integer solutions differ? |
| Feasible interval | $t_{\min}\le t\le t_{\max}$ | Both variable bounds intersect in one interval | Intersecting real intervals without integer rounding | Which parameters satisfy all bounds? |
| Objective slope | $\Delta=ps_x+qs_y$ | If $\Delta\gt0$, choose the smallest $t$ | Enumerating every feasible solution | Which endpoint minimizes a linear cost? |
| Signed floor | $\lfloor n/d\rfloor$ for signed nonzero $d$ | $\lfloor-7/3\rfloor=-3$ | Truncation toward zero gives $-2$ | How is an upper bound rounded? |
| Signed ceiling | $\lceil n/d\rceil$ for signed nonzero $d$ | $\lceil-7/3\rceil=-2$ | A positive-only shortcut fails | How is a lower bound rounded? |
Step-by-Step Derivations and Algorithms
Extended Euclid maintains representations of consecutive remainders as combinations of the original inputs. Starting with $r_0=a$ and $r_1=b$, each division writes $r_{i-1}=q_ir_i+r_{i+1}$. Applying the same update to coefficient pairs preserves $r_i=ax_i+by_i$. When the remainder reaches zero, the preceding remainder is the gcd and its coefficients are Bézout coefficients.
If $g\mid c$, scale those coefficients to obtain $(x_0,y_0)$. To prove completeness, subtract the particular solution from any other solution: $a(x-x_0)+b(y-y_0)=0$. After division by $g$, coprimality of $a/g$ and $b/g$ forces $x-x_0$ to be a multiple of $b/g$, yielding the single integer parameter.
Each bound becomes $L\le z_0+st\le R$. For positive $s$, this gives $\lceil(L-z_0)/s\rceil\le t\le\lfloor(R-z_0)/s\rfloor$. For negative $s$, division reverses the inequalities, so the endpoints exchange roles. A zero step either contributes no restriction when $z_0$ is in bounds or proves infeasibility. Intersect the intervals from both variables; then choose an endpoint according to the objective slope.
flowchart TD
A["Input coefficients and bounds"] --> B["Compute g, u, v"]
B --> C{"Does g divide c?"}
C -->|No| D["No integer solution"]
C -->|Yes| E["Scale one solution"]
E --> F["Build affine step"]
F --> G["Convert x bounds to t"]
G --> H["Convert y bounds to t"]
H --> I{"Intersection nonempty?"}
I -->|No| J["No bounded solution"]
I -->|Yes| K["Count feasible parameters"]
K --> L{"Objective slope sign"}
L -->|Positive| M["Choose lower endpoint"]
L -->|Negative| N["Choose upper endpoint"]
L -->|Zero| O["Choose either endpoint"]
Extended Euclid preserves $r=ax+by$ at every iteration, and the affine shift preserves $ax+by=c$ because $a(b/g)+b(-a/g)=0$. The algorithm uses $O(\log\min(\lvert a\rvert,\lvert b\rvert))$ arithmetic iterations, followed by $O(1)$ interval intersections and objective evaluation, with $O(1)$ auxiliary storage.
Implementation, Complexity and Engineering
The reference implementation defines floor and ceiling division for any nonzero signed denominator, constructs the affine family, intersects variable bounds, counts feasible solutions, and minimizes a linear objective. It handles one zero coefficient naturally and rejects the special case $a=b=c=0$, whose two-dimensional solution set cannot be represented by one parameter.
In fixed-width languages, intermediate coefficients may overflow even when the final solution fits. Use a wider type or checked arithmetic for Bézout updates, scaling by $c/g$, interval endpoints, and objective evaluation.
| Implementation choice | Complexity | Numeric boundary | Failure mode | Mitigation |
|---|---|---|---|---|
| Iterative extended Euclid | $O(\log\min(\lvert a\rvert,\lvert b\rvert))$ divisions | Coefficients may approach input magnitude | Adjusting gcd sign but not coefficients | Verify $ax+by=g$ |
| Affine parameterization | $O(1)$ after gcd | Scaling by $c/g$ may overflow | Using $(b,-a)$ instead of reduced steps | Divide both steps by $g$ |
| Signed floor division | $O(1)$ | Minimum signed value divided by $-1$ may overflow | Truncation toward zero | Use a proven helper and checked arithmetic |
| Signed ceiling division | $O(1)$ | Negation may overflow in fixed-width code | Positive-only shortcut | Use quotient and remainder or a wider type |
| Bound intersection | $O(1)$ | Inclusive endpoints require exact rounding | Ignoring negative step direction | Branch on the step sign and test endpoints |
| Objective optimization | $O(1)$ | Objective products may overflow | Choosing from coefficient signs alone | Compute the parameter slope in a wider type |
| Brute-force oracle | Product of bounded widths | Practical only for small ranges | Using it as the production solver | Reserve it for differential tests |
| Degenerate coefficients | Problem-specific | Solution set can be two-dimensional | Dividing by $\gcd(0,0)$ | Handle zero coefficients explicitly |
Applications, Case Studies and Exercises
Bounded Diophantine equations model package selection, resource allocation, synchronization offsets, currency combinations, and integer production plans. Their unrestricted algebra is only the first half of the problem: bounds determine feasibility, and the objective slope determines which feasible endpoint is operationally best.
Apply Extended Euclid & Bounded Diophantine Solutions
Case study 1 — package planning. Solve $15x+21y=84$ with $0\le x\le20$ and $-10\le y\le10$. Compute one Bézout solution, derive the step $(7,-5)$, and intersect both parameter intervals. Checkpoint: compare the complete family with a bounded brute-force search. Success means every generated pair satisfies the equation and every oracle solution appears once.
Case study 2 — minimum-cost production. A service combines batches of sizes $144$ and $252$ to meet a net requirement $c$, with signed adjustments allowed inside contractual bounds. Given costs $p$ and $q$, solve $144x+252y=c$ and choose the feasible endpoint from the slope $p(252/g)-q(144/g)$. Reject targets not divisible by $g$, verify both endpoints, and compare small replicas with exhaustive search.
Hands-on signed-rounding exercise. Test every numerator from $-20$ through $20$ and every nonzero denominator from $-7$ through $7$. Verify the defining floor and ceiling inequalities, then solve randomly generated bounded equations and compare feasibility, count, and minimum objective with brute force. Success means exact agreement for at least one thousand seeded cases, including negative coefficients and bounds.
Tiered exercises. Recall: state the divisibility criterion. Derive: prove every solution differs by $(b/g,-a/g)t$. Implement: return the lexicographically smallest feasible pair. Debug: find a counterexample to a positive-only ceiling formula. Extend: minimize $\lvert px+qy-r\rvert$ by checking feasible parameters nearest its real breakpoint and both interval endpoints.
Use extended Euclid for one constructive solution, reduce all remaining freedom to the integer parameter $t$, intersect signed bounds with proven floor and ceiling helpers, and optimize from the resulting slope. Common failures are skipping the gcd test, omitting division by $g$ in the step, applying positive-only rounding formulas, and failing to verify the selected endpoint in the original equation.