Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Common Divisor Proof

  1. Jan 31, 2010 #1
    Hello I have the following proposition to prove.

    Prop. Let a,b be integers. If 1 is a linear combination of a and b, then a and b are relatively prime.

    I am given the following definition.
    Let a and b be integers, not both zero. If gcd(a,b)=1, then a and b are said to be relatively prime. Notice that the only common divisors of relatively prime integers are 1 and -1.

    My work so far:

    (1) Let a,b be integers.
    (2) By definition of linear combination there exist integers x,y such that 1=ax+by.
    (3) Because 1 is a common divisor of a,b then 1 must be the gcd(a,b)
    (4)Therefore a and b are relatively prime

    I need help on (3), I know that I am missing some steps and logic but I am not sure what to do. Am I approaching this correctly? Thank you.
     
  2. jcsd
  3. Jan 31, 2010 #2

    mathman

    User Avatar
    Science Advisor

    If n (>1) is a common divisor of a and b, then n divides ax+by, but ax+by=1 and n cannot divide 1.
     
  4. Jan 31, 2010 #3
    Would I incorporate this by saying that there exists a common divisor, call it n where n>1, of a and b such that 1= knx+Lny where k and L are integers. so 1=n(kx+Ly). Obviously n cannot divide one, is this saying that therefore the gcd(a,b)=1? Therefore a and b are relatively prime?

    Thank you.
     
  5. Jan 31, 2010 #4
    Does anyone know if this is the correct proof:

    (1) Let a,b be integers.
    (2) By definition of linear combination there exist integers x,y such that 1=ax+by.
    (3) there exists a common divisor, call it n where n>1, of a and b such that 1= knx+Lny where k and L are integers. so 1=n(kx+Ly)
    (4)From (3) gcd(a,b)=1
    (4)Therefore a and b are relatively prime

    Thanks
     
  6. Jan 31, 2010 #5
    anyone?
     
  7. Jan 31, 2010 #6
    No, the correct proof would be:

    Hipothesis: let a and b be integers, not both zero, such that there are x,y, also integers, such that ax + by = 1.

    (1) Any common divisor of a and b must also be a divisor of any linear integer combination af a and b.

    (2) Therefore, if d|a and d|b, then d|ax+by, which implies that d|1.

    (3) If d is a positive common divisor, then d = 1; in particular gcd(a,b) = 1.

    Hopefully, this is will be the last time anyone spells out a proof for you in a non-homework section!
     
  8. Jan 31, 2010 #7
    Thanks for the help, I am new to the site. Maybe next time you could simply point me in the right direction of where to post instead of getting angry.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook