2
$\begingroup$

Prove that for every positive integer $m$ there exists a linear equation $ax+by=c$ which has exactly $m$ positive integer solutions.

So for this problem, I tried to find the integer solutions for both $x$ and $y$. I wasn't quite sure how to solve it but I was able to produce something akin to a solution:

Theorem:

Let $d=(a,b)$, then $ax+by=c$ has $m$ solutions only if $d \mid c$.

Since $d=(a,b)$, we have $d=am+bn$ for some integers $m$ and $n$. After this I was a bit lost on how to continue on with this but what I was going to do was create another variable place holder to set equal to $c =d \times \text{placeholder}$. So, my question is, what kind of beautiful proofs does stack exchange have for this problem?

$\endgroup$
  • $\begingroup$ Can you state the problem more precisely? Are all the variables required to be integers? Nonnegative integers? $\endgroup$ – Eric Wofsey Mar 2 '18 at 4:29
  • $\begingroup$ Makes no sense. The equation must be a line. If a line has two integer solutions it has a rational slope and infinite integer solutions. $\endgroup$ – fleablood Mar 2 '18 at 6:34
3
$\begingroup$

Over the integers, any equation $ax+by=c$ has either none or infinitely many solutions. So I'll assume that $a,b$ are positive integers and that you are looking for positive integer solutions.

Let us look at equations $ax+by=1$, where $(a,b)=1$. Given a solution $x_0,y_0$ (that can be found with the Euclidean Algorithm), the general solution is $$ x_n=x_0+bn,\ \ y_n=y_0-an. $$ Note that necessarily one of $x_0,y_0$ is positive and the other is negative. Let us assume that $x_0<0$, $y_0>0$. To have positive solutions we need $$ x_0+bn>0,\ \ \ y_0-an>0, $$ which translate into $$ -\frac{x_0}b<n<\frac{y_0}a. $$ So the number of positive solutions is $$ \left\lceil \frac{y_0}a+\frac{x_0}b-1\right\rceil $$ (the weird expression accounts for the fact the behaviour is different depending on whether the sum is an integer or not). For instance take $a=1$, $b=2$, $x_0=-2m-2$, $y_0=2m+2$. Then $$ ax_0+by_0=-2m-2+4m+4=2m+2. $$ And $$ \frac{y_0}a+\frac{x_0}b-1=\frac{2m+2}1+\frac{-2m-2}2-1=m. $$ That is, if $a=1$, $b=2$, $c=2m+2$, then $ax+by=c$ has $m$ positive integer solutions.

$\endgroup$
  • $\begingroup$ This means that at least one of $x$ or $y$ must be even, because we are counting positive integer solutions. $\endgroup$ – Feeds Mar 2 '18 at 5:41

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.