# On prime factors of $n^2+1$

It is a well-known conjecture that there are infinitely many primes of the form $n^2+1$. However, there are weaker results that one can prove. For example,

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

This was Problem N6 in IMO 2008 Shortlist. See solution here (in page 50). It is remarked there that by tools of analytic number theory (using distribution of prime numbers of the form $4k+1$ somehow), one can show something considerably stronger, namely:

Theorem. There are infinitely many positive integers $n$ such that $n^2+1$ has a prime divisor greater than $n\log(n)$.

I would appreciate if someone gave a proof of the Theorem or provide a reference where it is proved.

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)$

• Thank you very much! I think this might have been the intended solution for this problem. – Prism Dec 3 '13 at 19:49

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}$.

• Thanks Matthew! Very nice reference. That said, I hope to see somewhat more elementary argument for $n\log(n)$. :) – Prism Dec 2 '13 at 22:31
• Take a look at this paper matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7432.pdf and its references. Chebysheff and/or Nagell may have what you want, but I can't find an online copy of their proofs. – Matthew Conroy Dec 2 '13 at 23:15
• This paper is perhaps even better for you: eprints.maths.ox.ac.uk/165/1/x3%2B2.pdf – Matthew Conroy Dec 2 '13 at 23:17