Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I suppose that the question is meant to be about $n$ that cannot be written as $ax+by$ with $x,y\geq0$. If you confirm, please change your title, which is nonsensical as it stands. – Marc van Leeuwen Apr 2 '12 at 8:02
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)$. – André Nicolas Apr 2 '12 at 11:40
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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