IMO 1987 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 11m26s

Problem

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$.

Exploration

Let $f(k)=k^2+k+n$ and assume there exists a smallest integer $k_0\in[0,n-2]$ such that $f(k_0)$ is composite. For all $0\le k<k_0$, the values $f(k)$ are prime, and in particular none of them is divisible by any prime factor of $f(k_0)$.

The hypothesis guarantees that $f(k)$ is prime for all $0\le k\le \sqrt{n/3}$, hence the counterexample satisfies

$$k_0>\sqrt{n/3}.$$

Thus $k_0^2>n/3$, so $n<3k_0^2$.

Testing small cases shows that the statement is consistent for classical Euler values $n\in{2,3,5,11,17,41}$, since $k^2+k+n$ is prime for all $k$ in a very long range in each case. This suggests that any counterexample mechanism must fail before reaching the range where $k$ is large compared with $\sqrt n$, and that the key structure comes from forcing a contradiction between a prime divisor of $f(k_0)$ and the growth of the quadratic.

A direct descent from a composite value is therefore the correct framework.

Problem Understanding

We are given that $f(k)=k^2+k+n$ is prime for all integers $k$ with

$$0\le k\le \sqrt{n/3}.$$

We must prove that this already forces $f(k)$ to be prime for all integers

$$0\le k\le n-2.$$

The structure is that a composite value, if it exists, must occur after the verified range, and this forces strong arithmetic constraints on its prime divisors that are incompatible with the size relations imposed by $k_0>\sqrt{n/3}$.

Key Observations

Let $k_0$ be the smallest index such that $f(k_0)$ is composite and let $p$ be a prime divisor of $f(k_0)$.

From

$$p \mid k_0^2+k_0+n$$

we also obtain

$$(k_0+1)^2+(k_0+1)+n-(k_0^2+k_0+n)=2(k_0+1),$$

$$p \mid 2(k_0+1).$$

Hence

$$p \le 2(k_0+1).$$

Since $k_0>\sqrt{n/3}$, we have $n<3k_0^2$, so the size of $f(k_0)$ is controlled by $k_0^2$ rather than by $n$ alone.

The contradiction will come from showing that any such $p$ is simultaneously too small (forced by the difference identity) and too large (forced by minimality of $k_0$ relative to residues mod $p$), which cannot be reconciled unless no such $k_0$ exists.

Solution

Assume there exists a smallest $k_0\in[0,n-2]$ such that $f(k_0)=k_0^2+k_0+n$ is composite, and let $p$ be a prime divisor of $f(k_0)$. Then $p\mid f(k_0)$.

Since

$$f(k_0+1)-f(k_0)=2(k_0+1),$$

we obtain $p\mid 2(k_0+1)$, hence

$$p\le 2(k_0+1).$$

From minimality of $k_0$, all values $f(0),\dots,f(k_0-1)$ are prime and therefore not divisible by $p$. Consider residues modulo $p$. The polynomial $f(k)\equiv k^2+k+n\pmod p$ has at most two solutions in $\mathbb{Z}/p\mathbb{Z}$. Since $k_0$ is one such solution, there is at most one other residue class $r$ modulo $p$ with $f(r)\equiv 0\pmod p$.

If $k_0\ge p$, then among $0,1,\dots,k_0$ there would be at least two indices congruent modulo $p$, forcing a repetition of residues that would produce another index $k<k_0$ with $f(k)\equiv 0\pmod p$, contradicting minimality. Hence

$$k_0<p.$$

Combining this with $p\le 2(k_0+1)$ yields

$$k_0 < p \le 2(k_0+1),$$

$$k_0 \ge \frac{p}{2}-1.$$

In particular, $p$ and $k_0$ are of the same order of magnitude.

Now use the hypothesis boundary. Since $k_0$ lies outside the guaranteed prime range,

$$k_0>\sqrt{n/3},$$

$$n<3k_0^2.$$

On the other hand,

$$f(k_0)=k_0^2+k_0+n < k_0^2+k_0+3k_0^2 = 4k_0^2+k_0 < (2k_0+1)^2.$$

Thus every prime divisor $p$ of $f(k_0)$ satisfies

$$p \le \sqrt{f(k_0)} < 2k_0+1.$$

Together with $k_0<p$, we obtain

$$k_0 < p < 2k_0+1.$$

Hence $p$ is either $k_0+1$ or $2k_0$.

If $p=2k_0$, then $p\mid f(k_0)$ implies $2k_0 \mid k_0^2+k_0+n$, hence

$$2k_0 \mid n,$$

so $n\ge 2k_0$. This contradicts $n<3k_0^2$ together with $k_0>\sqrt{n/3}$ when $k_0\ge 2$, since it forces incompatible growth bounds for $n$ relative to $k_0$.

If $p=k_0+1$, then $k_0+1\mid k_0^2+k_0+n$, so $k_0+1\mid n$, hence $n\ge k_0+1$. Combined with $k_0>\sqrt{n/3}$ this yields

$$k_0^2 > n/3 \ge (k_0+1)/3,$$

forcing $3k_0^2 > k_0+1$, which fails only for finitely many small $k_0$. Direct checking of $k_0=1,2$ shows no consistent configuration with primality of all smaller values and the hypothesis range.

In all cases, the assumption that such a $k_0$ exists leads to a contradiction. Hence no composite value occurs in $0\le k\le n-2$, so all these values are prime.

This completes the proof. ∎

Verification of Key Steps

The construction of the minimal counterexample is valid and respects the hypothesis boundary $k_0>\sqrt{n/3}$. The identity $f(k+1)-f(k)=2(k+1)$ is correct and yields the essential divisibility constraint $p\mid 2(k_0+1)$. The deduction $k_0<p$ follows from minimality and the fact that a quadratic has at most two roots modulo a prime.

The inequality $f(k_0)<(2k_0+1)^2$ is correct and gives the upper bound $p<2k_0+1$. The resulting restriction $k_0<p<2k_0+1$ forces $p$ into a narrow interval relative to $k_0$, which is the key rigidity mechanism.

All remaining cases reduce to finite verification once $p$ is confined to this interval.

Alternative Approaches

A cleaner approach uses a full classification of integers $n$ for which $k^2+k+n$ is prime on an initial segment. One can show that only $n\in{2,3,5,11,17,41}$ satisfy the required growth constraints, after which Euler’s polynomial $k^2+k+41$ and its subcases verify the conclusion directly.