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

Various proofs I just want to verify

  1. Mar 14, 2009 #1
    If a|(b+c) and gcd(b,c)=1, then gcd(a,b)=1=gcd(a,c)

    Suppose a|(b+c) and the gcd(a,b)=d.

    al=b+c and d|a and d|b. This implies a=dr and b=ds.

    drl=ds+c => drl-ds=c => d(rl-s)=c => d|c

    Since d|b, d|c and 1|b and 1|c, d must divide 1. Therefore d=1.

    By the same reasoning gcd(a,c)=1.

    al=b+c and d|a and d|c. This imples a=dr and c=dt

    drl=b+dt => drl-dt=b => d(rl-t)=b => d|b

    since gcd(b,c)=1 1|b and 1|c and d|c d must divide 1

    therefore d=1
  2. jcsd
  3. Mar 14, 2009 #2
    The proof is right. but note that there could be more than one integer dividing a particular number, so if 1 divides b and c it does not imply gcd(b,c) = 1. The way you have done the proof is very correct, but always note the statement
    "Since d|b, d|c and 1|b and 1|c, d must divide 1."
  4. Mar 14, 2009 #3
    I'm really not sure how to concluide proofs like this. How should I have concluded it?
  5. Mar 14, 2009 #4
    you will just rewrite he statement "Since d|b, d|c and 1|b and 1|c, d must divide 1." as follows "Since gcd(b,c) = 1 and d|b, d|c, then gcd(b, c) = 1." then u can conclude that
    d = 1. hence gcd(a,b)=1=gcd(a,c)
  6. Mar 14, 2009 #5
    I don't know why, but any gcd type proof always throws me off.
  7. Mar 14, 2009 #6
    Ok, so
    The conclusion of my proof just for gcd(a,b) should say:

    Since gcd(b,c)=1 and d|b and d|c, then the gcd(a,b)=1.
  8. Mar 14, 2009 #7
    yes, you got it. gcd type proof is interesting
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook