Results 1 to 8 of 8

Math Help - Gcd question

  1. #1
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35

    Gcd question

    g.c.d.(r,s)
    Last edited by maths900; February 17th 2009 at 08:07 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    See that s is irreducible.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35
    Quote Originally Posted by vincisonfire View Post
    See that s is irreducible.
    Thanx but still dont kno how to show gcd (r,s)=1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    Because s in irreducible, gcd(r,s) is either s or 1. Show that s doesn't divides r (just long division or factorization of r).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35
    Quote Originally Posted by vincisonfire View Post
    Because s in irreducible, gcd(r,s) is either s or 1. Show that s doesn't divides r (just long division or factorization of r).
    Thanx that makes sense now. i will try it out
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    The original poster asked to prove \gcd( r,s ) = 1 as integers not as polynomials.
    If it was polynomials then the result works since x^4+x^3+x^2+x+1.

    Consider f=x+1 and g=(x+3)^2 then \gcd (f(x),g(x))=1.
    However if x=1 then f(1) = 2 and g(1) = 16 but \gcd( f(1), g(1)) \not = 1.
    ----

    To solve this problem we need to know a theorem:
    Let a,n,m>0 then \gcd( a^n -1, a^m - 1) = a^d - 1 where d=\gcd(n,m).

    This means, \gcd( m^5 - 1, m^{16} - 1) = m - 1 since \gcd(5,16)=1.
    But then, \gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1.
    This completes the proof since \tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4 and \tfrac{m^{16}-1}{m-1} = 1 + m + ... + m^{15}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35
    Quote Originally Posted by ThePerfectHacker View Post
    The original poster asked to prove \gcd( r,s ) = 1 as integers not as polynomials.
    If it was polynomials then the result works since x^4+x^3+x^2+x+1.

    Consider f=x+1 and g=(x+3)^2 then \gcd (f(x),g(x))=1.
    However if x=1 then f(1) = 2 and g(1) = 16 but \gcd( f(1), g(1)) \not = 1.
    ----

    To solve this problem we need to know a theorem:
    Let a,n,m>0 then \gcd( a^n -1, a^m - 1) = a^d - 1 where d=\gcd(n,m).

    This means, \gcd( m^5 - 1, m^{16} - 1) = m - 1 since \gcd(5,16)=1.
    But then, \gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1.
    This completes the proof since \tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4 and \tfrac{m^{16}-1}{m-1} = 1 + m + ... + m^{15}.
    I havent come across this theorem, would i be able to do it some other way?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by maths900 View Post
    I havent come across this theorem, would i be able to do it some other way?
    You can find the proof here.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum