# Diophantine Equation Proof: Show that if $n=ab-a-b$, then there are no nonnegative solutions of $ax + by = n$

Let $a$ and $b$ be relatively prime positive integers and let $n$ be a positive integer. A solution $(x, y)$ of the linear diophantine equation $ax + by = n$ is nonnegative when both $x$ and $y$ are non-negative. Show that if $n=ab-a-b$, then there are no nonnegative solutions of $ax + by = n$.

Not sure where to begin for this proof question. Anyone got any ideas?

As $\gcd(a,b)=1$, this implies $a \mid (y+1)$ and $b \mid (x+1)$, say $x+1=br$ and $y+1=as$ for positive integers $r,s$. Now substitute and the answer should be clear.
• Fundamental Theorem of Arithmetic. $a$ divides $a(x+1)$ on the left-hand side and $ab$ on the right, hence it must divide $b(y+1)$ on the left. But $gcd(a,b)=1$, so $a \mid (y+1)$. Similar logic proves $b \mid (x+1)$. – Kieren MacMillan Sep 29 '13 at 1:55
• You’re trying to prove that $x$ and $y$ cannot be negative, not $r$ and $s$ (which only exist as a result of the method of proof). If $x \ge 1$, then $x+1=br \ge 2$; as $b \ge 1$ by hypothesis, we have $r \ge 1$. By similar logic, $y \ge 1$ implies $s \ge 1$. Now take $x=0$, so that $by = n = ab-a-b$. Then the FTA says $b \mid a$, which contradicts $gcd(a,b)=1$. Again, similar logic forces $y \ne 0$. – Kieren MacMillan Sep 29 '13 at 2:41
• Isn't it enough to say $r+s = 1 \implies$ without loss of generality $r = 1, s = 0$, then we have $y + 1 = as = 0 \implies y = -1$, which is not allowed? – Jonathan Rayner May 31 at 14:36