IMO 1987 SL 20

Origin: USS

Problem

Let f(x) = x2 + x + p, p \inN. Prove that if the numbers f(0), f(1), . . . , f([ p/3 ]) are primes, then all the numbers f(0), f(1), . . . , f(p −2) are primes.

Solution

Let y be the smallest nonnegative integer with y \leqp −2 for which f(y) is a composite number. Denote by q the smallest prime divisor of f(y). We claim that y < q. Suppose the contrary, that y \geqq. Let r be a positive integer such that y \equivr (mod q). Then f(y) \equivf(r) \equiv0 (mod q), and since q \leqy \leqp −2 \leq f(r), we conclude that q | f(r), which is a contradiction to the minimality of y. Now, we will prove that q > 2y. Suppose the contrary, that q \leq2y. Since f(y) −f(x) = (y −x)(y + x + 1), we observe that f(y) −f(q −1 −y) = (2y −q + 1)q, from which it follows that f(q −1 −y) is divisible by q. But by the assumptions, q −1 −y < y, implying that f(q −1 −y) is prime and therefore equal to q. This is impossible, because

f(q −1 −y) = (q −1 −y)2 + (q −1 −y) + p > q + p −y −1 \geqq. Therefore q \geq2y + 1. Now, since f(y), being composite, cannot be equal to q, and q is its smallest prime divisor, we obtain that f(y) \geqq2. Conse- quently, y2 + y + p \geqq2 \geq(2y + 1)2 = 4y2 + 4y + 1 ⇒3(y2 + y) \leqp −1, and from this we easily conclude that y <

p/3, which contradicts the condition of the problem. In this way, all the numbers f(0), f(1), . . ., f(p −2) must be prime.