1
$\begingroup$

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. :)

$\endgroup$
1
  • $\begingroup$ 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)$. $\endgroup$
    – Christopher Carl Heckman
    Mar 1, 2016 at 7:00

2 Answers 2

Reset to default
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

With a bit of algebraic manipulation done in the other answer we can prove that there are an infinite number of them too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.