A linear Diophantine equation ax+by=c has integer solutions exactly when d=gcd(a,b)
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
decide whether ax+by=c has integer solutions;
find one solution with the Euclidean algorithm and then write down all of them;
count the solutions in positive or non-negative integers;
find the largest amount that cannot be paid with two coin values.
Coins of two values
A ticket machine takes coins worth 3 units and 5 units and gives no change. Can you pay 7? Can you pay 8? Can you pay 47?
8=3+5 works. 7 does not: one coin of 5 leaves 2, and no 5 leaves 7, which is not a multiple of 3. For 47 we need whole numbers x,y≥0 with 3x+5y=47. An equation in which only integer answers count is called a Diophantine equation, after Diophantus of Alexandria.
When is there a solution?
The equation ax+by=c has a solution in integers exactly when d=gcd(a,b) divides c.
If d∤c:d divides ax+by for every choice of x,y, so it cannot equal c.
If d∣c: Bezout's identity gives as+bt=d. Multiply by dc to get one solution.
So 6x+9y=20 has no integer solution at all, because 3∤20.
All the solutions
Suppose (x0,y0) is one solution. If (x,y) is another, then a(x−x0)=−b(y−y0). Divide by d: da(x−x0)=−db(y−y0). The numbers da and db share no factor, so db divides x−x0. This gives
x=x0+dbt,y=y0−dat,t∈Z.
Each step in t moves db across and da down the line. These are the dots in the simulation.
The straight line 3x + 5y = 47 drawn for x from 0 to 16, falling from the point (0, 9.4) to the point (15.7, 0). Three red dots sit on the line at the whole-number points (4, 7), (9, 4) and (14, 1). Arrows between neighbouring dots are labelled 5 across and 3 down.
One solution. Multiply by 190: 11×380+7×(−570)=190. So x0=380, y0=−570.
All solutions.x=380+7t, y=−570−11t.
Positive.x>0 needs t>−7380≈−54.3, so t≥−54. y>0 needs t<−11570≈−51.8, so t≤−52.
List.t=−54,−53,−52 give (2,24), (9,13) and (16,2).
Check.11×9+7×13=99+91=190. There are 3 positive solutions.
The coin problem
Let a and b be coprime. Which numbers n can be written as ax+by with x,y≥0?
The answer. Every n>ab−a−b can, and ab−a−b itself cannot. Exactly 2(a−1)(b−1) positive numbers cannot. This is often called the Frobenius coin problem, and the largest number is the Frobenius number.
For coins of 3 and 5: the largest amount you cannot pay is 15−3−5=7, and the amounts you cannot pay are 1,2,4,7, which is 22×4=4 amounts.
Why ab−a−b fails. Suppose ax+by=ab−a−b with x,y≥0. Then a(x+1)+b(y+1)=ab. So a∣b(y+1), hence a∣y+1, and similarly b∣x+1. Then a(x+1)+b(y+1)≥ab+ab, which is too big.
Practise with new numbers
Try it in Python
The program finds one solution of 11x+7y=190 from the extended Euclidean algorithm, moves it to the smallest x and lists the positive solutions.
Common mistakes
Forgetting the gcd test. Check gcd(a,b)∣c before you look for a solution.
Steps of b and a when the gcd is not 1. The steps are db and da.
Mixing positive and non-negative. "Positive" excludes 0. Read the question.
Using ab−a−b for coins that share a factor. With coins of 4 and 6, every odd amount is impossible.
Remember these
ax+by=c is solvable exactly when gcd(a,b)∣c.
All solutions: x=x0+dbt, y=y0−dat.
Turn "positive" into two inequalities for t.
Coprime a,b: largest non-representable number ab−a−b; there are 2(a−1)(b−1) of them.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Does 15x+21y=40 have integer solutions?
One solution of 4x+7y=1 is x=2, y=−1. Write all solutions.
How many ways can you pay 47 units with coins of 3 and 5, using any number of each, zero allowed?
What is the largest amount that cannot be paid with coins of 4 and 7?
Why can no amount of 13 units be paid with coins of 4 and 6?
References
David M. Burton, Elementary Number Theory, Chapter 2, section on the Diophantine equation ax+by=c.
Enroll free in Diophantine Equations and Pythagorean Triples
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.