# Prove that there exists a linear equation $ax+by=c$ which has $m$ solutions

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?

• Can you state the problem more precisely? Are all the variables required to be integers? Nonnegative integers? – Eric Wofsey Mar 2 '18 at 4:29
• 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. – fleablood Mar 2 '18 at 6:34

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.
• This means that at least one of $x$ or $y$ must be even, because we are counting positive integer solutions. – Feeds Mar 2 '18 at 5:41