# 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})$$.

• Well 7-5 =2 and 7+5 = 12 is just too good a coincidence to ignore. Gcd (5^m+7^m,5^n+7^n)=gcd (5^m+7^m-5^n-7^n,5^n+7^n). How can we rewrite $5^m-5^n+7^m-7n$? Nov 4, 2016 at 7:27
• You are correct that gcd (sm,sn)=gcd (sm,5^m7^msn-2n). But as neither 5 nor 7 divide sm, we can divide out all factors of 5 and 7. Nov 4, 2016 at 9:29
• That's basically my answer. Go throough my example. See where I divide 5 out of the gcd. Nov 4, 2016 at 9:32
• If gcd (n,b)=1 then gcd (b,nc)=gcd (b,c). You can verify gcd (7,5^n+7^n)=1 so gcd (5^m7^m,sm)=1. So gcd (sm,5^m7^msn-2m)=gcd (sm,sn-2m). Nov 4, 2016 at 9:41

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.

• For a formal proof I guess we could use induction. Nov 4, 2016 at 8:47
• I have made an edit. Please refer to it. Nov 4, 2016 at 8:50