1. ## gcd

caluclate :

2. 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?

3. Originally Posted by dhiab
caluclate :
$\displaystyle (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...

4. Originally Posted by chiph588@
$\displaystyle (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?

5. Originally Posted by hollywood
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.

6. 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.

7. Originally Posted by dhiab
caluclate :
Did you ever figure this problem out?

8. I was waiting for the original poster to say something.

It depends on the factorization

$\displaystyle 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 $\displaystyle a^n+b^n\text{ and }a^m+b^m$ have a common factor $\displaystyle 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:

$\displaystyle 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 $\displaystyle a^r+b^r$?

- Hollywood