# Greatest prime divisor of $n^2+1$

Prove that there exist infinitely many positive integers $$n$$ such that the greatest prime divisor of $$n^2+1$$ is less than $$n \cdot \pi^{-2019}.$$

What did I do: $$n = 2a^2$$, then $$n^2+1 = 4a^4+1 = ((a-1)^2+a^2)((a+1)^2+a^2)$$. Funny that it's trivial for $$P (n ^ 2 + 1) , because all n satisfy. But $$\pi^{-2019}.$$ goes down a lot .... how do I prove it?

• What's the source of this problem?
– user655800
Oct 8, 2019 at 14:02
• The proof you need is valid for all $D$ instead of $\pi^{2019}$. It does not matter their magnitude. Oct 8, 2019 at 14:06
• Why, you may choose any other special case with convenient factorization. Say, $n=a^3$, then... Oct 8, 2019 at 19:03

Let us prove that for every $$\varepsilon > 0$$ there exist infinitely many integers $$n > 0$$ such that $$P(n^2 + 1) < \varepsilon n$$.

Obviously, it is enough to prove that there exists one such $$n$$. As you noticed, if $$n = 2m^2$$, for some integer $$m > 0$$, then $$n^2 + 1 = (2m^2 - 2m + 1)(2m^2 + 2m + 1)$$. Hence, it is enough to prove that we can find $$m$$ such that $$P(2m^2 - 2m + 1) < 2\varepsilon m^2$$ and $$P(2m^2 + 2m + 1) < 2\varepsilon m^2$$.

It is well known and not difficult to prove that for every polynomial $$f \in \mathbb{Z}[x]$$ the set of prime numbers $$p$$ such that $$p$$ divides $$f(k)$$ for some integer $$k > 0$$ is infinite. Therefore, we can find an integer $$\ell > 0$$ such that $$p_1 := P(2\ell^2 - 2\ell + 1) > 2/\varepsilon$$ and $$p_2 := P(2\ell^2 + 2\ell + 1) > 2/\varepsilon$$.

Now letting $$m := \ell + t p_1 p_2$$, for some integer $$t > 0$$, we get that $$p_1$$ divides $$2m^2 - 2m + 1$$ and $$p_2$$ divides $$2m^2 + 2m + 1$$.

Hence, $$P(2m^2 - 2m + 1) < \max(p_1, (2m^2 - 2m + 1) / p_1)$$ and $$P(2m^2 + 2m + 1) < \max(p_2, (2m^2 + 2m + 1) / p_2)$$.

Taking $$t$$ sufficiently large, we get that $$P(2m^2 + 2m + 1) < (2m^2 + 2m + 1) / p_2 < \varepsilon(2m^2 + 2m + 1) / 2 < \varepsilon 4m^2 / 2 < 2\varepsilon m^2$$ and, similarly, $$P(2m^2 - 2m + 1) < 2\varepsilon m^2$$, as required.

• I like this answer! But can you elaborate a bit on how you find $p_1$ and $p_2$? It is clear from the previous sentence that you can find an $\ell$ so that $p_1 > 2/\varepsilon$ and similar for $p_2$, but how do we know that we can find them simultaneously, i.e. with the same $\ell$? Thanks in advance! Oct 9, 2019 at 14:14
• @Vincent More generally, given $c > 0$ and nonconstant polynomials $f_1, f_2, \dots, f_k \in \mathbb{Z}[x]$, we can prove that there exists an integer $n > 0$ such that each of $f_1(n), \dots, f_k(n)$ has a prime factor greater than $c$. This can be done by induction, since once we know that $f_1(n)$ is divisible by a prime $p > c$, then we have that $f_1(n + tp)$ is divisible by $p$, so we have to chose $t$ such that $f_2(n + tp)$ has a prime factor greater than $c$... and so on Oct 9, 2019 at 15:35
• Great, thank you! Oct 10, 2019 at 17:59