2008 IMO Problems/Problem 3

Problem 3

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

Solution

The main idea is to take a gaussian prime $a+bi$ and multiply it by a "twice as small" $c+di$ to get $n+i$ . The rest is just making up the little details.

For each sufficiently large prime $p$ of the form $4k+1$ , we shall find a corresponding $n$ satisfying the required condition with the prime number in question being $p$ . Since there exist infinitely many such primes and, for each of them, $n \ge \sqrt{p-1}$ , we will have found infinitely many distinct $n$ satisfying the problem.

Take a prime $p$ of the form $4k+1$ and consider its "sum-of-two squares" representation $p=a^2+b^2$ , which we know to exist for all such primes. As $a\ne b$ , assume without loss of generality that $b>a$ . If $a=1$ , then $n=b$ is what we are looking for, and $p=n^2+1 > 2n+\sqrt{2n}$ as long as $p$ (and hence $n$ ) is large enough. Assume from now on that $b>a>1$ .

Since $a$ and $b$ are (obviously) co-prime, there must exist integers $c$ and $d$ such that $ad+bc=1 \leqno{(1)}$ In fact, if $c$ and $d$ are such numbers, then $c\pm ma$ and $d\mp mb$ work as well for any integer $m$ , so we can assume that $c \in \left[-\frac{a}{2}, \frac{a}{2}\right]$ .

Define $n=|ac-bd|$ and let's see why this was a good choice. For starters, notice that $(a^2+b^2)(c^2+d^2)=n^2+1$ .

If $c=\pm\frac{a}{2}$ , then from (1), we see that $a$ must divide $2$ and hence $a=2$ . In turn, $d=-\frac{b-1}{2}$ and $n=\frac{b(b-1)}{2}-2$ . Therefore, $b^2-b=2n+4>2n$ and so $\left(b-\frac{1}{2}\right)^2>2n$ , from where $b > \sqrt{2n}+\frac{1}{2}$ . Finally, $p=b^2+2^2 > 2n+\sqrt{2n}$ and the case $c=\pm\frac{a}{2}$ is cleared.

We can safely assume now that $|c| \le \frac{a-1}{2}.$ As $b>a>1$ implies $b>2$ , we have $|d| = \left|\frac{1-bc}{a}\right| \le \frac{b(a-1)+2}{2a} < \frac{ba}{2a} = \frac{b}{2},$ so $|d| \le \frac{b-1}{2}.$

$n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right).\label{(2)}$

Before we proceed, we would like to show that $a+b-1 > \sqrt{p}$ . Observe that the function $x+\sqrt{p-x^2}$ over $x\in(2,\sqrt{p-4})$ reaches its minima on the ends, so $a+b$ given $a^2+b^2=p$ is minimized for $a = 2$ , where it equals $2+\sqrt{p-2^2}$ . So we want to show that $2+\sqrt{p-4} > \sqrt{p} + 1,$ which obviously holds for large $p$ .