Let $m$ and $n$ be positive integers such that $\gcd(m,n)=1.$Compute $\gcd(5^m+7^m,5^n+7^n)$. Problem: Let $m$ and  $n$ be positive integers such that $\gcd(m,n)=1.$Compute $\gcd(5^m+7^m,5^n+7^n)$.
My Attempt: I wrote a simple computer program and deduced that $\gcd(5^m+7^m,5^n+7^n)=2$ if $m+n$  is odd and $\gcd(5^m+7^m,5^n+7^n)=12$ if $m+n$ is even. I would like to know if there is a way to prove these results.
Edit: Found a solution on the web:
I don't understand why $\gcd(s_m,s_n)=\gcd(s_m,s_{n-2m})$. According to me, $\gcd(s_m,s_n)=\gcd(s_m,5^m7^ms_{n-2m})$.
 A: Here's a simple case.  See if you can generalize it:
$\gcd (5^3+7^3,5^7+7^7)=$
$\gcd (5^3+7^3,5^7+7^7-7^4 (5^3+7^3))=$
$\gcd (5^3+7^3,5^7-5^3*7^4)=$ note: $5\not \mid 5^3+7^3$ so
$\gcd (5^3+7^3,5^4-7^4)=$
$\gcd (5^3+7^3,5^4-7^4+7 (5^3+7^3))=$
$\gcd (5^3+7^3,5^4+5^3*7)=$
$\gcd (5^3+7^3,5+7)=$
$\gcd (5^3+7^3-7^2 (5+7),5+7)=$
$\gcd(5^3-7^2*5,5+7)=$
$\gcd(5^2-7^2,5+7)=$
$\gcd (5^2-7^2+7 (5+7),5+7)=$
$\gcd (5^2+7*5,5+7)=$
$\gcd (5+7,5+7)=12$
As $\gcd(m,n)=1$
This "swinging" by reducing and subtracting the powers will eventually result in $5^{\gcd (m,n)}\pm 7^{\gcd (m,n)}=5\pm 7= 2|12$. (Positive/negative doesn't matter for gcd)
Whether it will be $5+7$ or $5-7$ will depend on whether we swing an even or  odd number of times.
=====
=====
Alright.  Here's a more thorough proof:
Let $\gcd(B,A) = 1$ and wolog $B > A$ and $\gcd(n,m)=1$ wolog $n>m$ then $\gcd(B^n+A^n, B^m+A^m) = B + (-1)^{m+n}A$  (and so $\gcd(7^n+5^n,7^m+5^m) = 2$ if $m+n$ is odd and is $12$ if $m+n$ is even.
Proof:
$\gcd(n,m)=1$ which means by Euclid's algorithm That there are series of $n_i, m_i;k_i$ so that:
$n=n_0; m= m_0$
$n_0 = k_0*m_0 + m_1$
$n_1 = m_0; n_1 = k_1*m_1 + m_2$
.....
$n_i = m_{i-1}; n_i = k_i*m_i + m_{i+1}$
...
$n_{z-1} = k_{z-1}m_{z-1} + 1; m_z = 1$
$n_z=m_{z-1} = 1*m_{z- 1}$
$n_{z+1} = 1 $
Interestingly $z$ is odd if and only if $n+m$ is odd. (To be honest I'm not sure how to prove that.)
$\gcd(B^n + A^n,B^m + A^m) = \gcd(B^n + A^n - B^{n-m}(B^m + A^m),B^m + A^m)=$
$\gcd(B^n + A^n - B^n - B^{n-m}A^m,B^m + A^m) = \gcd(A^n - A^mB^{n-m},B^m +A^m)=$
$\gcd(-A^m(B^{n-m} - A^{n-m}),B^m + A^m) = \gcd(B^{n-m} - A^{n-m},B^m+ A^m)$
And repeating via induction we can get:
$=\gcd(B^{n-k_0*m=m_1} \pm A^{m_1},B^{m=n_1} + A^{n_1})$ where it is a "plus" if $k_0$ is even and a "minus" if $k_0$ is odd.
An repeating via induction we can get:
$=\gcd(B \pm A, B \pm A) = B\pm A$
"plus" if $\sum k_i$ is even, and "minus" if the sum is odd.
Somehow we can show $\sum k_i \text{ is odd } \iff z \text { is even } \iff $m+n $ \text { is even }$.  I guess that part needs a little work.
