# Solutions of the equation $ax+by=ab$

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.

-
What happens when looking modulo $b$? And $a$? – Lord_Farin Oct 18 '12 at 14:39
Does this mean $by=moda$ and $ax=modb$? – blah Oct 18 '12 at 14:46
Yes, $by = 0 \pmod a$ and $ax = 0 \pmod b$. Now you can use what you know about $\gcd(a,b)$. – Lord_Farin Oct 18 '12 at 14:49
So because $\gcd(a,b)=1$, $y$ must divide $a$ and $x$ must divide $b$? – blah Oct 18 '12 at 14:52

Hint $\$ By Euclid's Lemma, $\rm\ (a,b) = 1,\,\ a,b\:|\:ax+by\:\Rightarrow\: a\:|\:y,\ b\:|\:x\:\Rightarrow\:ab\:|\:ax,by$

-
so $ax=kab$ for some $k \in \Bbb Z$ and $by=nab$ for some $n \in \Bbb Z$ which means $k+n=1$ and aside from the given case this means that either $k$ or $n$ is negative? Is this correct? – blah Oct 18 '12 at 15:15
Yes, 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. – Bill Dubuque Oct 18 '12 at 15: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<t<0$, but there are no integers $t$ in that range.

-

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.

-