[Math] Linear Diophantine equation – Find all integer solutions

diophantine equationsnumber theory

Using the linear Diphantine equation 

  121x + 561y = 13200

(a) Find all integer solutions to the equation.

(b) Find all positive integer solutions to the equation.

edit: The answer I have for (a) is an equation:

$x=16800 + 51n$

$y=-3600-11n$

where $n \in \mathbb Z. $

Best Answer

HINT:

First check if the greatest common divisor of 121 and 561 is a multiple of 13200. If so then this equation has a solution, otherwise it doesn't. Also it would be wise to divide by the greatest common divisor, so you'll work with smaller numbers.

And to obtain solutions apply the Euclidean Division Algorith. So you have:

$$561 = 4 \cdot 121 + 77$$ $$121 = 1 \cdot 77 + \cdots$$

Can you spot the pattern? Then going backwards you should be able to obtain one solution and quite easily a closed form of the solution. Then you can check when both solutions are positive.

Also I'm pretty sure there are a lot of nice books and video tutorials about solving a linear Diophantene equation on the internet. This one is quite simple and easy to follow.

Related Question