Is it true that for every positive integer $n$ there is a prime $p>n,$ which divides $\prod_{i=1}^n (i^2+1)$ ?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ See OEIS sequence A219586. The paper of Hooley linked there seems relevant. $\endgroup$– Robert IsraelJul 31, 2019 at 2:15
-
6$\begingroup$ How about the following partial solution? The case of $n=1$ is trivial. So suppose $n>1$. By Bertrand's postulate there exists an odd prime $p$ with $n<p<2n$. Suppose $p\equiv 1 \pmod{4}$. In this case the equation $x^2\equiv -1 \pmod{p}$ has two solutions in $\{1,\dots,p-1\}$ whose sum is $p$. Hence one of them must be less than $\frac{p}{2}<n$. We conclude that there exists $1\leq i\leq n$ with $p\mid i^2+1$. $\endgroup$– KhashFJul 31, 2019 at 2:17
-
$\begingroup$ @KhashF: Great observation. See my response about how to complete this partial solution. $\endgroup$– GH from MOJul 31, 2019 at 4:12
-
$\begingroup$ If you like my answer, please accept it officially (so that it turns green). Thanks in advance! $\endgroup$– GH from MOAug 17, 2020 at 17:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
For $n\geq 7$, Erdős proved in 1932 that there is a prime $n<p<2n$ of the form $p=4k+1$. From this it follows, by the comment of KhashF, that $p$ divides $\prod_{i=1}^n (i^2+1)$. The remaining cases $1\leq n\leq 6$ are easy to check by hand, so the answer to the OP's question is affirmative.
answered Jul 31, 2019 at 4:10
$\begingroup$
$\endgroup$
A great question studied by many of the masters.
Let $P_n$ denote the largest prime factor of this product. Cebotarev proved that $P_n/n \rightarrow \infty$, which gives a complete answer to your question asymptotically. There were various improvements by Nagell and Erdős, and Hooley proved that $P_n \gg n^{1 + 1/10}$, see:
Hooley, Christopher, On the greatest prime factor of a quadratic polynomial, Acta Math. 117 (1967) pp 281–299, doi:10.1007/BF02395047.
This answers the question (and more) in the asymptotic range. For small $n$, you can use the following trick relevant to the arguments of these papers (also I see KhashF says this in the comments): take a prime $n < p \le 2n$ of the form $1 \mod 4$, and then note that $-1$ is a quadratic residue mod $p$ so there is an $x < p/2 \ge n$ so that $x^2+1$ is divisible by $p$. So now you win assuming that $\pi(2n;4,1) > \pi(n;4,1)$ where $\pi_1(x;4,1)$ is the number of primes less than or equal to $x$ which are $1 \pmod 4$. Now you dust off some explicit estimates for these quantities. More than good enough for this purpose is:
Michael A. Bennett, Greg Martin, Kevin O'Bryant, Andrew Rechnitzer, Explicit bounds for primes in arithmetic progressions, Illinois J. Math. 62 Number 1–4 (2018) pp 427–532, doi:10.1215/ijm/1552442669, arXiv:1802.00085.
which proves that
$$\left|\pi(x;4,1) - \frac{Li(x)}{2} \right| \le (0.0005028) \frac{x}{(\log x)^2}$$
for $x \ge 5438260589$. This is good enough to win then for $n \ge 5438260589$ because then
$$\pi(2x;4,1) - \pi(x;4,1) \ge \frac{Li(2x)}{2} - \frac{Li(x)}{2} - (0.0005028) \frac{2x}{(\log 2x)^2} - (0.0005028) \frac{x}{(\log x)^2} > 0. $$
For smaller $n$ you can do the usual ladder trick, e.g.:
$$1^2 + 1 = 2,$$ $$2^2 + 2 = 5,$$ $$4^2 + 1 = 17,$$ $$14^2 + 1 = 197,$$ $$184^2 + 1 = 33857,$$ $$33794^2 + 1 = 1142034437,$$ $$1142034424^2 + 1 = 1304242625601011777,$$ $$1304242625601011736^2 + 1 = 1701048826434620873794109106809733697,$$ $$1701048826434620873794109106809733360^2 + 1 = q_0,$$ where $q_0$ is prime, $$(q_0-131)^2 + 1 = q_1,$$ where $q_1$ is prime, $$(q_1 - 185)^2 + 1 = q_2,$$ where $q_2$ is prime, $$(q_2 - 483)^2 + 1 = q_3,$$ where $q_3$ is prime, and... the PARI stack overflows! so it is at least true for $$n \le q_3 = 491437705438594121865352195975\ldots6899550122553886277,$$ where $q_3 > 10^{579}$, but this is better than the bound we already established, so done. (This latter trick goes far enough that you can use crappier estimates at the previous step if you prefer.)
