IMC 2006 · Day 1 · P4

Let $S$ be an infinite set of integers such that rational function $f(x)$ is integral for all $x \in S$. Suppose that $f(x) = p(x)/q(x)$ where $p$ is a polynomial of degree $k$ and $q$ is a polynomial of degree $n$. Then $p, q$ are solutions to the simultaneous equations $p(x) = q(x) f(x)$ for all $x \in S$ that are not roots of $q$. These are linear simultaneous equations in the coefficients of $p, q$ with rational coefficients. Since they have a solution, they have a rational solution.

Thus there are polynomials $p', q'$ with rational coefficients such that $p'(x) = q'(x) f(x)$ for all $x \in S$ that are not roots of $q$. Multiplying this with the previous equation, we see that $p'(x) q(x) f(x) = p(x) q'(x) f(x)$ for all $x \in S$ that are not roots of $q$. If $x$ is not a root of $p$ or $q$, then $f(x) \ne 0$, and hence $p'(x) q(x) = p(x) q'(x)$ for all $x \in S$ except for finitely many roots of $p$ and $q$. Thus the two polynomials $p' q$ and $p q'$ are equal for infinitely many choices of value. Thus $p'(x) q(x) = p(x) q'(x)$. Dividing by $q(x) q'(x)$, we see that $p'(x)/q'(x) = p(x)/q(x) = f(x)$. Thus $f(x)$ can be written as the quotient of two polynomials with rational coefficients. Multiplying up by some integer, it can be written as the quotient of two polynomials with integer coefficients.

Suppose $f(x) = p''(x)/q''(x)$ where $p''$ and $q''$ both have integer coefficients. Then by Euler's division algorithm for polynomials, there exist polynomials $s$ and $r$, both of which have rational coefficients such that $p''(x) = q''(x) s(x) + r(x)$ and the degree of $r$ is less than the degree of $q''$. Dividing by $q''(x)$, we get that $f(x) = s(x) + r(x)/q''(x)$. Now there exists an integer $N$ such that $N s(x)$ has integral coefficients. Then $N f(x) - N s(x)$ is an integer for all $x \in S$. However, this is equal to the rational function $N r / q''$, which has a higher degree denominator than numerator, so tends to 0 as $x$ tends to $\infty$. Thus for all sufficiently large $x \in S$, $N f(x) - N s(x) = 0$ and hence $r(x) = 0$. Thus $r$ has infinitely many roots, and is 0. Thus $f(x) = s(x)$, so $f$ is a polynomial.