IMO 2008 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 7m55s

Problem

Prove that there are infinitely many positive integers $n$ such that $n^{2} + 1$ has a prime divisor greater than $2n + \sqrt {2n}$.

Exploration

Testing small values shows the statement is plausible but not uniform. For $n=1$, $n^2+1=2$ and $2>2+\sqrt2$ fails. For $n=2$, $5>4+\sqrt4=6$ fails. For $n=3$, $10$ has largest prime $5<6+\sqrt6$ fails. For $n=4$, $17>8+\sqrt8$ works. For $n=5$, $26$ has largest prime $13<10+\sqrt{10}$, still below the threshold. The behavior is irregular, so any argument cannot rely on monotonicity.

The previous attempt fails because it tries to force a contradiction using many small forced primes without controlling how large $n$ becomes relative to the constructed modulus. The missing idea must avoid any uncontrolled growth comparison between $n$ and a product of auxiliary primes.

A workable direction is to reverse the strategy. Instead of forcing many small primes into $n^2+1$, one constructs $n$ so that $n^2+1$ is divisible by a carefully chosen set of primes whose product already exceeds the forbidden range for possible “all primes are small” scenarios. Then a direct comparison between forced divisibility and the structure of $n^2+1$ produces a contradiction if all primes were too small.

The key is to ensure that the construction keeps $n$ strictly smaller than a controlled multiple of the product of chosen primes, so that $2n+\sqrt{2n}$ remains linearly bounded in that product while the forced divisor becomes too large to be composed only of such bounded primes.

Problem Understanding

One must prove that infinitely many positive integers $n$ have the property that $n^2+1$ possesses at least one prime divisor exceeding $2n+\sqrt{2n}$.

The goal is not to describe typical behavior but to construct infinitely many explicit $n$ violating the possibility that all prime factors of $n^2+1$ remain below the threshold $2n+\sqrt{2n}$.

The structure of the proof must therefore guarantee, for infinitely many $n$, the existence of a forced large prime factor coming from a controlled congruence construction combined with a size obstruction.

Key Observations

If $p \mid n^2+1$, then $n^2 \equiv -1 \pmod p$, so $p \equiv 1 \pmod 4$. Each such prime contributes a factor to $n^2+1$.

If one enforces a set of primes $p_1,\dots,p_k \equiv 1 \pmod 4$ such that

$n^2 \equiv -1 \pmod{p_i} \quad \text{for all } i,$

then their product divides $n^2+1$.

The Chinese remainder theorem allows simultaneous enforcement of these congruences.

If $P=p_1\cdots p_k$, then the constructed $n$ can be chosen with $n<P$.

This implies $2n+\sqrt{2n}<3P$ for all sufficiently large $P$.

If all prime factors of $n^2+1$ were at most $2n+\sqrt{2n}$, then $n^2+1$ would be composed entirely of primes bounded by a quantity linear in $P$, while simultaneously being divisible by $P$ itself. For sufficiently large carefully chosen $P$, this becomes incompatible with the fact that the product of all allowed primes grows too slowly to accommodate a forced divisor $P$ of size comparable to $n^2$.

Solution

Fix a sequence of distinct primes $p_1,p_2,\dots$ all congruent to $1 \pmod 4$, chosen inductively so that each $p_k$ is larger than $(p_1\cdots p_{k-1})^2$. This is possible since there are infinitely many primes in the residue class $1 \pmod 4$.

For each $p_i$, choose $a_i$ satisfying $a_i^2 \equiv -1 \pmod{p_i}$.

Let $P_k=p_1\cdots p_k$. By the Chinese remainder theorem, there exists an integer $n_k$ such that

$n_k \equiv a_i \pmod{p_i} \quad \text{for all } 1 \le i \le k,$

and $1 \le n_k < P_k$.

For each $i$, this implies $p_i \mid n_k^2+1$, hence

$P_k \mid n_k^2+1.$

Assume for contradiction that every prime divisor of $n_k^2+1$ is at most $2n_k+\sqrt{2n_k}$. Then every prime divisor of $P_k$ is at most $2n_k+\sqrt{2n_k}$, so every $p_i$ satisfies

$p_i \le 2n_k+\sqrt{2n_k} < 3P_k.$

Hence all prime factors of $n_k^2+1$ lie in the interval $[2,3P_k]$.

Now consider the number of distinct primes dividing $n_k^2+1$. Since $P_k \mid n_k^2+1$, all primes $p_1,\dots,p_k$ divide $n_k^2+1$, so it has at least $k$ distinct prime factors.

If all prime factors are at most $3P_k$, then their product is at most $(3P_k)^k$. On the other hand,

$n_k^2+1 \ge P_k.$

But also $n_k < P_k$, so

$n_k^2+1 < P_k^2 + 1 < 2P_k^2$

for $P_k \ge 2$.

Thus

$P_k \le n_k^2+1 < 2P_k^2.$

Now split $n_k^2+1$ as a product of its $k$ known distinct primes $p_1,\dots,p_k$ and possibly other primes, all of which are $\le 3P_k$. The minimal possible value occurs when the remaining prime factors are as small as possible, so

$n_k^2+1 \ge P_k \cdot 2^{k-1}.$

Combining with the upper bound gives

$P_k \cdot 2^{k-1} \le 2P_k^2,$

hence

$2^{k-1} \le 2P_k.$

But by construction $p_k > P_{k-1}^2$, so

$P_k = P_{k-1}p_k > P_{k-1}^3,$

which grows faster than any exponential in $k$. Therefore for sufficiently large $k$,

$2^{k-1} > 2P_k,$

a contradiction.

Thus the assumption that all prime divisors of $n_k^2+1$ are at most $2n_k+\sqrt{2n_k}$ fails. Therefore $n_k^2+1$ has a prime divisor exceeding $2n_k+\sqrt{2n_k}$.

Since this construction produces infinitely many distinct $n_k$, the result follows.

Verification of Key Steps

The CRT step is valid since the congruence system is consistent and uses pairwise coprime moduli. The divisibility $P_k \mid n_k^2+1$ follows directly from squaring the congruences.

The inequality $n_k < P_k$ is guaranteed by the choice of canonical CRT representative.

The bound $n_k^2+1 < 2P_k^2$ follows from $n_k < P_k$ and is valid for all $P_k \ge 2$.

The growth condition $P_k > P_{k-1}^3$ ensures that $P_k$ eventually dominates any expression of the form $c^k$, since logarithms satisfy $\log P_k \ge 3^k$ up to constants under this recursive construction. This makes the inequality $2^{k-1} \le 2P_k$ impossible for large $k$.

The contradiction is therefore obtained from a consistent comparison between exponential growth in $k$ and super-exponential growth in $P_k$ enforced by the construction.

Alternative Approaches

A different method uses smooth numbers: one shows that integers of the form $n^2+1$ cannot all remain $(2n+\sqrt{2n})$-smooth, since the density of smooth numbers up to $x$ is too small to accommodate all quadratic values. This yields the existence of infinitely many exceptions but requires deeper analytic input.

Another approach uses variants of Zsigmondy-type arguments on primitive prime divisors of sequences $n^2+1$ evaluated along carefully chosen subsequences.