IMO 2012 Shortlist N5

Category: Number Theory

Problem

For a nonnegative integer n define rad(n) = 1 if n = 0 or n = 1, and rad(n) = p1p2 ···pk where p1 < p2 < ··· < pk are all prime factors of n. Find all polynomials f(x) with nonnegative integer coefficients such that rad(f(n)) divides rad(f(nrad(n) )) for every nonnegative integer n. Solution 1. We are going to prove that f(x) = axm for some nonnegative integers a and m. If f(x) is the zero polynomial we are done, so assume that f(x) has at least one positive coefficient. In particular f(1) > 0. Let p be a prime number. The condition is that f(n) ≡ 0 (mod p) implies f(nrad(n) ) ≡ 0 (mod p). (1) Since rad(nrad(n)k ) = rad(n) for all k, repeated applications of the preceding implication show that if p divides f(n) then f(nrad(n)k ) ≡ 0 (mod p) for all k. The idea is to construct a prime p and a positive integer n such that p − 1 divides n and p divides f(n). In this case, for k large enough p − 1 divides rad(n)k . Hence if (p,n) = 1 then nrad(n)k ≡ 1 (mod p) by Fermat’s little theorem, so that f(1) ≡ f(nrad(n)k ) ≡ 0 (mod p). (2) Suppose that f(x) = g(x)xm with g(0) 6= 0. Let t be a positive integer, p any prime factor of g(−t) and n = (p−1)t. So p−1 divides n and f(n) = f((p − 1)t) ≡ f(−t) ≡ 0 (mod p), hence either (p,n) > 1 or (2) holds. If (p,(p−1)t) > 1 then p divides t and g(0) ≡ g(−t) ≡ 0 (mod p), meaning that p divides g(0). In conclusion we proved that each prime factor of g(−t) divides g(0)f(1) 6= 0, and thus the set of prime factors of g(−t) when t ranges through the positive integers is finite. This is known to imply that g(x) is a constant polynomial, and so f(x) = axm . Solution 2. Let f(x) be a polynomial with integer coefficients (not necessarily nonnegative) such that rad(f(n)) divides rad(f(nrad(n) )) for any nonnegative integer n. We give a complete description of all polynomials with this property. More precisely, we claim that if f(x) is such a polynomial and ξ is a root of f(x) then so is ξd for every positive integer d. Therefore each root of f(x) is zero or a root of unity. In particular, if a root of unity ξ is a root of f(x) then 1 = ξd is a root too (for some positive integer d). In the original problem f(x) has nonnegative coefficients. Then either f(x) is the zero polynomial or f(1) > 0 and ξ = 0 is the only possible root. In either case f(x) = axm with a and m nonnegative integers. To prove the claim let ξ be a root of f(x), and let g(x) be an irreducible factor of f(x) such that g(ξ) = 0. If 0 or 1 are roots of g(x) then either ξ = 0 or ξ = 1 (because g(x) is irreducible) and we are done. So assume that g(0),g(1) 6= 0. By decomposing d as a product of prime numbers, it is enough to consider the case d = p prime. We argue for p = 2. Since rad(2k ) = 2 for every k, we have rad(f(2k )) | rad(f(22k )). Now we prove that g(x) divides f(x2 ). Suppose that this is not the case. Then, since g(x) is irreducible, there are integer-coefficient polynomials a(x), b(x) and an integer N such that a(x)g(x) + b(x)f(x2 ) = N. (3) Each prime factor p of g(2k ) divides f(2k ), so by rad(f(2k ))|rad(f(22k )) it also divides f(22k ). From the equation above with x = 2k it follows that p divides N.47 In summary, each prime divisor of g(2k ) divides N, for all k ≥ 0. Let p1,...,pn be the odd primes dividing N, and suppose that g(1) = 2α pα1 1 ···pαn n . If k is divisible by ϕ(pα1+1 1 ···pαn+1 n ) then 2k ≡ 1 (mod pα1+1 1 ···pαn+1 n ), yielding g(2k ) ≡ g(1) (mod pα1+1 1 ···pαn+1 n ). It follows that for each i the maximal power of pi dividing g(2k ) and g(1) is the same, namely pαi i . On the other hand, for large enough k, the maximal power of 2 dividing g(2k ) and g(0) 6= 0 is the same. From the above, for k divisible by ϕ(pα1+1 1 ···pαn+1 n ) and large enough, we obtain that g(2k ) divides g(0) · g(1). This is impossible because g(0),g(1) 6= 0 are fixed and g(2k ) is arbitrarily large. In conclusion, g(x) divides f(x2 ). Recall that ξ is a root of f(x) such that g(ξ) = 0; then f(ξ2 ) = 0, i. e. ξ2 is a root of f(x). Likewise if ξ is a root of f(x) and p an arbitrary prime then ξp is a root too. The argument is completely analogous, in the proof above just replace 2 by p and “odd prime” by “prime different from p.” Comment. The claim in the second solution can be proved by varying n (mod p) in (1). For instance, we obtain f(nrad(n+pk) ) ≡ 0 (mod p) for every positive integer k. One can prove that if (n,p) = 1 then rad(n+pk) runs through all residue classes r (mod p − 1) with (r,p − 1) squarefree. Hence if f(n) ≡ 0 (mod p) then f(nr) ≡ 0 (mod p) for all integers r. This implies the claim by an argument leading to the identity (3).48