37th Iranian Mathematical Olympiad

Question

P(x) = a_n x^n + a_n-1 x^n-1 + + a_1 x + a_0 with integer coefficients *primitive* if and only if gcd(a_n, a_n-1, , a_1, a_0) = 1. a) Let P(x) be a primitive polynomial with degree less than 1398 and S be a subset of primes greater than 1398. Prove that there is a positive integer n so that P(n) is not divisible by any prime in S. b) Prove that there exists a primitive polynomial P(x) with degree less than 1398 such that for each *natural* number n, P(n) is divisible by every prime less than 1398. $$

Accepted Answer

a) We know that for every polynomial P(x) with degree n, the equation P(x) 0 p has at most n distinct roots modulo p, for every prime number p. Then for every p_i S we have some t_i 1, 2, , p where p_i P(t_i). Now choose t by Chinese Remainder Theorem such that t t_i p_i. Then for every p_i S we have p_i P(t). b) Put P(x) = x(x - 1) (x - 1396) + 1398! Note that 1397 and 1398 are composite numbers. Then obviously for any p 1398 and n N there exists an a_i such that 1 a_i 1398 and n a_i p_i. Therefore p_i P(n) and since P(x) is monic it satisfies our desired conditions.