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 5 of 6: Set n = p - x: the bound and the divisibility both hold

Previous step Next step

n=p-x \le \tfrac12(p-h),\quad p\mid n^2+1

Detailed analysis

Set $n=p-x$ ; since $0<x<p$ , $n$ is a positive integer. From $x\ge\frac{p+h}2$ we get $n=p-x\le p-\frac{p+h}2=\frac{p-h}2$ , the bound needed in Step 1. Also $n\equiv-x\pmod p$ , so $n^2\equiv x^2\equiv-1\pmod p$ , i.e.\ $p\mid n^2+1$ .