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

  • Thread starter buddyholly9999
  • Start date
  • Tags
    Head
In summary, the conversation discusses proving that if r and s are positive integers with r > s and gcd(r,s)=1, then gcd(rs , r + s)= 1. There are two ways to show this, using the Euclidean algorithm or by showing that 1 can be a linear combination of rs and r + s. The conversation also touches on proving that gcd(r^s, s^r) = 1 for distinct primes r and s, and concludes that finding the gcd in this scenario is trivial.
  • #1
buddyholly9999
74
0
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...
 
Physics news on Phys.org
  • #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:
  • #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?
 
  • #4
Suppose p is a prime and p divides both rs and r+s. WLOG p divides r... the rest is left to you.
 
  • #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:
  • #6
buddyholly9999 said:
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?
 
  • #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?
 
  • #8
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
Thanks for the help...ever need a back rub, foot massage...someone dealt with...you know where i'll be..
 

1. What is gcd and why is it important in proving the equation?

gcd stands for greatest common divisor and it is the largest number that divides both given numbers evenly. In this equation, proving that gcd(rs, r + s) = 1 means that the two numbers r and s are relatively prime, which is important in many areas of mathematics such as number theory and cryptography.

2. How do I approach proving this equation?

One way to prove this equation is through the Euclidean algorithm, which states that the gcd of two numbers can be found by repeatedly dividing the larger number by the smaller number until the remainder is 0. If the remainder is 0, the smaller number is the gcd. Using this method, you can show that the gcd of rs and r + s must be 1.

3. Can I use a different method to prove this equation?

Yes, there are other methods that can be used to prove this equation. For example, you could use a proof by contradiction, where you assume that gcd(rs, r + s) is not equal to 1 and then show that this leads to a contradiction. Another method is using the fundamental theorem of arithmetic, which states that every integer greater than 1 is either prime or can be uniquely factored into prime numbers.

4. Are there any specific techniques or strategies I should use in my proof?

One technique that can be helpful in proving this equation is to use the properties of prime numbers. For example, knowing that a prime number can only be divided by 1 and itself can be useful in showing that the gcd of rs and r + s must be 1. Additionally, breaking down the equation into smaller parts and working through each part can also be helpful.

5. Is there a real-life application for proving this equation?

Yes, there are many real-life applications for proving this equation. For example, in cryptography, this equation is used to ensure that two numbers used for encryption are relatively prime, making it more difficult for someone to decrypt the message. In number theory, proving this equation can help in solving problems related to prime numbers and their properties.

Similar threads

MHB Properties of gcd's and relatively prime integers
    • Linear and Abstract Algebra
Replies
2
Views
2K
Every field is an integral domain?
    • Linear and Abstract Algebra
Replies
2
Views
1K
MHB Short topical webpage title: Proving Properties of Unital Rings
    • Linear and Abstract Algebra
Replies
1
Views
2K
MHB Combination of Linear Transformations
    • Linear and Abstract Algebra
Replies
2
Views
1K
I Splitting ring of polynomials - why is this result unfindable?
    • Linear and Abstract Algebra
Replies
9
Views
1K
Proving Linear Manipulation to Reduce to GCD of Two Numbers
    • Linear and Abstract Algebra
Replies
6
Views
3K
A Structure of modulo-integer matrix group GL(r,Z(n))?
    • Linear and Abstract Algebra
Replies
17
Views
4K
Prove RS is parallel to KL using vector method
    • Precalculus Mathematics Homework Help
Replies
20
Views
2K
Order of a^m when gcd(m,n) = 1
    • Calculus and Beyond Homework Help
Replies
2
Views
1K
Proving gcd(r,s)=1 with gcd(r^2-s^2, r^2+s^2)
    • Linear and Abstract Algebra
Replies
3
Views
3K

Hot Threads

Recent Insights

Back
Top