Problem 3

Prove that there are infinitely many positive integers

n

such that

n^2+1

has a prime factor greater than

2n+\sqrt{2n}

Step 1 of 6: Strategy: fix the prime p first and look for a suitable n below it

Previous step Next step

In plain words

Instead of hunting for $n$ and hoping $n^2+1$ has a large prime factor, we reverse the search: pick the prime $p$ first, then build $n$ so that $p$ divides $n^2+1$ and $n$ is small enough that $p$ already exceeds $2n+\sqrt{2n}$ .

p \equiv 1 \pmod 8,\quad h=\lceil\sqrt p\rceil,\quad n\le\tfrac12(p-h),\ p\mid n^2+1 \implies p\ge 2n+\sqrt{2n}

Detailed analysis

Fix any prime $p\equiv1\pmod8$ with $p\ge2013$ , and let $h=\lceil\sqrt p\rceil$ . We aim to find a positive integer $n\le\frac12(p-h)$ with $p\mid n^2+1$ . If we succeed, then $p\ge 2n+h\ge 2n+\sqrt p$ ; since $n\le\frac12(p-h)<\frac p2$ , we get $2n<p$ , so $\sqrt{2n}<\sqrt p\le h$ , hence $p\ge2n+h>2n+\sqrt{2n}$ . So $p$ itself is a prime factor of $n^2+1$ exceeding $2n+\sqrt{2n}$ , exactly as required.