Baltic Way 2011 · Shortlist problem

It is true for all numbers $n = 2a^2$ where $a > 1$ and $a \equiv 1 \pmod{5}$. If $n = 2a^2$ then $n^2 + 1 = 4a^4 + 1 = (2a^2 + 2a + 1)(2a^2 - 2a + 1)$. As $2a^2 - 2a + 1 < 2a^2$ it remains to ensure that all prime factors of $2a^2 + 2a + 1$ are less than $2a^2$. If $a \equiv 1 \pmod{5}$ then $2a^2 + 2a + 1 \equiv 0 \pmod{5}$ and therefore $2a^2 + 2a + 1 = 5 \cdot \frac{2a^2+2a+1}{5}$, both these factors are less than $2a^2$.