# More primes

1. Sep 10, 2006

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

2. Sep 10, 2006

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

Last edited: Sep 10, 2006
3. Sep 10, 2006

### 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?

4. Sep 10, 2006

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

5. Sep 10, 2006

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

Last edited: Sep 10, 2006
6. Sep 10, 2006

### shmoe

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?

7. Sep 10, 2006

### 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?

8. Sep 10, 2006

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

9. Sep 10, 2006

### buddyholly9999

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