# Ax+by=c => gcd(a,b)|c ?

by kingwinner
Tags: gcda
 P: 1,270 Theorem: For all a,b,c E Z such that a and b are not both 0, there exist x,y E Z such that ax+by=c <=> gcd(a,b)|c. Here is my attempt of proving it... (<=) Sppose gcd(a,b)|c By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb Now gcd(a,b)|c => gcd(a,b)=c/s for some s E Z. => c/s = ka+mb => c=(ks)a+ (ms)b with (ks) and (ms) integers. But I have some trouble proving the converse of this. (=>) Suppose there exist x,y E Z such that ax+by=c. By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb Now I need to prove that gcd(a,b)|c, i.e. c = r gcd(a,b) for some r E Z. How can we prove this? I really have no idea at this point... Can someone please help me?
 P: 402 Remember that ANY common divisor of a and b, including the greatest, will also divide any integer linear combination ax + by of a and b.
P: 1,270
 Quote by JSuarez Remember that ANY common divisor of a and b, including the greatest, will also divide any integer linear combination ax + by of a and b.
Yes, I remember this. But how can we use this fact to prove that
there exist x,y E Z such that ax+by=c
=> gcd(a,b)|c ???

 Math Emeritus Sci Advisor Thanks PF Gold P: 39,565 Ax+by=c => gcd(a,b)|c ? Be specific. Start by defining n= GCD(a,b). Then a= nx for some integer x and b= ny for some integer y. If GCD(a,b)|c then c= nz for some integer z. Now write your equations using those.
 P: 1,270 OK, so since gcd(a,b) is a common divisor of a and b => gcd(a,b)|a and gcd(a,b)|b => gcd(a,b)|am+bk for ANY m,k E Z => in particular, gcd(a,b)|c which completes the proof.
 P: 1,270 But actually now I have some concerns about the proof of the other direction: gcd(a,b)|c => there exist x,y E Z such that ax+by=c Here is my attempted proof: Sppose gcd(a,b)|c By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb Now gcd(a,b)|c => c = s * gcd(a,b) for some s E Z => gcd(a,b) = c/s for some s E Z => c/s = ka+mb => c = (ks)a+ (ms)b with (ks) and (ms) integers. I am worried about the step in red, in which a division is required. If s=0, then we are in trouble since division by 0 is not allowed. How can we solve this issue? Or is there a simpler proof? Thanks for any help!
 P: 402 Your proof is essentially correct, but we should, in this context say that c is divisible by s, instead of speaking of the division of c by s (this is because here division means integer division, and this involves a remainder, which in this case is 0, etc.); in this sense, substituting c/s by c = s*gcd(a,b) is more correct. Regarding the s = 0 problem, you should be able to see that it doesn't matter: it could only happen if c = 0 and, in this case, gcd(a,b)|0 is always true. Another note: in integer division, 0|c iff c = 0, so it's entirely correct that "division by zero" isn't allowed in this context: 0|0 is a true statement (but also a somewhat trivial one).
 P: 1,270 Yes, I can see that c is divisible by s, but how can I complete the proof with this? And how can I combine these two equations c = s * gcd(a,b) for some s E Z gcd(a,b) = ka+mb if I do not divide the first equation by s? Thanks!
P: 1,270
 Quote by JSuarez Regarding the s = 0 problem, you should be able to see that it doesn't matter: it could only happen if c = 0 and, in this case, gcd(a,b)|0 is always true.

Yes, gcd(a,b)|0 is always true, but that's the hypothesis, and I need to prove the "conclusion" in this case, i.e. there exist x,y E Z such that ax+by=c.
 P: 402 No, the hypothesis is gcd(a,b)|c. The case c = 0 is a particular one, where you may choose x = y = 0 ( = s, by the way) making ax + by = 0 true as well. In any case, if are still worried, write it multiplicatively c = s*gcd(a,b), then there will be no problem at all; but you should understand WHY the argument is correct in either case.
P: 1,270
 Quote by JSuarez No, the hypothesis is gcd(a,b)|c. The case c = 0 is a particular one, where you may choose x = y = 0 ( = s, by the way) making ax + by = 0 true as well. In any case, if are still worried, write it multiplicatively c = s*gcd(a,b), then there will be no problem at all; but you should understand WHY the argument is correct in either case.
OK, so the special case for s=0 is easy to prove. Now I see how we can prove the claim in the two separate cases.

Is there any way to prove the claim at once without dividing into two cases?
If I write it multiplicatively, c = s * gcd(a,b) without isolating for gcd(a,b), then how can I replace the gcd(a,b) in the equation gcd(a,b) = ka+mb?
 P: 402 You don't have to consider s = 0 separately, just multiply gcd(a,b) = ax + by by s to obtain c = a(xs) + b(ys).
 P: 1,270 OK, then I think the following proof would be better. Sppose gcd(a,b)|c => c = s * gcd(a,b) for some s E Z By theorem, there exists k,m E Z such that gcd(a,b) = ka+mb => s * gcd(a,b) = ska + smb => c = (sk)a+ (sm)b with (sk) and (sm) integers. Thanks for your help!
 P: 402 Perfectly correct.