# Linear Diophantine equation - Find all integer solutions

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.$

• What have you accomplished so far? What have you tried to do? The purpose of this forum is to help, not to solve entire (and very homework-looking) excercises. – masu Oct 14 '13 at 21:57
• You could start by dividing both sides by $11$ – Henry Oct 14 '13 at 21:58
• Numerically, $\large\left(21,19\right)\ \mbox{and}\ \left(72,8\right)$. I just check $\large\left(b\right)$. – Felix Marin Oct 14 '13 at 22:47

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.

• Thank you! Do you think the answer to (a) is an equation since there are infinite solutions? And for (b), will it just be the equation from (a), but with restrictions on x? – allie Oct 14 '13 at 22:41
• More like a closed form, like: $x = an + b$, where $a,b$ are some fixed integers. – Stefan4024 Oct 14 '13 at 22:42
• Will you check my edits? Should I have closed form for both x and y? – allie Oct 14 '13 at 22:53
• Obviously not true, because $y$ and $x$ must be integers. Pleas follow the video in the link that I've posted and it should be clear. – Stefan4024 Oct 14 '13 at 22:55
• Yes. Now they're OK. Now you can check in which interval for $n$ $x$ is positive and the same for $y$ and then find the intersection. And generate all positive integer solutions. – Stefan4024 Oct 15 '13 at 0:03

Dividing the equation by the gcd 11, you get 11x + 51y = 1200. The complete solution to this equation is x = 21 + 51n and y = 19 - 11n. This is equivalent to the solution above x = 16800 + 51n and -3600 - 11n. The only positive integer solutions are (21,19) and (72,8).