6. N6 (ROM) ${ }^{\mathrm{IMO3}}$ Find all pairs of positive integers $m, n \geq 3$ for which there exist infinitely many positive integers a such that
$$
\frac{a^{m}+a-1}{a^{n}+a^{2}-1}
$$
is itself an integer.
6. Suppose that $(m, n)$ is such a pair. Assume that division of the polynomial $F(x)=x^{m}+x-1$ by $G(x)=x^{n}+x^{2}-1$ gives the quotient $Q(x)$ and remainder $R(x)$. Since $\operatorname{deg} R(x)$ $a^{m}+\alpha-1=0$; hence $m<2 n$.
Now we have $F(x) / G(x)=x^{m-n}-\left(x^{m-n+2}-x^{m-n}-x+1\right) / G(x)$, so $H(x)=x^{m-n+2}-x^{m-n}-x+1$ is also divisible by $G(x)$; but deg $H(x)=$ $m-n+2 \leq n+1=\operatorname{deg} G(x)+1$, from which we deduce that either $H(x)=G(x)$ or $H(x)=(x-a) G(x)$ for some $a \in \mathbb{Z}$. The former case is impossible. In the latter case we must have $m=2 n-1$, and thus $H(x)=x^{n+1}-x^{n-1}-x+1$; on the other hand, putting $x=1$ gives $a=1$, so $H(x)=(x-1)\left(x^{n}+x^{2}-1\right)=x^{n+1}-x^{n}+x^{3}-x^{2}-x+1$. This is possible only if $n=3$ and $m=5$.
Remark. It is an old (though difficult) result that the polynomial $x^{n} \pm$ $x^{k} \pm 1$ is either irreducible or equals $x^{2} \pm x+1$ times an irreducible factor.