# Square-free value of $n^2+1$ without large prime factors

It is well-known that there are infinitely many square-free numbers of the form $n^2+1,n\in\mathbb{Z}$.

Question: Are there infinitely many square-free numbers of the form $n^2+1$, each with all its prime factors $\leq n$?

• Interesting question. I bet the answer is affirmative, but a highly non-trivial application of sieve methods is required. Obviously a number $m$ cannot have more than one prime factor greater than $\sqrt{m}$, so a good idea may be to look for such $n$s by imposing that the first small primes of the form $4k+1$ ($5,13,17,\ldots$) do not divide $n^2+1$, then apply a sieve to such set. – Jack D'Aurizio Sep 13 '15 at 15:14
• On the one hand, the density of squarefree values of $n^2+1$ is computable and positive. On the other hand, the set of $n$-smooth values of $n^2+1$ is known to have positive lower density by a result of Dartyge. So one approach, similar to what Jack suggests, would be to obtain a lower bound on $n$-smooth values of similar quality (we only really need upper density bounded away from $0$) while restricting $n$ to a particular congruence class. Then the squarefree density can likely be brought arbitrarily close to $1$ by choosing an appropriate congruence class, so they'd intersect. – Erick Wong Sep 13 '15 at 15:47
• Fortunately if we just want infinitude, rather than positive density, an elementary argument suffices. See my answer below. – Noam D. Elkies Sep 22 '15 at 21:02

Yes, there are infinitely many such $n$.
One way to prove this is to start from a quadratic polynomial $N(x)$ with integer coefficients such that there's a factorization $N^2+1=AB$ into two quadratics; let's use $$N(x) = 5x^2+x-1, \quad N(x)^2 + 1 = (5x^2-4x+1) (5x^2+6x+2) = A(x) B(x).$$ Now substitute suitable positive integers for $x$, and try $n=N(x)$. One of $A,B$ is already smaller than $N$, and the other can be made to have all its prime factors smaller than $N$ by choosing $x$ in some congruence class; in our case $A<N$, and $B$ works as long as $x$ is even $-$ which fortunately is still consistent with $N^2+1$ being squarefree in our case. (NB $n^2+1$ could never be divisible by $4$ however $n$ was chosen.) I claim that as $X \to \infty$ a positive fraction of even choices of $x<2X$ make $n^2+1$ squarefree. Indeed let $S_p$ be the number of even $x < 2X$ for which $p^2 | N(x)^2 + 1$. Then $S_p=0$ if $p>10X$ or $p \neq 1 \bmod 4$, and otherwise $S_p < 4X/p^2 + 4$ (there are $4$ congruence classes for $x \bmod p^2$ that must be excluded). The sum of $4X/p^2$ over all $p \equiv 1 \bmod 4$ converges to $cX$ for some $c<1$ (in fact $c < 1/4$ if I computed right) and the sum of $4$ over $p<10X$ is $O(X/\log X)$. Hence $\sum_p S_p = (c+o(1)) X$ for large $X$, and we conclude that the number of choices of $x$ that make $n^2+1$ squarefree is at least $(1-c-o(1))X \to \infty$, QED.
• Thank you so much, Prof. Elkies! I guess that the density should be $c_n(1-\log 2)$(where $c_n$ is the density of square free $n^2+1$) , but it might be very hard to prove such a result. – zy_ Sep 22 '15 at 23:20