Category: Algebra

Problem

Let f and g be two nonzero polynomials with integer coefficients and degf > degg. Suppose that for infinitely many primes p the polynomial pf + g has a rational root. Prove that f has a rational root. Solution 1. Since degf > degg, we have |g(x)/f(x)| < 1 for sufficiently large x; more precisely, there is a real number R such that |g(x)/f(x)| < 1 for all x with |x| > R. Then for all such x and all primes p we have pf(x) + g(x) ≥ f(x) p − |g(x)| |f(x)|

Hence all real roots of the polynomials pf + g lie in the interval [−R,R]. Let f(x) = anxn

an−1xn−1
··· + a0 and g(x) = bmxm
bm−1xm−1
··· + b0 where n > m, an 6= 0 and bm 6= 0. Upon replacing f(x) and g(x) by an−1 n f(x/an) and an−1 n g(x/an) respectively, we reduce the problem to the case an = 1. In other words one can assume that f is monic. Then the leading coefficient of pf +g is p, and if r = u/v is a rational root of pf +g with (u,v) = 1 and v > 0, then either v = 1 or v = p. First consider the case when v = 1 infinitely many times. If v = 1 then |u| ≤ R, so there are only finitely many possibilities for the integer u. Therefore there exist distinct primes p and q for which we have the same value of u. Then the polynomials pf + g and qf + g share this root, implying f(u) = g(u) = 0. So in this case f and g have an integer root in common. Now suppose that v = p infinitely many times. By comparing the exponent of p in the denominators of pf(u/p) and g(u/p) we get m = n − 1 and pf(u/p) + g(u/p) = 0 reduces to an equation of the form un
an−1pun−1
... + a0pn

bn−1un−1

bn−2pun−2
... + b0pn−1 = 0. The equation above implies that un
bn−1un−1 is divisible by p and hence, since (u,p) = 1, we have u + bn−1 = pk with some integer k. On the other hand all roots of pf + g lie in the interval [−R,R], so that |pk − bn−1| p = |u| p < R, |k| < R + |bn−1| p < R + |bn−1|. Therefore the integer k can attain only finitely many values. Hence there exists an integer k such that the number pk−bn−1 p = k − bn−1 p is a root of pf + g for infinitely many primes p. For these primes we have f k − bn−1 p

p g k − bn−1 p = 0. So the equation f (k − bn−1x) + xg (k − bn−1x) = 0 (1) has infinitely many solutions of the form x = 1/p. Since the left-hand side is a polynomial, this implies that (1) is a polynomial identity, so it holds for all real x. In particular, by substituting x = 0 in (1) we get f(k) = 0. Thus the integer k is a root of f. In summary the monic polynomial f obtained after the initial reduction always has an integer root. Therefore the original polynomial f has a rational root.14 Solution 2. Analogously to the first solution, there exists a real number R such that the complex roots of all polynomials of the form pf + g lie in the disk |z| ≤ R. For each prime p such that pf + g has a rational root, by Gauss’ lemma pf + g is the product of two integer polynomials, one with degree 1 and the other with degree degf − 1. Since p is a prime, the leading coefficient of one of these factors divides the leading coefficient of f. Denote that factor by hp. By narrowing the set of the primes used we can assume that all polynomials hp have the same degree and the same leading coefficient. Their complex roots lie in the disk |z| ≤ R, hence Vieta’s formulae imply that all coefficients of all polynomials hp form a bounded set. Since these coefficients are integers, there are only finitely many possible polynomials hp. Hence there is a polynomial h such that hp = h for infinitely many primes p. Finally, if p and q are distinct primes with hp = hq = h then h divides (p − q)f. Since degh = 1 or degh = degf − 1, in both cases f has a rational root. Comment. Clearly the polynomial h is a common factor of f and g. If degh = 1 then f and g share a rational root. Otherwise degh = degf −1 forces degg = degf −1 and g divides f over the rationals. Solution 3. Like in the first solution, there is a real number R such that the real roots of all polynomials of the form pf + g lie in the interval [−R,R]. Let p1 < p2 < ··· be an infinite sequence of primes so that for every index k the polynomial pkf + g has a rational root rk. The sequence r1,r2,... is bounded, so it has a convergent subsequence rk1,rk2,.... Now replace the sequences (p1,p2,...) and (r1,r2,...) by (pk1,pk2,...) and (rk1,rk2,...); after this we can assume that the sequence r1,r2,... is convergent. Let α = lim k→∞ rk. We show that α is a rational root of f. Over the interval [−R,R], the polynomial g is bounded, |g(x)| ≤ M with some fixed M. Therefore |f(rk)| = f(rk) − pkf(rk) + g(rk) pk

|g(rk)| pk ≤ M pk → 0, and f(α) = f lim k→∞ rk = lim k→∞ f(rk) = 0. So α is a root of f indeed. Now let uk, vk be relative prime integers for which rk = uk vk . Let a be the leading coefficient of f, let b = f(0) and c = g(0) be the constant terms of f and g, respectively. The leading coefficient of the polynomial pkf + g is pka, its constant term is pkb + c. So vk divides pka and uk divides pkb + c. Let pkb + c = ukek (if pkb + c = uk = 0 then let ek = 1). We prove that α is rational by using the following fact. Let (pn) and (qn) be sequences of integers such that the sequence (pn/qn) converges. If (pn) or (qn) is bounded then lim(pn/qn) is rational. Case 1: There is an infinite subsequence (kn) of indices such that vkn divides a. Then (vkn) is bounded, so α = limn→∞(ukn/vkn) is rational. Case 2: There is an infinite subsequence (kn) of indices such that vkn does not divide a. For such indices we have vkn = pkndkn where dkn is a divisor of a. Then α = lim n→∞ ukn vkn = lim n→∞ pknb + c pkndknekn = lim n→∞ b dknekn

lim n→∞ c pkndknekn = lim n→∞ b dknekn . Because the numerator b in the last limit is bounded, α is rational.15

IMO 2012 Shortlist A4

Problem