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

More primes

  1. Sep 10, 2006 #1
    I saw this on a website. Prove that if r and s are positive integers with
    r > s and gcd(r,s)=1, then gcd(rs , r + s)= 1. I can think of two ways to show this. Using the Euclidean algorithm or by showing that 1 can be a linear combination of rs and r + s. Funny thing...I couldn't do either them. I'm ashamed of myself and now I'm looking for some answers...
  2. jcsd
  3. Sep 10, 2006 #2
    You can drop the conditions that r, s are positive (but I suppose you still need r, s != 0) and r > s.

    Let d = gcd(rs, r + s).

    d divides both rs - r(r + s) and rs - s(r + s).
    Last edited: Sep 10, 2006
  4. Sep 10, 2006 #3
    Ok..I'm afraid I'm not following...d = 1 in this case. 1 divides anything. So how is that 1 dividing rs - r(r + s) and rs - s(r + s) show that the
    gcd(rs, r + s) = 1. Wouldn't we have to show that 2 isn't a divisor, then 3 isn't a divisor?
  5. Sep 10, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Suppose p is a prime and p divides both rs and r+s. WLOG p divides r... the rest is left to you.
  6. Sep 10, 2006 #5
    Wait wait....I think someone got something wrong...probably me....

    Ok, r and s are primes...oops..I might have forgotten to mention that..

    that integer in my first post is typo....so....

    does that change everything?

    Ok OK..i'll restate it...

    let r and s be two different primes...show that gcd(rs, r + s) = 1.

    Again...I can't prove this..

    .....I type this as tears hit the keyboard... :(
    Last edited: Sep 10, 2006
  7. Sep 10, 2006 #6


    User Avatar
    Science Advisor
    Homework Helper

    Suppose you have a prime that divides both rs and r+s. It divides rs, so it must be either r or s. Can either r or s divide r+s?
  8. Sep 10, 2006 #7
    Oh yeah...makes sense now...

    you da man shmoe....now how about....

    gcd(r^s, s^r) = 1 same scenario...

    Could I say something like, r divides r^s, but s does not...and s dvides s^r but r does not..thus the gcd is 1?
  9. Sep 10, 2006 #8


    User Avatar
    Science Advisor
    Homework Helper

    with r and s still distinct primes gcd(r^m,s^n)=1 should be pretty clear for any non-negative integers m and n. You have the prime factorization of two numbers sitting in front of you, finding the gcd is trivial.
  10. Sep 10, 2006 #9
    Thanks for the help...ever need a back rub, foot massage...someone dealt with...you know where i'll be..
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook