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

  1. 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?
     
    Last edited: Jan 7, 2010
  2. jcsd
  3. 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.
     
  4. 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 ???
     
  5. HallsofIvy

    HallsofIvy 40,497
    Staff Emeritus
    Science Advisor

    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.
     
  6. 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
  7. 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!
     
  8. 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).
     
  9. 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!
     

  10. 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.
     
  11. 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.
     
  12. 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?
     
  13. 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).
     
  14. 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!
     
  15. Perfectly correct.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?