Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What happens when looking modulo $b$? And $a$? –  Lord_Farin Oct 18 '12 at 14:39
1  
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

4 Answers 4

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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