Results 1 to 8 of 8

Math Help - gcd

  1. #1
    Super Member dhiab's Avatar
    Joined
    May 2009
    From
    ALGERIA
    Posts
    534

    gcd

    caluclate :
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    If you have some more information on m and n, there might be something more to say, but for general m and n, the only thing you can guarantee is 2.

    Is this part of a larger problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dhiab View Post
    caluclate :
     (5^m+7^m, 5^n+7^m) = 5^{(m,n)}+7^{(m,n)} \text{ or } 2 .

    This is just from observations, hopefully I'll tackle this soon...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    Quote Originally Posted by chiph588@ View Post
     (5^m+7^m, 5^n+7^m) = 5^{(m,n)}+7^{(m,n)} \text{ or } 2 .

    This is just from observations, hopefully I'll tackle this soon...
    I don't think your equation holds in general. For example, m=6, n=9

    5^m + 7^m = 5^6 + 7^6 = 133274
    5^n + 7^n = 5^9 + 7^9 = 42306732
    5^(m,n) + 7^(m,n) = 5^3 + 7^3 = 468
    but (133274,42306732) = 2

    Am I missing something?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by hollywood View Post
    I don't think your equation holds in general. For example, m=6, n=9

    5^m + 7^m = 5^6 + 7^6 = 133274
    5^n + 7^n = 5^9 + 7^9 = 42306732
    5^(m,n) + 7^(m,n) = 5^3 + 7^3 = 468
    but (133274,42306732) = 2

    Am I missing something?
    No you're not missing anything. I said this gcd is either 5^(m,n) + 7^(m,n) or 2, but I don't know yet when to tell which one it'll be.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    Ok, I see now.

    So your conjecture is that gcd(5^m + 7^m,5^n + 7^n) is sometimes 2 and sometimes 5^gcd(m,n) + 7^gcd(m,n) but never any other value, and you don't yet have a choice function to tell which one it is. That's an improvement on what I had to say. I said essentially that it's 2 or some multiple of 2.

    For what it's worth, I can confirm your conjecture for all m,n less than 1000.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dhiab View Post
    caluclate :
    Did you ever figure this problem out?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    I was waiting for the original poster to say something.

    It depends on the factorization

    a^n+b^n=(a^r+b^r)(a^{n-r}-a^{n-2r}b^r+a^{n-3r}b^{2r}-...+b^{n-r})

    which works if n/r is odd. So a^n+b^n\text{ and }a^m+b^m have a common factor a^r+b^r if r is a common factor of n and m, and n/r and m/r are both odd.

    So in the prime factorizations of n, m, and r, the power of 2 is the same. In fact, we should have:

    gcd(a^n+b^n,a^m+b^m)=a^{gcd(n,m)}+b^{gcd(n,m)} if the prime factorizations of n and m contain the same power of 2.

    I'm still foggy on the converse, though. Couldn't there be a common factor that's not of the form a^r+b^r?

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum