0
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmm which theorem did you use to get from: As gcd(a,b)=1, this implies a∣(y+1) and b∣(x+1) $\endgroup$ – DJ_ Sep 29 '13 at 1:51
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Kieren MacMillan Sep 29 '13 at 1:55
  • $\begingroup$ Are we only assuming r, and s to be positive? When I sub it back in i get 1 = r + s. So if r=1 and s=0 then this doesn't prove that there are no non-negative solutions since that includes 0 and 1 $\endgroup$ – DJ_ Sep 29 '13 at 2:17
  • 2
    $\begingroup$ 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$. $\endgroup$ – Kieren MacMillan Sep 29 '13 at 2:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Jonathan Rayner May 31 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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