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

3,236

Solution 1

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.

Solution 2

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?

Share:
3,236

Related videos on Youtube

DJ_
Author by

DJ_

Updated on September 25, 2021

Comments

  • DJ_
    DJ_ about 2 years

    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?

  • DJ_
    DJ_ about 10 years
    Hmm which theorem did you use to get from: As gcd(a,b)=1, this implies a∣(y+1) and b∣(x+1)
  • Kieren MacMillan
    Kieren MacMillan about 10 years
    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)$.
  • DJ_
    DJ_ about 10 years
    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
  • Kieren MacMillan
    Kieren MacMillan about 10 years
    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$.
  • Jonathan Rayner
    Jonathan Rayner over 4 years
    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?
  • Kieren MacMillan
    Kieren MacMillan over 4 years
    @JonathanRayner. Yes! Very elegant solution.