Inputs
Formula used
We use the extended Euclidean algorithm to find integers u, v with au + bv = gcd(a,b). If d is divisible by g = gcd(a,b), one solution to ax + by = d is x0 = u(d/g) and y0 = v(d/g). The general solution is x = x0 + (b/g)t, y = y0 − (a/g)t, where t is any integer.
How to use
- Enter integers for a, b, and the target d.
- Optionally set ranges for x, y, mod constraints, or non-negativity.
- Choose an objective to guide the recommended solution.
- Use
tbounds to scan specific solution windows. - Provide multiple targets in batch to compute several at once.
Results
Example data
| a | b | d | gcd | Solvable? | Example (x0,y0) |
|---|---|---|---|---|---|
| 56 | 72 | 8 | 8 | Yes | 4,-3 |
| 35 | 20 | 5 | 5 | Yes | -1,2 |
| 99 | 78 | 33 | 3 | Yes | -121,154 |
| 17 | 31 | 1 | 1 | Yes | 11,-6 |
Key identities & properties
- Solvable iff g = gcd(a,b) divides d.
- All solutions are x = x0 + (b/g)t, y = y0 − (a/g)t.
- Step sizes are b/g for x and a/g for y, always integers.
- Any solution pair preserves ax + by = d exactly for every integer t.
Effect of parameter t
| Quantity | Expression | Comment |
|---|---|---|
| x(t) | x0 + (b/g)t | Arithmetic progression step size b/g |
| y(t) | y0 − (a/g)t | Arithmetic progression step size a/g |
| |x| + |y| | varies with t | Search near t minimizing L1 norm |
| max(|x|,|y|) | varies with t | Balance x and y to reduce peak |
Residue classes of x and y
For any solution, the residues are fixed modulo the step sizes:
| Variable | Residue constraint | Explanation |
|---|---|---|
| x | x ≡ x0 (mod b/g) | Changing t shifts x by multiples of b/g |
| y | y ≡ y0 (mod a/g) | Changing t shifts y by multiples of a/g |
Small-number examples (auto)
| a | b | d | gcd | One (x0, y0) | x step | y step |
|---|---|---|---|---|---|---|
| 15 | 21 | 3 | 3 | 3,-2 | 7 | 5 |
| 14 | 35 | 7 | 7 | -2,1 | 5 | 2 |
| 27 | 10 | 1 | 1 | 3,-8 | 10 | 27 |
| 84 | 66 | 6 | 6 | 4,-5 | 11 | 14 |
| 12 | 18 | 6 | 6 | -1,1 | 3 | 2 |
FAQs
1) When does ax + by = d have solutions?
Exactly when gcd(a,b) divides d. If not, there is no integer solution. If yes, there are infinitely many solutions parametrized by an integer t.
2) Why are there infinitely many solutions?
If one pair (x0, y0) works, then adding (b/g)t to x and subtracting (a/g)t from y keeps ax + by unchanged. Different integer t values generate distinct solutions.
3) How do I get non‑negative solutions?
Enable x ≥ 0 and/or y ≥ 0 and set t bounds. The tool searches t within bounds and returns a feasible solution that satisfies your objective and non‑negativity requirements.
4) Can I force residue conditions on x or y?
Yes. Set x ≡ r (mod m) and y ≡ s (mod n). The scan over t accepts only solutions meeting the congruences, together with any range and non‑negativity constraints.
5) What if the calculator says “Not solvable”?
Then gcd(a,b) does not divide d. Adjust d to a multiple of gcd(a,b), or change a or b. Otherwise, no integer pair can satisfy the equation.
6) Do signs of a and b matter?
The algorithm works with any signs. Internally it runs on |a| and |b| and then corrects the Bézout coefficients’ signs so the final identity uses your original a and b.
7) How are “min |x|”, “min |y|”, or “min x²+y²” handled?
We try t values near an analytically suggested point and select the best under your constraints. Objectives guide which feasible solution is reported, without changing the full parametric solution family.