# Proving there are infinitely many solutions

Let c be any integer.

Prove that if $k$ and $l$ are coprime positive integers, then the linear Diophantine equation $kx-ly=c$ has infinitely many positive integer solutions

To start off, I know that a positive integer solution is a pair $(x,y) \in \mathbb N \times \mathbb N$ such that $kx-ly=c$. But I am not sure how I can use this to prove the statement.

Any help is appreciated. :)

• The Euclidean algorithm will give you one solution. Once you have one solution $(k,\ell)$, you can look for a solution of the form $(k+A,\ell-B)$. – Christopher Carl Heckman Mar 1 '16 at 7:00

As Carl Heckman stated in the comments, by the Euclidean algorithm you can find one solution. Denote this solution as $(x_0, y_0)$. Consider $(x, y) = (x_0 + lz, y_0 + kz)$, where $z$ is a positive integer. If you substitute, you get $$k(x_0 + lz) - l(y_0 + kz) = kx_0 - ly_0 = c$$, which means that the second pair is also a solution. So you can choose $z$ big enough to make the solutions positive and then you can increase $z$ even more, getting infinitely many solutions.
First of all, you prove that there exist $x$ and $y$ that make the condition that make the above condition possible.
That can be done with ease since $k$ and $l$ are relatively prime so that there exist $x$ and $y$ such that $kx - ly = 1$. Now multiply both sides of this equation by $c$ to get $ckx - cly = c \implies k(cx) - l(cy) = c$. This proves the existence of one such pair.