Mongolian IMO Team Selection Tests, 2015

Assume that there is a quadruple $(a, b, n, m)$ such that
$$\mathrm{rad}(a^n + b^n) = \mathrm{rad}(a^m + b^m).$$
Let $d$ be the greatest common divisor of $a^n + b^n$ and $a^m + b^m$. We claim that
$$d = \begin{cases} a^{(n,m)} + b^{(n,m)}, & v_2(n) = v_2(m) \\ (a+b, 2), & v_2(n) \neq v_2(m) \end{cases}$$
where $v_2(n)$ denotes the exponent of $2$ in the decomposition of $n$. We set
$$k = \frac{mn}{\min\{v_2(n), v_2(m)\}}.$$
Since $a^n \equiv -b^n \pmod d$ and $a^m \equiv -b^m \pmod d$, we get $a^k \equiv b^k \equiv -b^k \pmod d$ if $v_2(n) \neq v_2(m)$. Thus $d = (a+b, 2)$, since $a^2 \equiv 0, 1 \pmod 4$. If $v_2(n) = v_2(m)$ then we may assume that
$n, m$ are odd and $(n, m) = 1$, i.e., $nu + mv = 1$ for some positive integers $u, v$. Hence the claim follows from $a \equiv a^{nu+mv} \equiv ((-b)^n)^u ((-b)^m)^v \equiv -b \pmod d$.

Since $\text{rad}(a^n + b^n) = \text{rad}(d)$, it suffices to consider the case that $v_2(n) = v_2(m)$. In this case, without loss of generality, we may assume that $n$ is odd and $m = 1$. Then we can easily get a contradiction from the following lemma.
Lemma. Let $p$ be an odd prime. If $a > b$ and $(a, b) \neq (2, 1)$ then there is a prime $q$ such that $q \mid a^p + b^p$ and $q \nmid a + b$.
Proof. Assume that $\text{rad}(a^p + b^p) = \text{rad}(a + b)$. Then $\text{rad}(A) \mid \text{rad}(a + b)$, where $A$ denotes the integer $(a^p + b^p)/(a + b)$. If $q$ is a prime divisor of $(A, a + b)$ then it is clear that $q = p$. Hence $A \le p$ by the lifting the exponent lemma. On the other hand, we have
$$\begin{align*} A &= (a-b) \sum_{i=1}^{(p-1)/2} a^{p-2i} b^{2(i-1)} + b^{p-1} \\ &\geq a^{p-2} + b^{p-1} \\ &\geq 3^{p-2} + 1 \\ &> p, \end{align*}$$
which yields a contradiction. $\square$