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

1. ### kingwinner

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...

Last edited: Jan 7, 2010
2. ### JSuarez

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.

3. ### kingwinner

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 ???

4. ### HallsofIvy

41,267
Staff Emeritus
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.

5. ### kingwinner

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.

Last edited: Jan 9, 2010
6. ### kingwinner

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!

7. ### JSuarez

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).

8. ### kingwinner

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!

9. ### kingwinner

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.

10. ### JSuarez

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.

11. ### kingwinner

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?

12. ### JSuarez

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).

13. ### kingwinner

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.