Register to reply 
Ax+by=c => gcd(a,b)c ?by kingwinner
Tags: gcda 
Share this thread: 
#1
Jan710, 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? 


#2
Jan810, 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.



#3
Jan910, 01:13 AM

P: 1,270

there exist x,y E Z such that ax+by=c => gcd(a,b)c ??? 


#4
Jan910, 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.



#5
Jan910, 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. 


#6
Jan910, 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! 


#7
Jan910, 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, 0c iff c = 0, so it's entirely correct that "division by zero" isn't allowed in this context: 00 is a true statement (but also a somewhat trivial one). 


#8
Jan910, 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! 


#9
Jan910, 07:05 PM

P: 1,270

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



#11
Jan910, 08:14 PM

P: 1,270

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



#13
Jan910, 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! 


#14
Jan910, 08:56 PM

P: 403

Perfectly correct.



Register to reply 