<s>[INST] Infinitely many $n$ such that $n^2+1$ is squarefree How can we show that there are infinitely many positive integers $n$ such that $n^2+1$ is square free? I was thinking we could split it into cases of squares of primes congruent to either 1 or 3 (mod 4).
Even stronger: could we prove that the set of numbers positive integers $m$ such that $m^2+1$ is not squarefree is a set of measure zero?
EDIT: could I get an elementary solution to the first question?
 [/INST] Let $S(n)$ be the number of squareful numbers of the form $k^2+1$ less than or equal to $n^2+1$.  We can bound it from above by counting every time a number is divisible by the square of a prime:
$S(n) \le \sum_{1 \le p \le n}{\sum_{1 \le k \le n, p^2 \vert k^2+1}{1}}$
Since $k^2+1$ is never divisible by $4$ or $9$, this becomes:
$S(n) \le \sum_{5 \le p \le n}{\sum_{1 \le k \le n, p^2 \vert k^2+1}{1}}$
$-1$ has at most two square roots mod $p^2$, so we can write this as:
$S(n) \le \sum_{5 \le p \le n}{(\frac{2 \cdot n}{p^2}+2)}$
And we can separate the constant term to get:
$S(n) \le  2 \cdot \pi(n) + \sum_{5 \le p \le n}{\frac{2 \cdot n}{p^2}}$
Assuming $n \gt 120$:
$S(n) \le \frac{2 \cdot \phi(120) \cdot n}{120} + 2 \cdot n \cdot \sum_{5 \le p \le n}{\frac{1}{p^2}}$
Simplifying and ignoring that the sum is limited to primes:
$S(n) \le \frac{8 \cdot n}{15} + 2 \cdot n \cdot (\frac{\pi^2}{6} - \frac{1}{16} - \frac{1}{9} - \frac{1}{4} - 1)$
Calculating and rounding up:
$S(n) \le 0.54 \cdot n + 0.45 \cdot n$
$S(n) \le 0.99 \cdot n$
So the density of squarefree numbers of the form $k^2+1$ is at least $0.01$, and therefore there are an infinite number of them.  I really wasn't expecting to end up with such a narrow margin!  It is possible to do better with some obvious improvements.
</s>