1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Intro to Proofs: Greatest Common Divisors

  1. Nov 11, 2011 #1
    1. The problem statement, all variables and given/known data

    (a) Let a and b be integers with gcd(a,b)=d, and assume that ma+nb=d for integers m and n. Show that the solutions in Z to


    are exactly

    x=m+k(b/d), y=n-k(a/d)

    where k∈Z.

    (b) Let a and b be integers with gcd(a,b)=d. Show that the equation


    has a solution (x,y)∈ ZxZ if and only if d|c.

    Z refers to integers.

    2. Relevant equations

    3. The attempt at a solution

    Ok so I'm pretty sure I figured out part (a).

    Part (b) on the other hand is causing me problems. I know since it's an "if and only if" question, I have to prove it both ways.

    This is what I have so far.

    So we have some x and y, such as


    Then we multiply both sides by some arbitrary element, such as n. Giving us,


    So that's the first part. Now I'm supposed to go the other way with it, showing that
    xa+yb=c -> c=nd, n∈ Z.
  2. jcsd
  3. Nov 11, 2011 #2
    How about the contrapositive for the other direction? That might be easier.
  4. Nov 12, 2011 #3
    So maybe this?

    Suppose dc...

    Then c≠nd

    In which case, c≠nd≠(nx0)a+(ny0)b.

    So like that? Or am I way off? Sorry I'm not very good at this... The teacher explains things way over everyone's head.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook