1
$\begingroup$

In a diophantine equation $ax + by = n$ with $(a, b) = 1$, the greatest possible value of $n$ such that both $(x, y)$ are not positive is $ab − b − a$?

This is given in my module (without any proof). I am assuming that "both $(x, y)$ are not positive" means at-least one must be negative. I was wondering how to prove this.

  • 0
    The statement of the problem is not clear. Among other things, are you looking for non-negative solutions or positive solutions? Also, "both $x$ and $y$ are not positive" could very well mean that *each* of $x$ and $y$ is $\le 0$. With rewording, you will need (i) the argument of Gerry Myerson that $ab-b-a$ is not representable with both $x$ and $y \ge 0$ and (ii) everything bigger **is** representable. For that, again the basic tool is the formula for the general solution of the Diophantine equation given a particular solution $(u,v)$.2012-04-02

1 Answers 1

1

First note that if $x=b-1$ and $y=-1$ then $ax+by=ab-b-a$.

Then what you have to know is that if $(u,v)$ is one solution to $ax+by=n$ then the full set of solutions is given by $x=u+kb$, $y=v-ka$ where $k$ runs through the integers (positive and negative (and zero)).

So to increase $y$, you have to decrease $x$ by $b$ (or more), so you can't get a positive solution when $n=ab-b-a$.

By the way, I'm assuming that $a,b$ are meant to be positive integers.