4
$\begingroup$

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) <n$, because all n satisfy. But $\pi^{-2019}.$ goes down a lot .... how do I prove it?

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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! $\endgroup$
    – Vincent
    Oct 9, 2019 at 14:14
  • 1
    $\begingroup$ @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 $\endgroup$
    – Marian
    Oct 9, 2019 at 15:35
  • $\begingroup$ Great, thank you! $\endgroup$
    – Vincent
    Oct 10, 2019 at 17:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .