IMO 1987 · Problem 6

Let \(n\) be an integer greater than or equal to \(2\). Prove that if \(k^2+k+n\) is prime for all integers \(k\) such that \(0\leq k\leq \sqrt{n/3}\), then \(k^2+k+n\) is prime for all integers \(k\) such that \(0\leq k\leq n-2\).

Official text of the problem. Official problem paper (PDF)

Solution

Write \(F(x)=x^2+x+n\). Suppose, for a contradiction, that some \(F(k)\) with \(0\leq k\leq n-2\) is composite, and choose the smallest such integer \(k\).

Since \(F(k)\) is composite, it has a prime divisor \(p\) satisfying \(p^2\leq F(k)\). Moreover, \[ p^2\leq F(k)\leq F(n-2)=n^2-2n+2<n^2, \] so \(p<n\).

Let \(r\) be the remainder when \(k\) is divided by \(p\), and put \[ t=\min\{r,p-1-r\}. \] Then \(t\) is an integer satisfying \[ 0\leq t\leq \frac{p-1}{2}. \] Also, \(t\equiv k\) or \(t\equiv -k-1\pmod p\). Since \[ F(-k-1)=F(k), \] we have \(p\mid F(t)\). But \(F(t)\geq n>p\), so \(F(t)\) is composite.

If \(t<k\), this contradicts the choice of \(k\). Consequently, \[ k\leq t\leq\frac{p-1}{2}, \qquad\text{hence}\qquad p\geq 2k+1. \] It follows that \[ k^2+k+n=F(k)\geq p^2\geq(2k+1)^2, \] and therefore \[ n\geq 3k^2+3k+1>3k^2. \] Thus \(0\leq k<\sqrt{n/3}\), where the hypothesis says that \(F(k)\) is prime—a contradiction.

Hence \(k^2+k+n\) is prime for every integer \(k\) with \(0\leq k\leq n-2\). \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).