Diophantine Equation Proof: Show that if $n=ab-a-b$, then there are no nonnegative solutions of $ax + by = n$
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?
Related videos on Youtube
DJ_
Updated on September 25, 2021Comments
-
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?
-
Stefan4024 about 10 yearsTake a look at the Coin problem
-
-
DJ_ about 10 yearsHmm which theorem did you use to get from: As gcd(a,b)=1, this implies a∣(y+1) and b∣(x+1)
-
Kieren MacMillan about 10 yearsFundamental 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_ about 10 yearsAre 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 about 10 yearsYou’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 over 4 yearsIsn'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 over 4 years@JonathanRayner. Yes! Very elegant solution.