1. Not finding help here? Sign up for a free 30min 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!

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

    xa+yb=d

    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

    xa+yb=c

    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

    x0a+y0b=d

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

    (nx0)a+(ny0)b=nd=c

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Intro to Proofs: Greatest Common Divisors
Loading...