Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Ljunggren's theorem kills it. //my bad, there is answer m=5, n=3.

May I know that what is"Ljunggren's theorem"? Thanks.

http://www.math.sc.edu/~filaseta/seminars/MSRI2002/MSRILecture42002.pdf

hmm wrote:

Wow, that was quite ingenious. I have another finish to this problem which I feel is slightly cleaner: Since $ a^n + a^2 - 1 | a^m + a - 1$, $ a^n + a^2 - 1 | (a+1)(a^m + a - 1) - (a^n + a^2 - 1) = (a^{m+1} + a^m) + (a^2 - 1) - (a^n + a^2 - 1) = a^{m+1} + a^m - a^n = a^n(a^{m-n+1} + a^{m-n} - 1)$. Therefore, $ a^{n} + a^2 - 1 | a^{m-n+1} + a^{m-n} - 1$. Hence, $ n \leq m - n + 1$, so $ 2n - 1 \leq m$. But it was have shown that $ m \leq 2n - 1$, so we have that $ m = 2n - 1$. Therefore, $ a^n + a^2 - 1 | a^n + a^{n-1} - 1$, so $ a^n + a^2 - 1 | a^{n-1} - a^2$. The only way this can be is if $ a^{n-1} = a^2$, yielding $ n = 3$ and $ m = 5$, as desired.

We first show that $f(a) = a^n+a^2-1$ has no double root. But it is easy to see that $\gcd(f(a), f'(a)) = \gcd(a^n+a^2-1, na^{n-1}+2a) = 1$ (not hard, I can show this more explicitly). Now let $r$ be a root of $f(a)$. Then $r^m+r-1 = 0, r^n+r^2-1 = 0$. Rearranging the above equations gives $r^m = 1-r, r^n = (1-r)(1+r)$. Dividing these equations and rearranging gives $r^{m-n+1}+r^{m-n}-1 = 0$. But this holds for all roots $r$, so we get that $f(a) \vert a^{k+1}+a^k-1$, where $k = m-n$. By a rather famous result, $X^n-X-1$ is irreducible for all $n$, so if we reverse the coefficients, $X^n+X^{n-1}-1$ is also irreducible. Therefore, $f(a) = a^{k+1} + a^k - 1 \implies n = 3, k = 2, \implies m = 5, n = 3$. This article seems to contain the proof that $X^n-X-1$ is irreducible in the beginning and much more later.

My solution is written in the language of modules of polynomials, though the key ideas are nearly the same. It is less elegant than solutions above (As usual). It may appear lengthy but it is just direct computations ( I didn't omit any details, it is just the same as in my scratch paper) Denote $f(a)=\frac{a^m+a-1}{a^n+a^2-1}$. . We let $P_m(x)=x^m+x-1$ and $Q_n(x)=x^n+x^2-1$, we have since both polynomials are monics, we can use Euclidean theorem for monic integer polynomials, to conclude that there is $S,R\in \mathbb{Z}[x]$ where $ \deg R < n$, such that $ P_m(x)= Q_m(x) S(x) + R(x)$, we have then \[ f(x) = \frac{x^m+x-1}{x^n+x^2-1} = \frac {P_m(x)}{Q_n(x)}= S(x) + \frac{R(x)}{Q_n(x)} \] If $R(x)$ is non-zero, We get the $\frac{R(x)}{Q_n(x)} \rightarrow 0$, which imply that for all but finitely many integers $s$, $ |\frac{R(x)}{Q_n(x)}| <1 $. And as that term never achieves zero for large numbers, we can't have $f(a)$ integer for infinitely many $a$'s. So we must have $Q_n | P_m$ in $\mathbb{Z}[x]$. Easily one can see that we must have $m > n$ . Now we prove that $Q_n | P_m$ iff $(m,n)=(5,3)$. We do module arithmetic in the Euclidean domain $\mathbb{Q}[x]$ to prove that. Note that $(x,Q_n(x))=1$ and $(x-1,Q_n(x))=1$ in $\mathbb{Q}[x]$, and hence \[ \begin{array}{lcl} x^m+x-1 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^m+x-x^n-x^2 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{m-1}+1-x^{n-1}-x & \equiv & 0\pmod{x^n+x^2-1} \\ \iff x^{n-1}(x^{m-n} - 1) + (1-x) & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{m-2} + \cdots + x^{n-1} -1 & \equiv &0 \pmod{x^n+x^2-1} \end{array}\] If we let $m=n+i$ we get \begin{align*} x^{m-2} + \cdots + x^{n-1} -1 &\equiv x^{n+i-2}+ \cdots + x^{n-1} + x^{i} + x^{i-1} + \cdots + x^2 -1 \\ &\equiv (x^{n+i-2}+ x^{i})+ (x^{n+i-3}+x^{i-1}) + \cdots + ( x^{n} + x^{2}) + x^{n-1} - x^{i} - x^{i-1} - \cdots - x^{2} -1 \\ &\equiv x^{i-2}+ x^{i-3}+ \cdots +1 + x^{n-1} - x^{i} - x^{i-1} - \cdots - x^{2} -1 \\ &\equiv x^{n-1} + x - x^{i} - x^{i-1} \pmod{x^n+x^2-1} \end{align*} Now if $i<n$ we get $x^{n-1} + x - x^{i} - x^{i-1} = 0 $ which cannot happen unless $n-1=i$ and $i-1=1$ and hence $(n,i)=(3,2)$ and so we have the solution $(m,n) = (5,3)$. Now if $i=n+j ; j\geq0$ , then \[ \begin{array}{lcl} x^{n-1} + x - x^{i} - x^{i-1} & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff - x^{n-1} - x + x^{n+j} + x^{n+j-1} & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{n+j-1} + x^{n+j-2} - x^{n-2} - 1 & \equiv & 0\pmod{x^n+x^2-1} \\ \iff x^{n-2}(x^{j+1}-1) + x^{n+j-2} - 1 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{n+j-2} + 2x^{n+j-3} + \cdots + 2x^{n-2}+ x^{n} + \cdots + 1 & \equiv &0 \pmod{x^n+x^2-1} \end{array}\] But $x^{n+j-2} + 2x^{n+j-3} + \cdots + 2x^{n-2}+ x^{n} + \cdots + 1 \geq 1$ for $ x\geq0$ , while $s^n+s^2-1=0$ for some $s\in(0,1)$ since divisibility applies also in $\mathbb{R}[x]$ , we get $s^{n+j-2} + 2s^{n+j-3} + \cdots + 2s^{n-2}+ s^{n} + \cdots + 1 = 0$, getting a contradiction.

I found a pretty cool and unique solution to this problem. Can someone check for its validity?

Notice that $m>n$ since $m,n>3$ implies that if $m \leq n$, then $0<\frac{a^m+a-1}{a^n+a^2-1}<1$ for $a$ relatively large. First we claim that $\frac{a^m+a-1}{a^n+a^2-1}$ must always be an integer. Indeed, since $\frac{a^m+a-1}{a^n+a^2-1}=R(x)+\frac{Q(x)}{a^n+a^2-1}$ for polynomials $R,Q$, with $deg(Q)<deg(a^n+a^2+1)$, implying that for large $a$, $Q(x)<a^n+a^2-1$ occurs, meaning that the quotient cannot yield an integer unless $Q(x)=0$ for infinitely many values, implying the above claim. Now we can bound. Since $a^n + a^2 - 1 | a^m + a - 1$, we get that $ a^n + a^2 - 1 | (a+1)(a^m + a - 1) - (a^n + a^2 - 1)$. But $(a+1)(a^m + a - 1) - (a^n + a^2 - 1)= a^{m+1} + a^m - a^n = a^n(a^{m-n+1} + a^{m-n} - 1)$. Therefore, $ a^{n} + a^2 - 1 | a^{m-n+1} + a^{m-n} - 1$. Hence, $ n \leq m - n + 1$, so $ 2n - 1 \leq m$. Plugging in $a=2$, we immediately get $2^n+3|2^m+1$ with $m<2n$. Then $gcd(2^n+3,2^m+1)=gcd(3(2^{m-n})-1,2^n+3)$. Since $3(2^{m-n})-1<3(2^{m-n})<3(2^n)$ and $3(2^{m-n})-1$ is odd, $3(2^{m-n})-1=2^n+3$. This rearranges to $3(2^k)=2^n+4$ for $k=m-n$. Since $n>2$, $k<2$, implying the only solution to be $m=5,n=3$.

The condition is equivalent to $a^n+a^2-1$ dividing $a^m+a-1$ as polynomials. The big step is the following analytic one. Claim: We must have $m \le 2n$. Proof. Assume on contrary $m > 2n$ and let $0 < r < 1$ be the unique real number with $r^n+r^2 = 1$, hence $r^m+r = 1$. But now \begin{align*} 0 &= r^m + r - 1 < r(r^n)^2 + r - 1 = r\left( (1-r^2)^2+1 \right) - 1 \\ &= -(1-r)\left( r^4+r^3-r^2-r+1 \right). \end{align*}As $1-r > 0$ and $r^4+r^3-r^2-r+1 > 0$, this is a contradiction $\blacksquare$ Now for the algebraic part. Obviously $m > n$. \begin{align*} a^n+a^2-1 &\mid a^m+a-1 \\ \iff a^n+a^2-1 &\mid (a^m+a-1)(a+1) = a^m(a+1) + (a^2-1) \\ \iff a^n+a^2-1 &\mid a^m(a+1) - a^n \\ \iff a^n+a^2-1 &\mid a^{m-n}(a+1) - 1. \end{align*}The right-hand side has degree $m-n+1 \le n+1$, and the leading coefficients are both $+1$. So the only possible situations are \begin{align*} a^{m-n}(a+1) - 1 &= (a+1)\left( a^n+a^2-1 \right) \\ a^{m-n}(a+1) + 1 &= a^n+a^2-1. \end{align*}The former fails by just taking $a=-1$; the latter implies $(m,n) = (5,3)$. As our work was reversible, this also implies $(m,n) = (5,3)$ works, done.

orl wrote: Find all pairs of positive integers $m,n\geq3$ 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. Laurentiu Panaitopol, Romania It is standard to prove that $x^n+x^2-1 \mid x^m+x-1$ as polynomials, by the given condition. Now the former has different signs at $x=0$ and $x=1$, so pick a root $0<\alpha<1$. Notice that $\alpha^n+\alpha^2=1$ and $\alpha^m+\alpha=1$. Suppose $m \ge 2n$. Then $$\alpha^m \le \alpha^{2n} \implies 1=\alpha^2+\alpha^n<\alpha+\alpha^{2n} \iff \alpha^{2n}-\alpha^2>\alpha^n-\alpha \iff \alpha^n+\alpha<1=\alpha^2+\alpha^n \iff \alpha<\alpha^2 \iff \alpha>1$$which is a contradiction! So $m<2n$. Now $x^n+x^2-1 \mid x^{m-n+1}+x^{m-n}-1$ by taking residues. Finally, the latter polynomial has degree $m-n+1 \le (2n-1)-(n-1)$ so in fact, these two polynomials are equal, hence $m-n=2, m=2n-1$ so $m=5, n=3$. Clearly, this pair works, so we're done.

Kind of nice. The condition forces the polynomial $a^n + a^2 - 1$ to divide $a^m + a - 1$. $\textbf{Claim 01.}$ $m < 2n$. $\textit{Proof.}$ Suppose otherwise, we have $m \ge 2n$. Notice that $(0)^n + (0)^2 - 1 = -1$ and $(1)^n + (1)^2 - 1 = 1$. By the Intermediate Value Theorem, we have that the polynomial $a^n + a^2 - 1$ has a root $\alpha$ which satisfy $0 < \alpha < 1$. Therefore, \[ \alpha^m + \alpha = \alpha^n + \alpha^2 \Rightarrow \alpha (1 - \alpha) = \alpha^n (1 - \alpha^{m - n}) = (1 - \alpha^2)(1 - \alpha^{m - n}) \]This gives us \[ \alpha = (1 + \alpha)(1 - \alpha^{m - n}) \]which can be rewritten as $\alpha^{m - n} + \alpha^{m - n + 1} = 1$. Since $m - n + 1 > n \ge 3$ and $0 < \alpha < 1$. We have \[1 = \alpha^{m - n} + \alpha^{m - n + 1} \le \alpha^n + \alpha^{n - 1} \le \alpha^n + \alpha^2= 1\]results to a clear contradiction. Now, we have \[ x^n + x^2 - 1 | x^{m - n + 2} - x^{m - n} - x + 1 \]Notice that we have the bound $n \le m - n + 2 \le n + 1$. We'll prove that we must have $m - n + 2 = n + 1$. Assume otherwise, then we must have $LHS = RHS$ since they are both the polynomial in the same degree and both having leading coefficient $1$, which is a clear contradiction as $RHS$ has constant $+1$ and $LHS$ has constant $-1$. Then we have $m - n + 2 = n + 1$. By considering the constant term ad the largest coefficient, we deduce \[ (x^n + x^2 - 1)(x - 1) = x^{n + 1} - x^{n - 1} - x + 1 \]But taking $x = 2$. We have $LHS = 2^n + 2^2 - 1 \le 2^{n} + 2^{n - 1} - 1$ since $n \ge 3$. For equality to hold, we must have $n = 3$. This forces $m = 5$, and we could check that \[ (x^3 + x^2 - 1)(x^2 - x + 1) = x^5 + x - 1 \]Therefore, the pair $(3,5)$ clearly satisfies.

Lemma: For $ a, m, n\in \mathbb{N} $, we have \[a^n+a^2-1\ |\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)\] Proof: We proceed by induction on $ i $. For $ i=0, 1 $, it is true. So assume for some $i>2$, it is true. \begin{align*} a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)\\[1em] \implies a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right) - (-1)^i(a^n+a^2-1)\\[.5em] &=a^{m-i} + (-1)^i\left(-a^n+ a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}(a^2-a)\\[1em] \therefore a^n+a^2-1\ &|\ a^{m-i-1} + (-1)^{i+1}\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}\left(a-1\right)\\ \end{align*}Which proves our lemma. Now, let $ i=n $, we get, \[a^n+a^2-1\ |\ a^{m-n} + (-1)^n \left(\frac{a^n+1}{a+1}\right) + (-1)^n(a-1)\]Clearly, $ m\ge n $. Let $ m=nk+q $. If $ n $ is even, \begin{align*} a^n+a^2-1\ &|\ a^{m-n}+a-1 + \left(\frac{a^n+1}{a+1}\right)\\[.5em] \implies a^n+a^2-1\ &|\ a^q+a-1 + k\left(\frac{a^n+1}{a+1}\right) \end{align*} Which is not possible since the polynomial on the right side has degree at most $ n-1 $, and can't be $ 0 $ for all $ a\in \mathbb{Z} $. So, $ n $ is odd. Then we have, \begin{align*} a^n+a^2-1\ &|\ a^{m-n} + a-1 - \left(\frac{a^n+1}{a+1}\right) - 2(a-1)\\[.5em] \implies a^n+a^2-1\ &|\ a^q + a -1 - k\left(\frac{a^n+1}{a+1}\right) -2k(a-1) = P(a) \end{align*} Since $ P(a) $ has degree at most $ n-1 $, $ P(a) =0 $ for all $ a\in \mathbb{Z} $. \begin{align*} P(a) &= a^q + a -1 - k\left(\frac{a^n+1}{a+1}\right) -2k(a-1)\\ \therefore a^q + a - 1 &= k\left(\frac{a^n+1}{a+1}\right)+2k(a-1) \end{align*} Comparing the coefficients and degrees on both sides, we have, $ q=n-1=2,\ k=1 $. Which gives us the only solution $ (m, n) = (5, 3) $.

The problem is a joke if someone knows a particular lemma.

Cool problem! We require $a^n+a^2-1\mid a^m+a-1$, else the remainder (which is deg $n-1$ at most) will eventually be smaller than $a^n+a^2-1$ for large enough $a.$ Also note $n<2m$ otherwise $a^m+a>a^{2m}+a^2>a^n+a^2$ for $0<a<1$ and obviously one of the roots has this value. So then the remainder is $-a^{m-n+2}+a^{m-n}+a-1,$ so we want $a^n+a^2-1\mid a^{m-n+2}-a^{m-n}-a+1,$ which must be equal to $a^n+a^2-1$ or $(a^n+a^2-1)(a-1)$ as $m-n+2\leq m+1.$ For size reasons $m-n+2=m$ or $m-n+2=m+1$. The first case fails by comparison of $a$ coefficient, and the second case requires $n=3$, which gives us $(a^3+a^2-1)(a-1)=a^m+a-1,$ fixing $m=5.$ So just $(3,5)$ works.

Here is a weird reason why $m<2n$ which I can't find above, given that we already know $x^n+x^2-1$ has to divide $x^{m-n+1}+x^{m-n}-1$. Both of these polynomials are monotonic when $x>0$, and one divides the other, so it is impossible for them to have different signs for some $x>0$. Consider $x=\frac{1}{2}^{\frac{1}{n}}$. $\left(\frac{1}{2}^{\frac{1}{n}}\right)^n+\left(\frac{1}{2}^{\frac{1}{n}}\right)^2-1=\frac{1}{2}+\frac{1}{2}^{\frac{2}{n}}-1>0$ since $\frac{2}{n}<1$. On the other hand, $\left(\frac{1}{2}^{\frac{1}{n}}\right)^{m-n+1}+\left(\frac{1}{2}^{\frac{1}{n}}\right)^{m-n}-1=\left(\frac{1}{2}^{\frac{1}{n}}+1\right)\left(\frac{1}{2}^{\frac{m-n}{n}}\right)-1$. The first part of the product is $<2$ and since $\frac{m-n}{n}\ge 1$, the second part of the product is $\le \frac{1}{2}$. Thus this is $<0$, giving the desired contradiction.

Let $f(x)=x^n+x^2-1$ and $g(x)=x^m+x-1$ be polynomials in $\mathbb Z[x]$. We claim that $(m,n)=(5,3)$ works. Claim 1: $f \mid g$ holds always. Proof: For any $x \in \mathbb C$ we do polynomial division with quotient and residue in $\mathbb Z[x]$ $$g(x)=f(x)q(x)+r(x) \implies \frac{g(x)}{f(x)}=q(x)+\frac{r(x)}{f(x)}$$From here note that $\text{deg} \; r<\text{deg} \; f$ so set $x$ to be a extremely large positive integer such that $-f(x)<r(x)<f(x)$ meaning that for infinite values $r$ is 0 so $r(x)=0$ holds always meaning that $f \mid g$ as desired. Claim 2: $2n-1 \ge m$ Proof: From Claim 1 one has that all the roots of $f$ are also roots of $g$ now $f'(x)=nx^{n-1}+2x>0$ if $x>0$ hence $f$ is strictly increasing in $\mathbb R^+$, now $f(1)=1$ and $f\left(\frac{2}{3} \right)=\left(\frac{2}{3} \right)^n-\frac{5}{9}<0$ meaning that there exists a root of $f$ satisfying $\frac{2}{3}<z<1$. Assume FTSOC that $m \ge 2n$ then by all said before and ineqs $$(1-z^2)^2=z^{2n}\ge z^m=1-z \implies (1-z)(z^2+z+1+z) \ge 1 \implies 1-z^3+z-z^2 \ge 1 \implies 1 \ge z+z^2 \ge 3z-1 \implies \frac{2}{3} \ge z \; \text{contradicction!!}$$Contradiction comes from assuming $m \ge 2n$ hence $2n-1 \ge m$ as desired. A nice finish: Lets now work in integers and divisions $$a^n+a^2-1 \mid a^m+a-1 \implies a^n+a^2-1 \mid a^{m-n+2}-a^{m-n}+1-a=(a-1)(a^{m-n}(a+1)-1) \implies a^n+a^2-1 \mid a^{m-n}(a+1)-1$$From here as RHS has at most degree $n$ we see that both have to be equal and $m=2n-1$ hence $a^n+a^2-1=a^n+a^{n-1}-1$ which means $n=3$ and this means $m=5$. Hence the pair $(m,n)=(5,3)$ is the unique pair that works, thus we are done

Did it back like 2 years ago? Very cool problem. Solved with quirtt and Fafnir. Solution: We will show that $(m,n)=(5,3)$ is the only solution. One can see that it works as \[a^5+a-1=(a^2-a+1)(a^3+a^2-1).\]We will break the solution into two claims which will bound the values of $m$. We define \begin{align*} P(a) \overset{\text{def}}{=} a^m+a-1 \\ Q(a) \overset{\text{def}}{=} a^n+a^2-1 \end{align*}where $P,Q$ are polynomials. We will now prove a well-known but extremely useful lemma which will take the problem from Number Theory to Algebra! Lemma: If two polynomials $f,g \in \mathbb{Z}[x]$ are such that $f(n) \mid g(n)$ for infinitely many integers $n$, then $f(x) \mid g(x)$. Proof: Due to size reasons, it is easy to see $\deg(g) > \deg(f)$. By the division algorithm over $\mathbb{Q}[x]$, write $g = fq + r$ for $f,q \in \mathbb{Q}[x]$ and $\deg(r) < \deg(f)$. One can clear out the denominators by multiplying by suitable integer, so we assume that all the polynomials are in $\mathbb{Z}[x]$. Just pick huge $k$ such that $f(k) \mid g(k)$. It would actually mean that $f(k) \mid r(k)$. But since $\deg(r) < \deg(f)$, we must have $r \equiv 0$ as desired. $\square$ So, we can actually apply the lemma to reduce the problem down to just two polynomials dividing each other! Claim: $2n-1 \le m$. Proof: First of all notice that $\gcd(a+1,Q(a))=1$. The algebra for divisibility begins here \begin{align*} P(a) & \equiv 0 \pmod{Q(a)} \\ (a+1)P(a) & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^2-a+ a^m+a-1 & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^m+a^2-1 & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^m-a^n & \equiv 0 \pmod{Q(a)} \\ a^{m-n+1}+a^{m-n}-1 & \equiv 0 \pmod{Q(a)} \\ \end{align*}Bringing this into divisibility condition, we get \begin{align} a^n+a^2-1 \mid a^{m-n+1}+a^{m-n}-1 \label{1} \end{align}Due the bound on the degree, we get $m-n+1 \ge n$ which on simplifying gives $2n-1 \le m$ as desired. $\square$ The next is claim is a little harder to come up with and prove. Claim: $m < 2n$. Proof: Assume for the sake of contradiction, that $m>2n$. By the Intermediate Value Theorem, there exists a real root of $Q$ which lies between 0 and 1. Let this root be $\alpha$. By the problem condition, $\alpha$ is also a root of $P$. Now $P(\alpha)$ and $Q(\alpha)$ gives the following \begin{align} \alpha^m + \alpha = 1 \\ \alpha^n + \alpha^2 = 1 \end{align}Now we compute $\alpha^m$ and $\alpha^{2n}$. \begin{align*} \alpha^m & = 1- \alpha \\ \alpha^{2n} & = (1-\alpha^2)^2 \\ \end{align*}By assumption, we must have $\alpha^m < \alpha^{2n}$. Plugging in the values, we get \begin{align*} 1-\alpha & \le (1-\alpha^2)^2 \\ 1-\alpha & \le (1-\alpha)^2(1+\alpha)^2 \\ 1 & \le (1-\alpha)(1+\alpha)^2 \\ \iff \alpha & \le \varphi \end{align*}where $\varphi$ is the golden ratio. We will now show that $\alpha > \varphi$ which would bring the desired contradiction. It is easy to see that $P$ is an increasing function in the interval $[0,1]$. Note that \begin{align*} P(\varphi)=\varphi^m+\varphi-1 & < \varphi^2+\varphi-1 = 0 = P(\alpha) \\ \implies P(\varphi) & < P(\alpha) \end{align*}and we can conclude that $\alpha > \varphi$ and we are done with the claim. $\square$ Now, due to the bounds we just need to check the case for $m=2n-1$. Putting this in $(1)$ we get \[a^n+a^2-1 \mid a^{n-1}-a^2.\]This forces $n=3$ and we are done. $\blacksquare$

solved with hint to consider r, otherwise im very proud of myself It's obvious that m>n; we want to find m,n s.t. $a^{m-n+2}-a^{m-n}-a+1\equiv a^m+a-1-a^{m-n}(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}$. We claim that $m\le 2n$. Assume FTSOC m>2n, and take 0<r<1 as the real number root of both polynomials. We have $$0=r^m+r-1\le r^{2n+1}+r-1=-(1-r)(r^4+r^3-r^2-r+1),r^4+r^3-r^2-r+1>r^2(r^2+r-1)>r^2(r^m+r-1)=0,1-r>0\implies 0\le RHS<0,$$impossible. Case 1. m=2n. We have $a(a^3-2a+1)\equiv a^{n+2}-a^n-a+1-(a^2-1)(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}\implies n=\{1,2,3\}$, none of which work. Case 2. m=2n-1. We have $a^{n-1}+a^3-1\equiv a^{n+1}-a^{n-1}-a+1-a(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}$, and checking the possible n, only $\boxed{n=3,m=5}$ works. Case 3. m=2n-2 has similar computation with degrees on n, and none of n work. Case 4 has $m\le 2n-3$, none of which work by looking at deg LHS<deg RHS except for a few n, and checking those don't work. Having exhausted all cases, we conclude the proof here. Remark. After enough of these problems, reducing the degree of polynomials by suitably subtracting multiples of the modulus becomes second nature; it's very natural to do so by euclidean algorithm, and once LHS|RHS with LHS deg<RHS deg except for a few numbers, the problem is solved.

The answer is $(m,n)=(5,3)$ only, which clearly works since $a^3+a^2-1 \mid a^5+a-1$ in the polynomial sense. We now prove this is the only one. For fixed $(m,n)$, since $a^n+a^2-1$ is monic we can write $$\frac{a^m+a-1}{a^n+a^2-1}=p(a)+\frac{q(a)}{a^n+a^2-1}$$for some $p,q \in \mathbb{Z}[x]$ and $\deg q<n$. Then by considering sufficiently large $a$ we require $q \equiv 0$, so we should have $a^n+a^2-1 \mid a^m+a-1$ in the polynomial sense. Note that both of these polynomials have exactly one positive real root, so they must be the same. Call this common root $r$; clearly $r<1$. Claim: $m<2n$. Proof: Suppose otherwise. We should then have $$1=r^n+r^2=r^m+r<r^{2n}+r \implies r-r^2>r^n-r^{2mn}.$$On the other hand, since $r^m<r$ but $r^n=1-r^2>1-r$, this is impossible, since $x-x^2$ increases as $x$ gets closer to $1/2$. $\blacksquare$ Now let $m=n+k$ with $0 \leq k \leq n-1$ (since clearly $m \geq n$). We should have $$a^n+a^2-1 \mid a^k(a^n+a^2-1)-(a^{n+k}+a-1)=a^{k+2}-a^k-a+1=(a-1)(a^{k+1}+a^k-1).$$Since $\gcd(a^n+a^2-1,a-1)=1$ (in the polynomial sense) it follows that $a^n+a^2-1 \mid a^{k+1}+a^k-1$. In general $a^{k+1}+a^k-1$ is a nonzero polynomial, so $k<n-1$ is impossible, hence $k=n-1$ and $a^n+a^2-1 \mid a^n+a^{n-1}-1 \implies a^n+a^2-1 \mid a^{n-1}-a^2$. The last polynomial has degree less than $n$, hence it must be zero, i.e. $n=3$. Thus we extract the claimed solution. $\blacksquare$ Remark: Good problem to test "polynomial" intuition? To me considering $r$ felt "intuitive" but it's not super motivated in itself. I guess you start thinking about the roots after divisibility, and these are mostly hard to pin down except $r$.

The only answer is $(m, n) = (5, 3)$. Obviously $m > n$. It's not hard to see that $x^n + x^2 - 1 \mid x^m + x - 1$. Let $r$ be a real root of $x^n + x^2 - 1$. Then $r$ is real root of $x^m + x - 1$. Thus $r^n + r^2 = r^m + r$, which is equivalent to $r(1 - r) = r^n(1 - r^{m-n})$. If $m > 2n$, then $r(1 - r) = r^n(1 - r^{m-n}) > r^n(1 - r^{n}) \ge r(1 - r)$, a contradiction. Thus $m \le 2n$. Now note that $x^n + x^2 - 1 \mid (x + 1)(x^m + x - 1) = x^{m+1} + x^m + x^2 - 1$, thus $x^n + x^2 - 1 \mid x^{m-n}(x + 1) - 1$. Since $m - n + 1 \le n + 1$, thus $x^{m-n}(x + 1) - 1 = (x + 1)(x^n + x^2 - 1)$ or $x^{m-n}(x + 1) - 1 = x^n + x^2 - 1$. In the first case we have $x^{n+1} + x^n + x^3 + x^2 - x - 1 = x^{n} + x^2 - 1$, which is impossible. In the second case we have $x^n + x^2 - 1 = x^n + x^{n-1} - 1$, thus $n = 3$. Thus $m = 5$. Therefore $(m, n) = (5, 3)$ is only answer. $\blacksquare$

Note that these are both polynomials, so if for infinitely many $a$, $a^n+a^2-1\mid a^m+a-1$ then the polynomial $a^n+a^2-1$ divides the polynomial $a^m+a-1$. Note that $P(x) \mid Q(x)$ implies $\text{deg} P\le \text{deg} Q$. In particular, $m\ge n$. Since $a^n + a^2 - 1\mid a^m+a-1$, which implies $a^n+a^2-1|(a+1)(a^m+a-1)-(a^n+a^2-1)$. This becomes $a^n+a^2-1\mid a^{m+1}+a^{m}-a^n$. Note that $\gcd(a^n+a^2-1,a)=\gcd(a^2-1,a)=1$ so $a^n+a^2-1\mid a^{m-n+1}+a^{m-n}-1$. This implies $m\ge 2n-1$. This also means $m-n\ge n-1\ge 2$. By IVT and taking the derivative, there exists a unique real $0<r<1$ for which $r^n+r^2-1=0$. We must have $r^m+r-1=0$. Setting them equal, we get \[r=\frac{r^n(1-r^{m-n})}{1-r}=\frac{(1-r^2)(1-r^{m-n})}{1-r}=(1+r)(1-r^{m-n})\]and this becomes $r^{m-n}(r+1)=1=r^n+r^2\ge r^n+r^{m-n}$ which implies $r^{m-n+1}\ge r^n\implies m-n+1\le n$ so $m\le 2n-1$. Note that equality is dependent on $m-n=2$, so we need $(m,n)=(5,3)$ which works.

Claim. [Main Claim] $m \leq 2n$. Proof. Let $r$ be a root of $a^n + a^2 - 1 = 0$, such that $r^n + r^2 = r^m + r = 1$. Suppose for the sake of contradiction that $m > 2n$. Then, \begin{align*} r^m + r &< r^{2n} + r \\ &= (r^n - r^{n+2}) + r \\ &= 1 - 2r^2 + r^3 + r \\ 0 &< r^4 + r - 2r^2 \\ &=r(r-1)(r^2+r-1). \end{align*}On the other hand, $r^2 + r > 1$ and $r - 1 < 0$, so this is a clear contradiction. $\blacksquare$ Now, by Euclidean algorithm we have $$a^n + a^2 - 1 \mid (a-1)(a^{m-n+1}+a^{m-n} - 1).$$In particular, as $a^n + a^2 - 1 \equiv 1 \pmod {a-1}$, we have $$a^n + a^2 - 1 \mid a^{m-n+1} + a^{m-n} + 1.$$If $m \leq 2n-2$, then the RHS is clearly smaller and $a^{m-n+1}+a^{m-n} + 1 = 0$, which is clearly impossible. If $m \in \{2n-1, 2n\}$, perform one more step to get $$a^n + a^2 - 1 \mid a^{m-n} + a^{m-2n+1}-a^{m+3-2n} - 1.$$As $m-2n+1 \leq 1$, the RHS is smaller than the LHS now, so it must uniquely equal zero. When $m = 2n-1$, we get $a^{n-1} = a^2$, giving the solution pair $(3, 5)$. When $m = 2n$, we get $a^n + a - a^3 - 1=0$, which does not work for any value of $n$. Thus, $(3, 5)$ is the only solution.

We claim our only solution is $\boxed{(5,3)}$. Our condition, $N/D \in \mathbb{Z}$, can be rewritten as \[D \mid a^{m-n}\left(a^n+a^2-1\right) - \left(a^m+a-1\right) \implies D \mid a^{m-n+1}+a^{m-n}-1.\] There are clearly no solutions for $m \leq 2n-2$, and investigating $m=2n-1,2n$ gives the desired solution. Now assume FTSOC $m>2n$, and consider a root $0<r<1$ of $D \mid N$. Then \[\left(a^n+a^2\right)^2 - (a^m+a) = 0 \implies a\left(2a^{n+1}+a^3-1\right) = a^m-a^{2n}.\] The RHS is negative under the assumption, but the LHS can be expressed as \[a\left((a^{n+1})+a(a^n+a^2)\right)-(a^n+a^2) = a(1-a)(a-a^n) > 0. \quad \blacksquare\]

Let $P(a)$ be the enumerator and $Q(a)$ be the denominator. Divide $P$ on $Q$: $$P=QT+R$$where $deg R<def Q$ and division is done in $\mathbb{Q}$. Multiply this equation by the lcm of denominators so that all coeffiecients were integer. Now $Pc$ is divisible by $Q$ and $(Tc)Q$ are divisible by $Q$ in infinitely many points from the problem statement, thus $Rc$ is also divisible by $Q$ in infinitely many points. But if $R \neq 0$, then eventually $|Rc| < |Q|$, so $R$ must be equal to zero. Hence $P$ is divisible by $Q$ Now $a^{m+1}+a^{m}-a^n=(a+1)P-Q \vdots Q$, but $(Q,a)=1$, thus $a^{m-n+1}+a^{m-n}-1 \vdots Q$. Denote $m-n=t$ Obviously $t+1 \geq$deg $Q=n$. Note that $Q(0)=-1$ and $Q(1)=1$, thus there exists a number $x_0 \in (0,1)$ such that $Q(x_0)=0$. Then $x_0^{t+1}+x_0^{t}=1=x_0^n+x_0^2$. Note that if $t>2$, then $x_0^{t+1} \leq x_0^n$ and $x_0^t<x_0^2$, contradicting the statement. Thus $t \leq 2$. But $n \leq t+1 \leq 3$, thus $n=3, t=2$, and $m=t+n=5$ To show that it works, just note that $x^5+x-1=(x^3+x^2-1)(x^2-x+1)$