A linear Diophantine equation asks for integers, not just real numbers. We compare the theory with 18x + 12y = 72, from Euclid’s algorithm to every solution. We do not hunt for a lucky pair by trial and error: we construct a complete procedure, then impose any constraints required by the problem.
Open the laboratory: enter a, b and c and follow every step
1. The starting equation
| Theory | Worked example |
|---|---|
The form is ax + by = c, with a, b, c ∈ ℤ. We seek x, y ∈ ℤ. | 18x + 12y = 72 |
For the main procedure assume a, b ≠ 0. Zero coefficients are covered at the end. | a = 18, b = 12, c = 72 |
2. Finding the greatest common divisor
Use Euclid’s algorithm: each division produces a remainder smaller than the divisor.
| Theory | Worked example |
|---|---|
Calculate d = GCD(|a|,|b|) by successive divisions. | 18 = 12×1 + 6 |
| Divide the previous divisor by the remainder until the remainder is zero. | 12 = 6×2 + 0 |
| The last nonzero remainder is the GCD, taken positive. | d = 6 |
3. Checking whether solutions exist
| Theory | Worked example |
|---|---|
Integer solutions exist if and only if d ∣ c: the GCD divides the right-hand side. | 6 ∣ 72 |
If the GCD does not divide c, no integer pair exists. Otherwise, continue. | 72/6 = 12 |
Why is this necessary? Every ax + by is a multiple of the GCD. Why is it sufficient? Bézout’s identity, constructed next, produces a solution whenever c/d is an integer.
4. Extended Euclid and Bézout’s identity
Working backwards through the divisions means rewriting the remainders as combinations of the original coefficients.
| Theory | Worked example |
|---|---|
| Isolate the last nonzero remainder and substitute earlier remainders backwards where needed. | 6 = 18 - 12 |
Obtain integers u, v with au + bv = d: this is Bézout’s identity. | 18(1) + 12(-1) = 6 |
The coefficients in that combination are u and v. | u = 1, v = -1 |
5. Finding a particular solution
Turn Bézout’s identity into the original equation by multiplying throughout by the same number.
| Theory | Worked example |
|---|---|
Start from au + bv = d. | 18(1) + 12(-1) = 6 |
The multiplier is m = c/d. | 72/6 = 12 |
Multiply the entire identity: a(um) + b(vm) = c. | 18(12) + 12(-12) = 72 |
Thus x₀ = u(c/d) and y₀ = v(c/d). | x₀ = 12, y₀ = -12 |
The pair (12,-12) is correct even though one coordinate is negative: for now we seek solutions in ℤ. Non-negativity is an additional requirement.
6. Proving the general formula
| Theory | Worked example |
|---|---|
| Write the original equation. | 18x + 12y = 72 |
| Write the equation satisfied by the particular solution. | 18(12) + 12(-12) = 72 |
| Subtract the equations side by side. | 18(x - 12) + 12(y + 12) = 0 |
| Move the second term to the right-hand side. | 18(x - 12) = -12(y + 12) |
Divide both sides by d. | 3(x - 12) = -2(y + 12) |
Set a′ = a/d and b′ = b/d. These numbers are coprime. From a′(x - x₀) = -b′(y - y₀), Euclid’s lemma gives b′ ∣ (x - x₀).
Therefore some integer k satisfies x - x₀ = b′k. Substitution and cancellation give y - y₀ = -a′k.
x = x₀ + (b/d)ky = y₀ - (a/d)kk ∈ ℤ
We have proved that every solution has this form. Conversely, substituting into the equation cancels the terms involving k: every integer k yields a solution. None are missing.
7. Applying the general formula
| Theory | Worked example |
|---|---|
First coordinate: x = x₀ + (b/d)k. | x = 12 + (12/6)k |
Second coordinate: y = y₀ - (a/d)k. | y = -12 - (18/6)k |
Simplify and remember that k may be any integer. | x = 12 + 2k; y = -12 - 3k; k ∈ ℤ |
The formulas describe infinitely many integer solutions, including negative coordinates. A different particular solution may give different-looking formulas, but they describe the same family after shifting the parameter.
8. Finding non-negative solutions
If the problem requires non-negative quantities, impose both conditions, not just one.
| Theory | Worked example |
|---|---|
Require x₀ + (b/d)k ≥ 0. | 12 + 2k ≥ 0 ⇒ k ≥ -6 |
Require y₀ - (a/d)k ≥ 0. | -12 - 3k ≥ 0 ⇒ k ≤ -4 |
Intersect the intervals and retain only integer values of k. | -6 ≤ k ≤ -4 |
In general a constraint has the form q + tk ≥ m, with m = 0 for non-negative quantities and m = 1 for strictly positive integer quantities.
- If
t > 0:k ≥ ⌈(m - q)/t⌉. - If
t < 0:k ≤ ⌊(m - q)/t⌋; dividing by a negative number reverses the inequality. - If
t = 0, directly check whetherq ≥ m.
⌈ ⌉ and ⌊ ⌋ mean rounding up and down respectively. An empty interval means no admissible solution; with opposite-sign coefficients the interval may be unbounded.
9. Calculating the solutions
In this example k ∈ {-6,-5,-4}. Substitute each value into both formulas.
| k | x = 12 + 2k | y = -12 - 3k |
|---|---|---|
| -6 | 0 | 6 |
| -5 | 2 | 3 |
| -4 | 4 | 0 |
The three non-negative solutions are (0,6), (2,3), (4,0). Check: 18×0 + 12×6 = 72, 18×2 + 12×3 = 72, 18×4 + 12×0 = 72.
If we require x ≥ 1 and y ≥ 1, only (2,3) remains. “Integer”, “non-negative” and “strictly positive” are three different requirements.
10. Summary of the method
| Stage | Theory | Worked example |
|---|---|---|
| Equation | ax + by = c | 18x + 12y = 72 |
| GCD | d = GCD(|a|,|b|) | d = 6 |
| Existence | d ∣ c | 6 ∣ 72 |
| Bézout | au + bv = d | 18 - 12 = 6 |
| Multiplier | m = c/d | m = 12 |
| Particular solution | x₀ = um, y₀ = vm | (12,-12) |
| General formula: x | x = x₀ + (b/d)k | x = 12 + 2k |
| General formula: y | y = y₀ - (a/d)k | y = -12 - 3k |
| Constraints | x, y ≥ 0 | -6 ≤ k ≤ -4 |
| Solutions | k ∈ ℤ | (0,6), (2,3), (4,0) |
11. Two distinct tasks, also with larger numbers
- Extended Euclid finds a particular solution without guessing.
- The general formula produces every other solution by varying integer
k.
For 252x + 198y = 900, the divisions are 252 = 198×1 + 54, 198 = 54×3 + 36, 54 = 36×1 + 18, 36 = 18×2 + 0. The GCD is 18.
Working backwards gives 18 = 4×252 - 5×198. Multiply by 900/18 = 50: a particular solution is (200,-250). The family is x = 200 + 11k, y = -250 - 14k.
Non-negativity requires k ≥ -18 and k ≤ -18. Thus k = -18 and the only non-negative pair is (2,2). Load this example in the laboratory to see every backwards substitution.
12. Impossible cases, signs and zero coefficients
No integer solution: 18x + 12y = 73 is impossible because 6 does not divide 73. No non-negative solution: 6x + 10y = 2 has family x = 2 + 5k, y = -1 - 3k, but simultaneously requires k ≥ 0 and k ≤ -1.
Negative coefficients: apply Euclid to absolute values. If |a|u′ + |b|v′ = d, restore the original signs in the Bézout coefficients to obtain au + bv = d. The general formula and constraints remain valid.
- If
a = 0andb ≠ 0,bmust dividec:y = c/bis fixed andxis free. - If
b = 0anda ≠ 0, similarlyx = c/ais fixed andyis free. - If
a = b = 0andc ≠ 0, no solution exists. Ifc = 0too, every integer pair is a solution:x = s,y = t, with two independent parameters.
The laboratory uses exact integer arithmetic without rounding coefficients. It accepts up to 80 digits for each of the three parameters and distinguishes the complete formulas from the table, which displays at most 25 solutions per page.