Results 1 to 3 of 3

Math Help - Addition of relatively prime numbers

  1. #1
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Addition of relatively prime numbers

    RTP: If gcd(a,b)=1, then gcd(a, (a+b))=1, where a,b are positive integers

    Proof
    Note 1=as+bt
    Assume gcd(a, (a+b))=k
    Then
    am+(a+b)n=a(m+n)+bn=k*1
    a(m+n)+bn=aks+bkt
    Thus
    m+n=ks,n=kt
    So
    m+kt=ks,m=ks-kt
    So
    a(ks-kt)+bkt=aks+bkt
    -akt=0
    This is impossible, so our assumption is wrong
    Thus our statement is true

    Questions
    1. Is this proof valid?
    2. Can I generalize to :If gcd(a,b)=k, then gcd(a, (a+b))=k
    3. Is there a simpler non-contradiction, non-FTA proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288
    This thread is a repost. Sorry. Marking it as solved and requesting that it be removed please
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by I-Think View Post
    RTP: If gcd(a,b)=1, then gcd(a, (a+b))=1, where a,b are positive integers

    Proof
    Note 1=as+bt
    Assume gcd(a, (a+b))=k
    Then
    am+(a+b)n=a(m+n)+bn=k*1
    a(m+n)+bn=aks+bkt
    Thus
    m+n=ks,n=kt
    So
    m+kt=ks,m=ks-kt
    So
    a(ks-kt)+bkt=aks+bkt
    -akt=0
    This is impossible, so our assumption is wrong
    Thus our statement is true

    Questions
    1. Is this proof valid?
    2. Can I generalize to :If gcd(a,b)=k, then gcd(a, (a+b))=k
    3. Is there a simpler non-contradiction, non-FTA proof?
    Quote Originally Posted by I-Think View Post
    This thread is a repost. Sorry. Marking it as solved and requesting that it be removed please
    I can't find your other thread. Your proof looks fine from what I see. Yes, you're theorem generalizes. One merely needs note that if \text{gcd}(a,a+b)\mid \text{gcd}(a,b) since z\mid a\text{ and }z\mid a+b\implies z\mid a\text{ and }z\mid b. Also, \text{gcd}(a,b)\mid \text{gcd}(a,b) since  z\mid a\text{ and }z\mid b\implies z\mid a\text{ and }z\mid a+b
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. The addition of irrational numbers.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 25th 2011, 03:58 PM
  3. Addition of numbers relatively prime
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 30th 2010, 05:55 AM
  4. addition of power numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 29th 2010, 02:39 PM
  5. Addition of 3 or more numbers
    Posted in the Math Software Forum
    Replies: 0
    Last Post: August 1st 2010, 09:14 AM

/mathhelpforum @mathhelpforum