Results 1 to 2 of 2

Math Help - Relatively Prime

  1. #1
    Junior Member
    Joined
    Feb 2006
    From
    Canada
    Posts
    45

    Exclamation Relatively Prime

    Does anyone how to prove the following:

    a and b are relatively prime if and only if There exist integers s and t satisfying sa + tb = 1

    Thanks very much!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by suedenation
    Does anyone how to prove the following:

    a and b are relatively prime if and only if There exist integers s and t satisfying sa + tb = 1

    Thanks very much!!!
    If as+tb=1 assume that \gcd(a,b)=d>1. Then the left hand is divisible by d but the right hand is not a contradiction. Thus,
    \gcd(a,b)=1.

    The converse is tricker to prove, maybe I will post the proof later on I cannot post it now.
    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. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 07:03 PM
  5. Replies: 6
    Last Post: August 27th 2010, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum