Cím:	Solution to a problem of the 43rd International Mathematical Olympiad
Füzet:	2003/októberi melléklet, 3 - 5. oldal	PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   3. Determine all pairs $\left(m\mathrm{,}n\right)$ of integers $m\mathrm{,}n\ge 3$, such that there exist infinitely many positive integers $a$ for which $\begin{array}{c}{\displaystyle \frac{a^m+a-1}{a^n+a^2-1}}\end{array}$ is an integer.   Solution by B. A. Rácz. Let $\text{p}\left(x\right)=x^m+x-1$ and $\text{q}\left(x\right)=x^n+x^2-1$. First we shall prove that if the condition of the problem is satisfied by a pair $\left(m\mathrm{,}n\right)$ then the denominator as a polynomial is a divisor of the numerator, that is $\text{q}\left(x\right)\mid \text{p}\left(x\right)$. Let us divide the polynomial $\text{p}\left(x\right)$ by $\text{q}\left(x\right)$, that is, let $\begin{array}{c}{\displaystyle \text{p}\left(x\right)=\text{h}\left(x\right)\cdot \text{q}\left(x\right)+\text{r}\left(x\right)\mathrm{,}}\end{array}$ where either $r\left(x\right)$ is zero or the degree of the remainder is smaller than that of the divisor: $\text{deg}\text{r}<\text{deg}\text{q}$. Since the leading coefficient of the divisor is 1, the quotient and remainder both have integer coefficients. According to the condition, it is true for infinitely many integers $a$ that $\begin{array}{c}{\displaystyle \frac{\text{p}\left(a\right)}{\text{q}\left(a\right)}=\text{h}\left(a\right)+\frac{\text{r}\left(a\right)}{\text{q}\left(a\right)}}\end{array}$ is an integer. It follows from the relation of the degrees that $\frac{\text{r}\left(a\right)}{\text{q}\left(a\right)}\to 0$ as $|a|\to \infty$, and thus the value of this ratio must be 0 for infinitely many integers $a$. This is also true for the numerator, and if the value of the polynomial is 0 at infinitely many points then it must be identically zero. Thus the polynomial $\text{r}\left(x\right)$ is identically zero, and $\text{q}\left(x\right)$ is a divisor of the polynomial $\text{p}\left(x\right)$. Since the divisibility cannot hold if $m<n$, we can assume that $m\ge n$. Then the polynomial $\text{q}\left(x\right)$ also divides the polynomial $\begin{array}{c}{\displaystyle \left(x+1\right)\cdot \text{p}\left(x\right)-\text{q}\left(x\right)=x^n\left(x^{m-n+1}+x^{m-n}-1\right)\mathrm{.}}\end{array}$ Since $x^n$ and $x^n+x^2-1$ are coprime and the second factor is also a polynomial according to the assumption, it follows that $\begin{array}{c}{\displaystyle x^n+x^2-1\mid x^{m-n+1}+x^{m-n}-1.}\end{array}$ Let $k=m-n$. Then $k\ge 0$, $\text{q}\left(x\right)=x^n+x^2-1\mid x^{k+1}+x^k-1$ and it is clear that $k+1\ge n$. Since $\text{q}\left(x\right)$ is a continuous function and $\text{q}\left(0\right)<0<\text{q}\left(1\right)$, there exists a number $0<\alpha <1$, such that $\text{q}\left(\alpha \right)=0$, that is ${\alpha }^n+{\alpha }^2=1$. Hence it follows from the divisibility $\text{q}\left(x\right)\mid x^{k+1}+x^k-1$ that ${\alpha }^{k+1}+{\alpha }^k=1$, and thus $\begin{array}{c}{\displaystyle {\alpha }^n+{\alpha }^2={\alpha }^{k+1}+{\alpha }^k=1.}\end{array}$ (*) If $k=1$, the second equality cannot be true for any real $\alpha$. If $k\ge 2$ then $n\ge 3$ and thus with the condition $k+1\ge n$ above, we have $\begin{array}{c}{\displaystyle k\ge n-1\ge 2.}\end{array}$ Since $0<\alpha <1$, it follows that ${\alpha }^n\ge {\alpha }^{k+1}$ and ${\alpha }^2\ge {\alpha }^k$. With $\left(*\right)$, this can happen only if ${\alpha }^n={\alpha }^{k+1}$ and ${\alpha }^2={\alpha }^k$, that is for $n=k+1$ and $2=k$, which makes $m=5$ and $n=3$. For this number pair, on the other hand, $a^5+a-1=\left(a^3+a^2-1\right)\left(a^2-a+1\right)$. If $a$ is a positive integer then $a^3+a^2-1\ge 1+1-1>0$, and thus $\begin{array}{c}{\displaystyle \frac{a^5+a-1}{a^3+a^2-1}=a^2-a+\mathrm{1,}}\end{array}$ which is an integer for every positive integer $a$. There is one single pair of numbers satisfying the conditions of the problem, namely the pair $\left(\mathrm{5,3}\right)$.