On prime factors of $n^2+1$

Solution 1:

In this answer I will prove that for any $\epsilon>0$, there are infinitely many primes $p$ with $p>(1-\epsilon)n\log n$ and $p\mid n^2+1$. The idea is to bound the product $$H(N)=\prod_{n\leq N}(n^{2}+1)$$ in two different ways, and is similar in spirit to Erdős' proof of Chebyshev's inequalities${}^{**}$.

Lower bound: Notice that $$H(N)\geq\prod_{n\leq N}n^{2}=(N!)^{2}\geq N^{2N}/e^{2N-2},$$ and so $$\log(H(N))\geq2N\log N-(2N-2). \ \ \ \ \ \ \ \ \ \ (1)$$

Upper bound: This is the meat of the argument. Lets assume that $H(N)$ has no prime divisor greater than a parameter $w$ which is chosen so that $w>N$. Our end goal is to show that $w$ cannot be too small, as this implies that $n^2+1$ will have large prime divisors for some $n$. Writing $H(N)$ as a product of primes, we have $$H(N)=\prod_{p\leq w}p^{\alpha_{p}}$$ for some coefficients $\alpha_{p}$. Each prime $p>x$ can divide $n^{2}+1$ for at most two different values of $n$, and so we see that $\alpha_{p}\leq2$ in this case. For $p\leq x$, if $p\mid n^{2}+1$, then $n^{2}\equiv-1\text{ mod }p$. This congruence can only be solved when $p\equiv1\text{ mod }4$, and in that case there will be at most $2\lceil N/p\rceil$ values of $n$ for which $p\mid n^{2}+1$. Similarly, if $p^{k}\mid n^{2}+1$, then $n^{2}\equiv-1\text{ mod }p^{k}$, and there are at most $\gcd(\phi(p^{k}),2)=2$ solutions to this congruence, and hence at most $2\lceil N/p^{k}\rceil$ values of $n$ for which $p^{k}\mid n^{2}+1$. Putting this all together, we find that for $p\leq N$, and $$p\equiv1\text{ mod }4 ,\alpha_{p}\leq2\left\lceil\frac{N}{p}\right\rceil+2\left\lceil\frac{N}{p^{2}}\right\rceil+2\left\lceil\frac{N}{p^{3}}\right\rceil+\cdots+2\left\lceil\frac{N}{p^{k}}\right\rceil$$ where $k=\left\lceil\log_{p}N\right\rceil.$ Using the upper bound $\left\lceil x\right\rceil\leq x+1,$ we obtain $$\alpha_{p}\leq\frac{2N}{p-1}+2\left(\log_{p}(N)+1\right)$$ since $1+\frac{1}{p}+\frac{1}{p^{2}}+\cdots+\frac{1}{p^{k}}\leq\frac{1}{1-1/p}.$ Thus, $$H(N)\leq\prod_{\begin{array}{c} p\leq N\\ p\equiv1\text{ mod }4 \end{array}}p^{\frac{2N}{p-1}+2\log_{p}(N)+2}\prod_{\begin{array}{c} N<p\leq w\\ p\equiv1\text{ mod }4 \end{array}}p^{2},$$ and so, noting that $p^{\log_{p}(N)}=N,$ we have $$H(N)\leq\prod_{\begin{array}{c} p\leq N\\ p\equiv1\text{ mod }4 \end{array}}N^{2}\prod_{\begin{array}{c} p\leq N\\ p\equiv1\text{ mod }4 \end{array}}p^{\frac{2N}{p-1}}\prod_{\begin{array}{c} p\leq w\\ p\equiv1\text{ mod }4 \end{array}}p^{2}.$$ Taking the logarithm it follows that $$\log H(N)\leq2\pi(N;4,1)\log N+2N\sum_{\begin{array}{c} p\leq N\\ p\equiv1\text{ mod }4 \end{array}}\frac{\log p}{p-1}+2\theta(w;4,1).$$ By using the prime number theorem for arithmetic progressions, we have the asymptotics $\sum_{p\leq N,\ p\equiv1\ (4)}\frac{\log p}{p-1}\sim\frac{1}{2}\log N$, $\theta(w;4,1)\sim w/2$ and $\pi(N;4,1)\log N\sim N/2$, and so $$\log H(N)\lesssim N\log N+w.\ \ \ \ \ \ \ \ \ \ (2)$$

Combining equations $(1)$ and $(2)$ together, it follows that $$2N\log N-(2N-2)\leq\log H(N)\lesssim N\log N+w,$$ and hence for $N>N_0(\epsilon)$ we must have $$(1-\epsilon)N\log N\leq w.$$ Since $w$ cannot be taken to smaller, this implies that for any $\epsilon>0$, we can take $N$ large enough so that there exists $p>(1-\epsilon)N\log N$ such that $p\mid H(N)$. It follows that for any $\epsilon>0$, there are infinitely many primes $p$ such that $$p>(1-\epsilon) n\log n \text{ and } p\mid n^{2}+1.$$

${}^{**}$ See these three answers for more details on proving Chebyshevs estimates in a similar fashion: Chebyshev: Proof $\prod \limits_{p \leq 2k}{\;} p > 2^k$, Are there any Combinatoric proofs of Bertrand's postulate? and How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?

For a similar question and solution, see this answer: Squares in $(\operatorname{rad}(1)^2+1)\cdot(\operatorname{rad}(2)^2+1)\ldots(\operatorname{rad}(n)^2+1)$

Solution 2:

Even better: Deshouillers and Iwaniec (1982) have shown that there are infinitely many positive integers $n$ such that $n^2+1$ has a prime factor greater than $n^{6/5}$.