Register to reply

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

by kingwinner
Tags: gcda
Share this thread:
kingwinner
#1
Jan7-10, 11:31 PM
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?
Phys.Org News Partner Science news on Phys.org
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
JSuarez
#2
Jan8-10, 02:30 PM
P: 403
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
#3
Jan9-10, 01:13 AM
P: 1,270
Quote Quote by JSuarez View Post
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
#4
Jan9-10, 06:45 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,345
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.
kingwinner
#5
Jan9-10, 06:09 PM
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.
kingwinner
#6
Jan9-10, 06:16 PM
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!
JSuarez
#7
Jan9-10, 06:36 PM
P: 403
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
#8
Jan9-10, 07:02 PM
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!
kingwinner
#9
Jan9-10, 07:05 PM
P: 1,270
Quote Quote by JSuarez View Post
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
#10
Jan9-10, 08:02 PM
P: 403
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
#11
Jan9-10, 08:14 PM
P: 1,270
Quote Quote by JSuarez View Post
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
#12
Jan9-10, 08:17 PM
P: 403
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
#13
Jan9-10, 08:30 PM
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!
JSuarez
#14
Jan9-10, 08:56 PM
P: 403
Perfectly correct.


Register to reply