uniolympiads Ελληνικά

IMC 2006, Day 1, Problem 4

Let ff be a rational function (i.e. the quotient of two real polynomials) and suppose that f(n)f(n) is an integer for infinitely many integers nn. Prove that ff is a polynomial.

Original from the official PDFLet f be a rational function (i.e. the quotient of two real polynomials) and suppose that f (n) is an integer for infinitely many integers n. Prove that f is a polynomial. (20 points)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Let SS be an infinite set of integers such that rational function f(x)f(x) is integral for all x∈Sx\in S.

Suppose that f(x)=p(x)/q(x)f(x)=p(x)/q(x) where pp is a polynomial of degree kk and qq is a polynomial of degree nn. Then p,qp,q are solutions to the simultaneous equations p(x)=q(x)f(x)p(x)=q(x)f(x) for all x∈Sx\in S that are not roots of qq. These are linear simultaneous equations in the coefficients of p,qp,q with rational coefficients. Since they have a solution, they have a rational solution.

Thus there are polynomials p′,q′p',q' with rational coefficients such that p′(x)=q′(x)f(x)p'(x)=q'(x)f(x) for all x∈Sx\in S that are not roots of qq. Multiplying this with the previous equation, we see that p′(x)q(x)f(x)=p(x)q′(x)f(x)p'(x)q(x)f(x)=p(x)q'(x)f(x) for all x∈Sx\in S that are not roots of qq. If xx is not a root of pp or qq, then f(x)≠0f(x)\ne0, and hence p′(x)q(x)=p(x)q′(x)p'(x)q(x)=p(x)q'(x) for all x∈Sx\in S except for finitely many roots of pp and qq. Thus the two polynomials p′qp'q and pq′pq' are equal for infinitely many choices of value. Thus p′(x)q(x)=p(x)q′(x)p'(x)q(x)=p(x)q'(x). Dividing by q(x)q′(x)q(x)q'(x), we see that p′(x)/q′(x)=p(x)/q(x)=f(x)p'(x)/q'(x)=p(x)/q(x)=f(x). Thus f(x)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)f(x)=p''(x)/q''(x) where p′′p'' and q′′q'' both have integer coefficients. Then by Euler's division algorithm for polynomials, there exist polynomials ss and rr, both of which have rational coefficients such that p′′(x)=q′′(x)s(x)+r(x)p''(x)=q''(x)s(x)+r(x) and the degree of rr is less than the degree of q′′q''. Dividing by q′′(x)q''(x), we get that f(x)=s(x)+r(x)/q′′(x)f(x)=s(x)+r(x)/q''(x). Now there exists an integer NN such that Ns(x)Ns(x) has integral coefficients. Then Nf(x)−Ns(x)Nf(x)-Ns(x) is an integer for all x∈Sx\in S. However, this is equal to the rational function Nr/q′′Nr/q'', which has a higher degree denominator than numerator, so tends to 0 as xx tends to ∞\infty. Thus for all sufficiently large x∈Sx\in S, Nf(x)−Ns(x)=0Nf(x)-Ns(x)=0 and hence r(x)=0r(x)=0. Thus rr has infinitely many roots, and is 0. Thus f(x)=s(x)f(x)=s(x), so ff is a polynomial.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?