HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Diophantine Equations and Pythagorean Triples
  1. 1Linear Diophantine equations
  2. 2Pythagorean triples
  3. 3Factoring, bounding and Pell's equation
  1. Mathematics
  2. /Diophantine Equations and Pythagorean Triples
  3. /Linear Diophantine equations

Course 28.3·Lesson 1 of 3

Linear Diophantine equations

A linear Diophantine equation ax+by=cax + by = cax+by=c has integer solutions exactly when d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b)

Lesson 1 of 3Show all lessonsHide
Diophantine Equations and Pythagorean Triples
  1. 1Linear Diophantine equations
  2. 2Pythagorean triples
  3. 3Factoring, bounding and Pell's equation

Try the code and the simulations beside the lesson.

What you will be able to do

  • decide whether ax+by=cax + by = cax+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 333 units and 555 units and gives no change. Can you pay 777? Can you pay 888? Can you pay 474747?

8=3+58 = 3 + 58=3+5 works. 777 does not: one coin of 555 leaves 222, and no 555 leaves 777, which is not a multiple of 333. For 474747 we need whole numbers x,y≥0x, y \ge 0x,y≥0 with 3x+5y=473x + 5y = 473x+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=cax + by = cax+by=c has a solution in integers exactly when d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b) divides ccc.

  • If d∤cd \nmid cd∤c: ddd divides ax+byax + byax+by for every choice of x,yx, yx,y, so it cannot equal ccc.
  • If d∣cd \mid cd∣c: Bezout's identity gives as+bt=das + bt = das+bt=d. Multiply by cd\dfrac{c}{d}dc​ to get one solution.

So 6x+9y=206x + 9y = 206x+9y=20 has no integer solution at all, because 3∤203 \nmid 203∤20.

All the solutions

Suppose (x0,y0)(x_0, y_0)(x0​,y0​) is one solution. If (x,y)(x, y)(x,y) is another, then a(x−x0)=−b(y−y0)a(x - x_0) = -b(y - y_0)a(x−x0​)=−b(y−y0​). Divide by ddd: ad(x−x0)=−bd(y−y0)\dfrac{a}{d}(x - x_0) = -\dfrac{b}{d}(y - y_0)da​(x−x0​)=−db​(y−y0​). The numbers ad\dfrac{a}{d}da​ and bd\dfrac{b}{d}db​ share no factor, so bd\dfrac{b}{d}db​ divides x−x0x - x_0x−x0​. This gives

x=x0+bd t,y=y0−ad t,t∈Z.\displaystyle x = x_0 + \dfrac{b}{d}\,t, \qquad y = y_0 - \dfrac{a}{d}\,t, \qquad t \in \mathbb{Z}.x=x0​+db​t,y=y0​−da​t,t∈Z.

Each step in ttt moves bd\dfrac{b}{d}db​ across and ad\dfrac{a}{d}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.

A worked example

Find all positive solutions of 11x+7y=19011x + 7y = 19011x+7y=190.

  1. Euclid. 11=7+411 = 7 + 411=7+4, 7=4+37 = 4 + 37=4+3, 4=3+14 = 3 + 14=3+1. Back: 1=4−3=2×4−7=2×11−3×71 = 4 - 3 = 2 \times 4 - 7 = 2 \times 11 - 3 \times 71=4−3=2×4−7=2×11−3×7.
  2. One solution. Multiply by 190190190: 11×380+7×(−570)=19011 \times 380 + 7 \times (-570) = 19011×380+7×(−570)=190. So x0=380x_0 = 380x0​=380, y0=−570y_0 = -570y0​=−570.
  3. All solutions. x=380+7tx = 380 + 7tx=380+7t, y=−570−11ty = -570 - 11ty=−570−11t.
  4. Positive. x>0x > 0x>0 needs t>−3807≈−54.3t > -\tfrac{380}{7} \approx -54.3t>−7380​≈−54.3, so t≥−54t \ge -54t≥−54. y>0y > 0y>0 needs t<−57011≈−51.8t < -\tfrac{570}{11} \approx -51.8t<−11570​≈−51.8, so t≤−52t \le -52t≤−52.
  5. List. t=−54,−53,−52t = -54, -53, -52t=−54,−53,−52 give (2,24)(2, 24)(2,24), (9,13)(9, 13)(9,13) and (16,2)(16, 2)(16,2).

Check. 11×9+7×13=99+91=19011 \times 9 + 7 \times 13 = 99 + 91 = 19011×9+7×13=99+91=190. There are 333 positive solutions.

The coin problem

Let aaa and bbb be coprime. Which numbers nnn can be written as ax+byax + byax+by with x,y≥0x, y \ge 0x,y≥0?

The answer. Every n>ab−a−bn > ab - a - bn>ab−a−b can, and ab−a−bab - a - bab−a−b itself cannot. Exactly (a−1)(b−1)2\dfrac{(a - 1)(b - 1)}{2}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 333 and 555: the largest amount you cannot pay is 15−3−5=715 - 3 - 5 = 715−3−5=7, and the amounts you cannot pay are 1,2,4,71, 2, 4, 71,2,4,7, which is 2×42=4\tfrac{2 \times 4}{2} = 422×4​=4 amounts.

Why ab−a−bab - a - bab−a−b fails. Suppose ax+by=ab−a−bax + by = ab - a - bax+by=ab−a−b with x,y≥0x, y \ge 0x,y≥0. Then a(x+1)+b(y+1)=aba(x + 1) + b(y + 1) = aba(x+1)+b(y+1)=ab. So a∣b(y+1)a \mid b(y + 1)a∣b(y+1), hence a∣y+1a \mid y + 1a∣y+1, and similarly b∣x+1b \mid x + 1b∣x+1. Then a(x+1)+b(y+1)≥ab+aba(x + 1) + b(y + 1) \ge ab + aba(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=19011x + 7y = 19011x+7y=190 from the extended Euclidean algorithm, moves it to the smallest xxx and lists the positive solutions.

Read it first. Then run it. Do you get the three solutions of the worked example?

1. Change the equation to a, b, c = 3, 5, 47. How many positive solutions does the ticket machine allow?

2. Change it to a, b, c = 6, 9, 20. What does the program print, and why?

Common mistakes

  • Forgetting the gcd test. Check gcd⁡(a,b)∣c\gcd(a, b) \mid cgcd(a,b)∣c before you look for a solution.
  • Steps of bbb and aaa when the gcd is not 111. The steps are bd\dfrac{b}{d}db​ and ad\dfrac{a}{d}da​.
  • Mixing positive and non-negative. "Positive" excludes 000. Read the question.
  • Using ab−a−bab - a - bab−a−b for coins that share a factor. With coins of 444 and 666, every odd amount is impossible.

Remember these

  • ax+by=cax + by = cax+by=c is solvable exactly when gcd⁡(a,b)∣c\gcd(a, b) \mid cgcd(a,b)∣c.
  • All solutions: x=x0+bdtx = x_0 + \frac{b}{d}tx=x0​+db​t, y=y0−adty = y_0 - \frac{a}{d}ty=y0​−da​t.
  • Turn "positive" into two inequalities for ttt.
  • Coprime a,ba, ba,b: largest non-representable number ab−a−bab - a - bab−a−b; there are (a−1)(b−1)2\frac{(a-1)(b-1)}{2}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.

  1. Does 15x+21y=4015x + 21y = 4015x+21y=40 have integer solutions?
  1. One solution of 4x+7y=14x + 7y = 14x+7y=1 is x=2x = 2x=2, y=−1y = -1y=−1. Write all solutions.
  1. How many ways can you pay 474747 units with coins of 333 and 555, using any number of each, zero allowed?
  1. What is the largest amount that cannot be paid with coins of 444 and 777?
  1. Why can no amount of 131313 units be paid with coins of 444 and 666?

References

  • David M. Burton, Elementary Number Theory, Chapter 2, section on the Diophantine equation ax+by=cax + by = cax+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.
No payment. You can leave at any time.

Problems (3)

A vending machine takes tokens worth 7 units and 11 units and gives no change…Hard · High School (11–12) · by StemPy Lab
Stamps come in values of 5 units and 8 units…Advanced · High School (11–12) · by StemPy Lab
A gardener spends exactly 345 units on plants: shrubs at 13 units each and herbs at 8 units each…Hard · High School (11–12) · by StemPy Lab
Next: lesson 2Pythagorean triples
← Diophantine Equations and Pythagorean Triples
← PreviousPythagorean triples →

Discussion (0)

Log in to join the discussion.

Loading…

divides
ccc
. One solution comes from the extended Euclidean algorithm, and then all solutions are
x=x0+bdtx = x_0 + \frac{b}{d}tx=x0​+db​t
,
y=y0−adty = y_0 - \frac{a}{d}ty=y0​−da​t
. Bounds on
ttt
count the positive solutions. For coprime
aaa
and
bbb
, the largest number that is not
ax+byax + byax+by
with
x,y≥0x, y \ge 0x,y≥0
is
ab−a−bab - a - bab−a−b
.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Python Labs (1)

Every solution of a linear equationPython Lab · by StemPy Lab