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?
On
Would this naive one work?
As $(a, b) = 1,$ and $(ab - a - b)$ is a multiple of which, thus the eqn. $ax + by = ab - a - b$ has solution.
Suppose that all solutions are non-negative, i.e. both $x, y \ge 0,$ then, as $a, b > 0,$ $ab - a - b \ge 0,$ i.e. $(a - 1)(b - 1) \ge 1.$
But this is not true, e.g. $a = 100\wedge b = 1.$
P.S. For the comments in Kieren's solution, assuming that all solutions are non-negative, then $1\le x + 1 = br,$ as $b$ is positive then $r\ge 1,$ so be $s\ge 1,$ thus the $r + s = 1$ doesn't hold. by TRUE implying FALSE, one thus gets contradiction, right?
Substituting, we have \begin{align} ax+by &= n \\ &= ab-a-b \\ a(x+1)+b(y+1) &= ab. \end{align}
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.
Hope this helps!
Kieren.