IMO 2008 · Problem 3

Prove that there exist infinitely many positive integers \(n\) such that \(n^2+1\) has a prime divisor which is greater than \(2n+\sqrt{2n}\).

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

Solution

Let \(N\) be an arbitrary positive integer. We will construct a suitable integer \(n>N\).

Put \[ A=(N^2+13)! \] and choose a prime divisor \(p\) of \(A^2+1\). Every prime at most \(N^2+13\) divides \(A\), so cannot divide \(A^2+1\). Consequently, \[ p>N^2+13. \]

Let \(r\) be the remainder when \(A\) is divided by \(p\). Since \(p\nmid A\), we have \(1\le r\le p-1\). Set \[ n=\min\{r,p-r\}. \] Then \(p\mid n^2+1\), and, since \(p\) is odd, \[ 1\le n\le \frac{p-1}{2}. \] Moreover, \[ n^2+1\ge p>N^2+13, \] so \(n>N\).

Now put \(d=p-2n\), a positive odd integer. We have \[ d^2+4=(p-2n)^2+4\equiv4(n^2+1)\equiv0\pmod p. \] Thus \(d^2+4\ge p>13\). As \(d\) is positive and odd, this forces \(d\ge5\). Therefore \[ d^2\ge p-4=2n+d-4>2n, \] and hence \[ p=2n+d>2n+\sqrt{2n}. \]

We have found such an \(n>N\) for every positive integer \(N\), proving that infinitely many exist. \(\square\)

The solution was checked against the official IMO shortlist solutions.