Results 1 to 3 of 3

Math Help - GCD=1 Problem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    GCD=1 Problem

    Let r,s,t be integers. If r=st+1, prove gcd(r,s) = 1.

    My works so far:

    I know that to prove gcd(r,s) =1, I need to have ra + sb = 1 for some integers a and b.

    Now r = st + 1 means 1 = r - st.

    Well, r = r(1) and - st means + s(-b)

    So 1 = r(1) + s (-t)

    Is that right?

    Thank you.

    KK
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    Let r,s,t be integers. If r=st+1, prove gcd(r,s) = 1.
    It is much simpler then that,
    \gcd (a,b) =1 for a,b>0.
    If and only if there exists integers x,y such as,
    ax+by=1.

    Thus, given,
    r=st+1
    r-st=1
    r(1)+s(-t)=1
    Since there exists integers 1,-t such that,
    rx+sy=1.
    We conclude assuming r,s>0 that \gcd(r,s)=1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    Haha, I was making this much harder than it has to be.

    I'm glad you answered this so quickly, as this problem is due in an hour.

    Thank you very much!

    KK
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum