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 2 of 6: Choose x with x^2 = -1 mod p in the upper half of the residues

Previous step Next step

p\equiv1\pmod4 \implies \exists\, x\in(\tfrac p2,p),\ x^2\equiv-1\pmod p; \quad x=\tfrac{p+1}2+t,\ t\ge0

Detailed analysis

Since $p\equiv1\pmod8$ implies $p\equiv1\pmod4$ , the number $-1$ is a quadratic residue mod $p$ , so some integer squares to $-1\pmod p$ ; among its two square roots mod $p$ (which sum to $p$ ), choose the one $x$ with $\frac p2<x<p$ . Write $x=\frac{p+1}2+t$ for an integer $t\ge0$ .