Let $a,b \in \Bbb N $ with $\gcd(a,b)=1$. The equation $ax + by = ab$ has the obvious solution $(b, 0)$ in integers. Show, however, that it has no solution in positive integers.
Solutions of the equation $ax+by=ab$
-
0So because $\gcd(a,b)=1$, $y$ must divide $a$ and $x$ must divide $b$? – 2012-10-18
4 Answers
Hint $\ $ By Euclid's Lemma, $\rm\ (a,b) = 1,\,\ a,b\:|\:ax+by\:\Rightarrow\: a\:|\:y,\ b\:|\:x\:\Rightarrow\:ab\:|\:ax,by$
-
0Yes, that's one way to conclude. Or: if two common multiples $\ge 0$ have sum = lcm then one of them is $0$ and the other is the lcm, by the *leastness* of the lcm. – 2012-10-18
Assume x and y are integers. $ax + by =ab$ is equivalent to $a(x-b)=b(a-y)$. Since gcd(a,-b)=1, a must divide into a-y. Thus, $a-y=ak$, or $y=a(1-k)$ where k is an integer (positive or negative). Now we can write $a(x-b)=b(a-y)=b(ak)$. Canelling out the a's on each side, we now have $x-b=bk$. So $x=b(1+k)$. Thus an integer solution must be of the form $(b(1+k);a(1-k))$ with k being an integer. We want both x and y to be positive. x is positive if and only if $k \ge -1$ and y is positive if and only if $1 \ge k$. Thus, k can only be equal to -1, 0 or 1. If k=0, we have (b,0) as a solution, if k=1, the solution is (0,a). Other than those two solutions, there are no positive integer solutions. k=-1 makes y negative.
The general integer solution is $x=b+tb$, $y=-ta$. We're assuming $a,b,x,y>0$, so we have from the $x$ equation that $1+t>0$ and from the $y$ equation that $-t>0$. Putting these together gives $-1
Assume $a\geq 2$. Since $ax-ab=-by$ therefore $a|by$. But $gcd(a,b)=1$ thus $a|y$. Hence $y=0,a,2a,\ldots$. The only possibilities $y=0,a$. If $y=0$ then $x=b$, if $y=a$ then $x=0$. If $a=1$ then by symmetry if $b\geq 2$ we obtain the statement. The case $a,b=1$ is trivial.