MEMO

Solution:

If $\frac{m}{n}=q$ is an odd integer, we have
$$\frac{a^{m}+b^{m}}{a^{n}+b^{n}}=\frac{\left(a^{n}\right)^{q}+\left(b^{n}\right)^{q}}{a^{n}+b^{n}}=\left(a^{n}\right)^{q-1}-\left(a^{n}\right)^{q-2} \cdot b^{n}+\cdots-a^{n} \cdot\left(b^{n}\right)^{q-2}+\left(b^{n}\right)^{q-1}$$
which is an integer for all positive integers $a$ and $b$. We will prove that pairs $(q n, n)$, where $q$ is an odd integer, are the only solutions. Let us assume the opposite, i.e. that there exist pairs $(m, n)$ that are solutions to our problem for which $\frac{m}{n}$ is not an odd integer. Among those pairs, let us choose one pair having the minimal sum.

Obviously, $m>n$. Let $m=n+k$ for a positive integer $k$. Without loss of generality, we may assume $a>b$. In that case
$$\frac{a^{m}+b^{m}}{a^{n}+b^{n}}>\frac{a^{n} \cdot b^{k}+b^{m}}{a^{n}+b^{n}}=b^{k}$$
thus there exists a positive integer $t$ such that
$$\frac{a^{m}+b^{m}}{a^{n}+b^{n}}=b^{k}+t$$
This equation can be written as follows:
$$\begin{aligned} a^{m}+b^{m} & =\left(b^{k}+t\right)\left(a^{n}+b^{n}\right), \\ a^{m} & =a^{n} b^{k}+t\left(a^{n}+b^{n}\right) . \end{aligned}$$
Since $a$ and $b$ are relatively prime, $a^{n}+b^{n}$ and $a^{n}$ are relatively prime as well. Therefore, from the last equation we can conclude that $t$ is divisible by $a^{n}$. Let $c$ be a positive integer such that $t=c \cdot a^{n}$. We have
$$a^{k}=b^{k}+c \cdot a^{n}+c \cdot b^{n}$$
The right-hand side of the previous equation is greater than $a^{n}$ so we conclude that $k>n$. Previous equation can be written as
$$a^{n}\left(a^{k-n}-c\right)=b^{n}\left(b^{k-n}+c\right) \text{.}$$
This implies that $b^{k-n}+c$ is divisible by $a^{n}$, since $a$ and $b$ are relatively prime. Let $x$ be a positive integer such that
$$b^{k-n}+c=x \cdot a^{n}$$
The previous equation gives us
$$a^{k-n}-c=x \cdot b^{n}$$
Summing the last two equations gives us
$$a^{k-n}+b^{k-n}=x\left(a^{n}+b^{n}\right)$$
which means that
$$\frac{a^{k-n}+b^{k-n}}{a^{n}+b^{n}}$$
is an integer. Since $(k-n)+n=k<m+n$ and because we have chosen $(m, n)$ to have minimal sum, we conclude that
$$\frac{k-n}{n}=s$$
is an odd positive integer. Let $r \geqslant 0$ be an integer such that $s=2 r+1$. This implies that
$$k-n=(2 r+1) \cdot n$$
i.e.
$$k=(2 r+2) \cdot n$$
This means that
$$\frac{m}{n}=\frac{n+k}{n}=\frac{(2 r+2) \cdot n+n}{n}=2 r+3$$
which contradicts our assumption that $\frac{m}{n}$ is not an odd integer. Therefore, the only solutions are pairs $(m, n)=(q n, n)$ where $q$ is an odd positive integer and $n$ is an arbitrary positive integer.

Solution 2:

Clearly $m>n$. Write $m=k n+r$, where $k \geqslant 1$ and $0 \leqslant r<n$. Since
$$\frac{a^{m}+b^{m}}{a^{n}+b^{n}}=a^{(k-1) n+r}+\frac{b^{m}-a^{(k-1) n+r} b^{n}}{a^{n}+b^{n}}$$
is integer, $\frac{b^{m}-a^{(k-1) n+r} b^{n}}{a^{n}+b^{n}}$ is integer as well. However, since $a$ and $b$ are coprime,
$$\frac{b^{m-n}-a^{(k-1) n+r}}{a^{n}+b^{n}}=-a^{(k-2) n+r}+\frac{a^{(k-2) n+r} b^{n}+b^{m-n}}{a^{n}+b^{n}}$$
is again an integer. Proceeding this way we get that $a^{n}+b^{n}$ divides $b^{r}+(-1)^{k} a^{r}$. Since $\left|b^{r}+(-1)^{k} a^{r}\right|<a^{n}+b^{n}$, we conclude that $b^{r}+(-1)^{k} a^{r}=0$. Since $a$ and $b$ are coprime, $r$ has to be zero and $k$ odd. So the only solutions are $(k n, n)$ where $k$ is an odd integer.

Solution 3:

If $m<n$, then $a^{m}+b^{m}<a^{n}+b^{n}$ and so there are no solutions. Assume now that $m \geqslant n$. Using long division, we get:
$$\begin{aligned} & \left(a^{m}+b^{m}\right):\left(a^{n}+b^{n}\right)=a^{m-n}-a^{m-2 n} b^{n}+a^{m-3 n} b^{2 n}-\cdots \\ & \frac{a^{m}+b^{n} a^{m-n}}{b^{m}-b^{n}+a^{m-n}} \\ & \frac{-a^{m-n} b^{n}-b^{2 n} a^{m-2 n}}{b^{m}+b^{2 n} a^{m-2 n}} \\ & \frac{a^{m-2 n} b^{2 n}+a^{m-3 n} b^{3 n}}{b^{m}-a^{m-3 n} b^{3 n}} \end{aligned}$$
The remainders after each step are of the form $b^{m}+(-1)^{k} a^{m-k n} b^{k n}$. For the expression to be an integer, one of these expressions has to be equal to zero. This can only happen when $k$ is odd and $m=k n$. Finally, we check that for $(m, n)=(k n, n)$ for $k$ odd we get
$$a^{m}+b^{m}=\left(a^{n}+b^{n}\right)\left(\left(a^{n}\right)^{k-1}-\cdots \pm\left(b^{n}\right)^{k-1}\right)$$