Proving gcd(rs , r + s)= 1: I'm in Over My Head!

[buddyholly9999]

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...

 

[Muzza]

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).

 

[buddyholly9999]

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?

 

[matt grime]

Suppose p is a prime and p divides both rs and r+s. WLOG p divides r... the rest is left to you.

 

[buddyholly9999]

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... :(

 

[shmoe]

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... :(

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?

 

[buddyholly9999]

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?

 

[shmoe]

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.

 

[buddyholly9999]

Thanks for the help...ever need a back rub, foot massage...someone dealt with...you know where i'll be..