The proof consists of three steps. (1) We cannot have $0<m<n$. (2) We cannot have $n<m\le 2n$. (3) If $a^n+b^n\mid a^m+b^m$, then the same holds if we switch $m$ to $m-2n$. From these, it follows that if some exponent $m$ works, then its residue upon division by $n$ (in range $[1,2n]$) works as well, and this residue can only be $n$ because of (1-3). As a corollary, the solutions have the form $((2k-1)n,n)$ where $k,n$ are arbitrary positive integers, and they work due to the result $x+y\mid x^{2k-1}+y^{2k-1}$ (we may take arbitrary $a,b$). (1) is obvious because if $0\le m<n$, then $0<a^m+b^m<a^n+b^n$, thus it cannot be divisible by $a^n+b^n$. Let $d:=a^n+b^n$. Then we have the following: $$d\mid a^m\pm b^m\implies d\mid a^{m-n}\mp b^{m-n}.\quad (*)$$ This is true because $$a^m\pm b^m \mp b^{m-n}(a^n+b^n)=a^m\mp b^{m-n}a^n=a^n(a^{m-n}\mp b^{m-n}),$$ where $d$ and $a$ are coprime as if they shared a prime divisor, it would also divide $b$. (2) follows because for $n<m<2n$, $d\mid a^m+b^m$ implies $d\mid a^{m-n}-b^{m-n}$ where $0<m-n<n$. This shows that $a^{m-n}-b^{m-n}$ is non-zero, and that its absolute value is at most $\max\{a^{m-n},b^{m-n}\}<a^n+b^n$, and hence it is not divisible by $d$, contradiction. (3) is an immediate corollary of $(*)$ because $$d\mid a^m+b^m\implies d\mid a^{m-n}-b^{m-n}\implies d\mid a^{m-2n}+b^{m-2n}.$$ Answer: $(m,n)=((2k-1)n,n)$ with $n,k$ positive integers.

If $m=n$ then this works, otherwise we clearly must have $m > n$ Now, WLOG let $b>a$. Then $a^n+b^n|a^m+b^m$ or $a^n+b^n|b^m - b*a^{m-n}$ Now clearly $gcd(a^n+b^n, b) = gcd(a^n,b) = 1$ as a and b are relatively prime. Thus $a^n+b^n | b^{m-1} - a^{m-n}$. Applying the euclidean algorithm again we get $a^n+b^n | a^n*b^{m-n-1} + a^{m-n}$. That's what motivates us to look at 3 possibilities, m-n<n, m-n=n, m-n>n. Let's deal with the easiest one first, m-n=n. If this were the case then we would have $a^n+b^n|a^n(b^{m-n-1} + 1)$. And, as before we have that $(a^n+b^n , a^n) = 1$ (where () means gcd) Thus $a^n+b^n|b^{m-n-1} + 1$. But we know that $m=2n$ so this means $a^n+b^n|b^{n-1}+1$. And since $a,b > 1$ we have that $a^n > 1$ and $b^n > b^{n-1}$ and thus $b^{n-1} + 1 < a^n+b^n$ which is not possible as we need $b^{n-1} + 1 \ge a^n + b^n$ Now, let's deal with $m-n < n$ This is actually easier dealt with by looking back at the original equation. From $a^n+b^n|a^m+b^m$ then $a^n+b^n|b^m - b^n*a^{m-n} = b^n(b^{m-n} - a^{m-n})$. From $(a^n+b^n, b^n) = 1$ we have $a^n+b^n | b^{m-n} - a^{m-n}$. Clearly $0 < b^{m-n} - a^{m-n} < b^n < a^n+b^n$ which is a contradiction Finally, let's deal with $m-n > n$ We still have $a^n+b^n | b^{m-n} - a^{m-n}$. Now, applying the euclidean algorithm we have $a^n+b^n | b^{m-n} + b^n * a^{m-2n}$ and again, we can divide LHS by $b^n$ to get $a^n + b^n | b^{m-2n} + a^{m-2n}$. And this is where I get sniped. Sigh. Now, if $m-2n < n$ then we're done and this is impossible. Thus, either $m-2n = n$ or $m = 3n$ (which is a solution) or $ m> 3n$. Now, if $m>3n$ we keep going to get $a^n + b^n | b^{m-3n} - a^{m-3n}$. Clearly, if $m < 3n$ then we reach contradiction, and so we must have $m > 3n$ in which case we may apply EA again to get $a^n + b^n | b^{m-4n} + a^{m-4n}$. Thus, in general, if $(2k-1)n \le m < 2kn$ for some positive integer k then $a^n+b^n | b^{m-(2k-2)n} + a^{m-(2k-2)n}$, which we can prove through an easy induction. And from here, it is easy to see that unless $m - (2k-2)n = n$ or $m = (2k-1)n$ that we won't have a solution. Thus the answer, which is already stated above, is $(m,n) = ((2k-1)n,n)$ where n and k are positive integers. Darn got sniped when i was almost done.

My solution: We first prove that we must have $n \mid m$. Let $m=cn+d$ with $0 \leq d < n$ and $c>0$, because obiously $m \geq n$. Then we get $$0 \equiv a^m+b^m \equiv a^{cn+d}+b^{cn+d} \equiv a^d(-b^n)^c+b^{cn+d} \equiv b^{nc} (b^d \pm a^d) \pmod{a^n+b^n}. $$ If $d \not= 0$, then $0<\left| a^d \pm b^d \right| < a^n+b^n$, which is a contradiction. Hence $d=0$ and $m=cn$. Now we prove that $c$ must be odd. Let $A=a^n$ and $B=b^n$, then we get, if $c$ were even, $$0 \equiv A^c+B^c \equiv A^c + (-A)^c \equiv 2A^c \pmod{A+B}.$$ If $A+B$ had an odd prime divisor $p$, then we would have $p \mid A$ and hence also $p \mid B$, which is a contradiction. Hence $A+B$ must be a power of 2, which implies that $A$ and $B$ are both odd. But because $A+B>2$, we have $4 \mid A+B \mid 2A^c$, hence $A$ must also be even, which is absurd. Hence, it is necessary that $m=cn$ for some odd positive integer $c$. Clearly this is also sufficient.

Gryphos wrote: If $d \not= 0$, then $0<\left| a^d \pm b^d \right| < a^n+b^n$, which is a contradiction. Hello, I do not understand how this is a contradiction, could you please explain? Thank you in advance!

${}{}{}$

My solution: first set $(m,n)=k$ $m=pk$ $n=qk$ and $c=a^k$$d=b^k$. We have $c^q\equiv -d^q( mod c^q+d^q)$$c^p\equiv -d^p( mod c^q+d^q)$ now if we take $x$ the smallest positive number such that$c^x\equiv -d^x( mod c^q+d^q)$ we get that if we set $p=mx+g$$c^g\equiv d^g( mod c^q+d^q)$ which is contradiction because $g\le x<2x$ so we get that $x|p,x|q$ which is contradiction. Which now implies that $q=1$ . Also if we assume that $p$ is even we get that $c^p\equiv d^p\equiv -d^p(mod c^q+d^q)$ but we have that $(c,d)=1$.

Setting $m=un+v$ then plugging $a^n \equiv -b^n \pmod{a^n+b^n}$, we easily get $v=0$. Also, standard Euclidean Algorithm gives $u \equiv 1 \pmod{2}$ so the answer is $(n(2k+1),n)$.

$$a^n+b^n|a^{m-2nk}+b^{m-2nk}$$Answer:$(m,n)=(n(2k+1),n)$

very easy problem for p4