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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.