Suppose the equation $ax+by=c$ has $m$ positive solutions. How many positive solutions does the equation $ax+by=c+ab$ have?

181 Views Asked by At

Suppose that $a,b,c$ are positive integers. Suppose the equation $ax+by=c$ has $m$ positive solutions. How many positive solutions does the equation $ax+by=c+ab$ have?

I know $ax+by=ab$ does not have any positive integer solutions but would that necessarily imply that $ax+by=c+ab$ still has m solutions? I have this confusion since if we add the two equations we get $ax+by=\frac{c+ab}{2}$.

1

There are 1 best solutions below

0
On BEST ANSWER

We write $a = du$ and $b = dv$ with $\gcd(u, v) = 1$. It follows that $d \mid c$ and we may write $c = dw$.

Thus the two equations become $ux + vy = w$ and $ux + vy = w + duv$, respectively.

Let us prove the following claim.

Assume that $u, v$ are coprime. Then the number of positive solutions of $ux + vy = w + uv$ is exactly $1$ more than that of $ux + vy = w$.

Proof: Every positive solution $(x_0, y_0)$ of $ux + vy = w$ uniquely gives a positive solution of $ux + vy = w + uv$, namely $(x_0, y_0) \mapsto (x_0 + v, y_0)$. This gives a bijection between positive solutions of $ux + vy = w$ and positive solutions of $ux + vy = w + uv$ such that $x > v$.

Thus it suffices to consider what are the "extra" solutions of $ux + vy = w + uv$, namely those satisfying $x \leq v$. I claim that there is exactly one.

Firstly, taking the equation mod $v$, we see that $ux \equiv w \mod v$, which (together with $x \leq v$) shows that there is at most one such solution. Secondly, by taking $x_0$ to be the minimum positive integer such that $ux \equiv w\mod v$, we have $w + u(v - x_0) > 0$ and also $w + uv - ux_0 \equiv 0 \mod v$, hence $(x_0, \frac{w + uv - ux_0}v)$ is a positive integer solution.


By induction, the number of positive solutions of $ux + vy = w + duv$ is exactly $d$ more than that of $ux + vy = w$.

Therefore the answer is $m + \gcd(a, b)$.