We try $n=2k^2$ for some $k$: $n^2+1=4k^4+1=(2k^2+2k+1)(2k^2-2k+1)$. Now $\gcd(2k^2+2k+1,2k^2-2k+1)=\gcd(4k,2k^2-2k+1)=1$ and $2k^2-2k+1<2k^2=n$, so $2k^2-2k+1|n!$. Thus everything we still need to show is that $2k^2+2k+1$ can be choosen such that it divides $n!$. For this, take for example $k=25m+1$, since then $2k^2+2k+1=5 \cdot s$ for some $s$ not divisible by $5$. Thus $5<n$, $s=\frac{2k^2+2k+1}5 < 2k^2 =n$ and $\gcd(5,s)=1$, implying the result.

Let $ n=4k^{2}+2k+1$ $ n^{2}+1=(4k^{2}+1)^{2}+2(4k^{2}+1)2k+(2k)^{2}+1=2(4k^{2}+1)(2k^{2}+2k+1)$. If we suppose $ 2<2k^{2}+2k+1<4k^{2}+1$, then $ 2(4k^{2}+1)(2k^{2}+2k+1)$ divides $ (4k^{2}+2k+1)!$

http://www.mathlinks.ro/Forum/viewtopic.php?t=169901 See more here with the general.

$ n_0 = 18$ gives a solution, since $ 18^2 + 1 = 325 = 5^2*13$ Now if we have a solution $ n_i$, then $ n_{i + 1} = n_i^2 + 1 - n_i$ is also a solution: Denote $ n_i^2 + 1$ by $ k$ and $ n_i$ by $ n$. Then $ (k - n)^2 + 1 = k^2 - 2nk + n^2 + 1 = k(k - 2n + 1)$. But $ k|n!$ and $ n < k - 2n + 1 < k - n$ thus $ (k - n)^2 + 1 = k(k - 2n + 1)|(k - n)!$. So we've found infinitely many distinct solutions for the equation.

Solution. Consider the equation $ n^2-5m^2=-1$. Clearly, $ \max\{m,2m\}<n$. For $ n>5, m\neq 5$, we have that $ n^2+1=5m^2|n!$. The equation $ n^2-5m^2=-1$ is a Fermat (or Pell) equation with infinitely many solutions. And the conclusion follows. $ \Box$

Does anybody know why it is that in the corresponding PEN document it is said that the source for this problem is Kazakhstan, 1998? Let me thank you in advance for your learned replies...

boxedexe wrote: Solution. Consider the equation $ n^2-5m^2=-1$. Clearly, $ \max\{m,2m\}<n$. For $ n>5, m\neq 5$, we have that $ n^2+1=5m^2|n!$. The equation $ n^2-5m^2=-1$ is a Fermat (or Pell) equation with infinitely many solutions. And the conclusion follows. $ \Box$ @boxedexe. This might be nine years too late (srry about the necrobump), but Pell Equations are in the form $x^2 - d y^2 = 1$. $n^2 - 5m^2 = -1$ is a negative Pell Equation and does not necessarily have infinite solutions. See more about it here: https://en.wikipedia.org/wiki/Pell%27s_equation#The_negative_Pell_equation