Does the Greatest Common Divisor of a and b Divide c in the Equation Ax+by=c?

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

Can someone please help me?

 

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

 

[kingwinner]

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 ?

 

[HallsofIvy]

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.

 

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

 

[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!

 

[JSuarez]

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

 

[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!

 

[kingwinner]

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.

 

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

 

[kingwinner]

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?

 

[JSuarez]

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

 

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

Thanks for your help!

 

[JSuarez]

Perfectly correct.