Linear Diophantine equations ax + by = c
ax + by = c has integer solutions exactly when d = gcd(a,b) divides c. Given that, the extended Euclidean algorithm supplies one solution, and every other is obtained by moving along the line: x = x₀ + (b/d)t and y = y₀ − (a/d)t. Stating that full parametrised family is what the question is really asking for.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Compute d = gcd(a,b) and test d ∣ cIf it fails there are no integer solutions — a complete answer.
- Find Bézout coefficientsExtended Euclidean gives au + bv = d. Scale by c/d to get a particular solution.
- Write the general solutionx = x₀ + (b/d)t, y = y₀ − (a/d)t for t ∈ ℤ. Note the signs are opposite.
- Apply extra constraints if askedFor non-negative solutions, solve the inequalities for t and count the admissible integers.
Worked example
Solve 6x + 9y = 21 over the integers.
- d = gcd(6,9) = 3, and 3 ∣ 21 ✓, so solutions exist.
- Bézout: 6(−1) + 9(1) = 3. Scale by 21/3 = 7: 6(−7) + 9(7) = 21.
- So (x₀, y₀) = (−7, 7).
- General: x = −7 + (9/3)t = −7 + 3t, y = 7 − (6/3)t = 7 − 2t.
Answer. x = −7 + 3t, y = 7 − 2t for any integer t. E.g. t = 3 gives (2, 1), and 12 + 9 = 21 ✓.
Where marks get dropped
These are the specific errors that cost credit on linear diophantine equations ax + by = c questions — QED's rubric penalises each of them separately.
- Giving one solution and stopping. The question almost always wants the full parametrised family.
- Using b and a instead of b/d and a/d in the parametrisation, which skips solutions when d > 1.
- Getting the signs the same way round. One coefficient is added and the other subtracted.
Practise this until it is automatic
Unlimited fresh questions
QED generates new linear diophantine equations ax + by = c problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.
Linear Diophantine equations ax + by = c — frequently asked questions
Why does d ∣ c decide solvability?
Because d divides ax + by for every x and y, so it must divide c. Conversely Bézout produces a solution when it does.
How do I find non-negative solutions?
Impose x ≥ 0 and y ≥ 0 on the parametrisation, giving two inequalities in t, and count the integers in the overlap.
What is the coin problem?
With coprime a and b, the largest amount NOT representable by non-negative combinations is ab − a − b — the Frobenius number.
The rest of Number Theory
Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Divisibility & the division algorithm
- 2Primes & unique factorisation
- 3gcd, lcm & the Euclidean algorithm
- 4Modular arithmetic & congruences
- 5Solving linear congruences
- 6Fermat’s little theorem
- 7The Chinese remainder theorem
- 8Modular inverses & fast exponentiation
- 9Euler’s totient φ(n) & Euler’s theorem
- 10Base-b representations & digit arguments
- 11RSA & modular exponentiation in cryptography
- 12Wilson’s theorem & primality testing
- 13Linear Diophantine equations ax + by = c
Ready to make linear diophantine equations ax + by = c exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →