# Linear Diophantine Equations

I was asked to find

i) all integer solutions, and

ii) all non-negative integer solutions

to the equations below. I know (a) has no answers, but have no idea how to go about proving the rest. Please help.

(a) $943x + 533y = 100000$

(b) $1249x + 379y = 5$

(c) $663x + 494y = 130$

## 1 Answer

The equation $ax + by = n$ has integer solutions in $x, y$ if and only if the GCD of $a$ and $b$ divides $n$. Hence part (b) and part (c) does indeed have integer solutions, while part (a) indeed has none.

Make use of Bezout's Identity (I'll leave the workings to you, so as to let you get a feel for this) to derive that the integer solutions for (b) is $$x = 379n + 220\\ y=-1249n - 725$$ for arbitrary $n \in \mathbb{Z}$, and that the integer solutions for (c) is $$x = 38n + 30\\ y= -51n - 40$$ for arbitrary $n\in\mathbb{Z}$.

For part (ii), simply subject the solutions to the constraint that both $x,y$ must be non-negative, and observe that under this constraint, $n$ can admit only finitely many values, which gives you all of the non-negative integer solutions.