Let us assume that there are infinitely many $ a$ for $ m, n,$ then clearly $ m > n.$ So we may let $ m = n + k$ for some $ k > 0.$ Since $ a^m + a - 1 = (a^n + a^2 - 1)a^k - (a^{k + 2} - a^k - a + 1)$ there are infinitely many $ a$ such that $ a^n + a^2 - 1 | a^{k + 2} - a^k - a + 1.$ Let $ f(x) = x^n + x^2 - 1, g(x) = x^{k + 1} + x^k - 1, h(x) = (x - 1)g(x).$ We have $ \frac {h(x)}{f(x)} = g(x) + \frac {r(x)}{f(x)}$ with $ \text{deg}(r) < \text{deg}(f).$ As there are infinitely many $ a$ for which $ r(a)=0$, we get that $ r$ is identically $ 0,$ or in other words, $ f|h.$ This in turn yields that $ f|g.$ Now, it is clear that $ f$ has a root $ b \in ]0, 1[,$ and then $ b$ is a root of $ g,$ too. So we have $ b^n + b^2 - 1 = 0 = b^{k + 1} + b^k - 1.$ So we get (consider the degrees) that $ k \geq 2,$ and so $ b^n \geq b^{k + 1}$ and $ b^2 \geq b^k.$ Now, since $ 1 = b^n + b^2 \geq b^{k + 1} + b^k = 1,$ we must actually have $ k = 2, n = 3, m = 5.$ And finally the identity $ a^5 + a - 1 = (a^2 - a + 1)(a^3 + a^2 - 1)$ shows that the unique solution is the pair $ (m, n) = (5, 3).$

mathmanman wrote: So we get (consider the degrees) that $ k \geq 2,$ and so $ b^n \geq b^{k + 1}$ Can you explain this?

http://www.kalva.demon.co.uk/imo/isoln/isoln023.html

Peter wrote: mathmanman wrote: So we get (consider the degrees) that $ k \geq 2,$ and so $ b^n \geq b^{k + 1}$ Can you explain this? Of course : $ k+1 = \deg(g) \geq \deg(f) = n \geq 3.$ (as for the inequality, remember that $ b \in ]0, 1[.$)

Ok, I see now. Let me reword your first paragraph a bit. As the polynomial $ x^{m} + x - 1 \mod x^{n} + x^{2} - 1$ is zero for infinitely many $ x$'s, it is the zero polynomial. So $ x^{n} + x^{2} - 1|x^{m} + x - 1 = (x^n + x^2 - 1)x^k - (x - 1)(x^{k + 1} + x^k - 1)$, and since $ x = 1$ is not a root of $ x^{n} + x^{2} - 1$, it follows that $ x^{n} + x^{2} - 1|x^{k + 1} + x^k - 1$ (denote this $ f|g$). And then we continue mathmanman wrote: Now, it is clear that $ f$ has a root $ b \in ]0, 1[,$ and then $ b$ is a root of $ g,$ too. So we have $ b^n + b^2 - 1 = 0 = b^{k + 1} + b^k - 1.$ So we get (consider the degrees) that $ k \geq 2,$ and so $ b^n \geq b^{k + 1}$ and $ b^2 \geq b^k.$ Now, since $ 1 = b^n + b^2 \geq b^{k + 1} + b^k = 1,$ we must actually have $ k = 2, n = 3, m = 5.$ And finally the identity $ a^5 + a - 1 = (a^2 - a + 1)(a^3 + a^2 - 1)$ shows that the unique solution is the pair $ (m, n) = (5, 3).$