Berkeley Math Circle: Monthly Contest 6

Solution:

By Fermat's Christmas theorem, the only primes which may divide $n^{2}+1$ other than $2$ are those which are $1 \pmod{4}$, and moreover $2^{2} \nmid n^{2}+1$ for any $n$.

Consider primes $p \equiv 1 \pmod{4}$. Observe that for any $x$, we have
$$\#\{n \leq x \mid n^{2}+1 \equiv 0 \pmod{p^{2}}\} \leq \frac{2}{p^{2}} x + 2$$
since there are at most two solutions $\bmod\ p^{2}$ to $n^{2} \equiv -1 \pmod{p^{2}}$.

Summing over all primes $p \equiv 1 \pmod{4}$ now implies the result, since
$$\sum_{p \equiv 1} \frac{2}{p^{2}} < 2\left(\frac{1}{4^{2}} + \frac{1}{8^{2}} + \ldots\right) = \frac{\pi^{2}}{6} \cdot \frac{1}{8} < 1$$