Um... Finding infinitely many $ n$ where $ n^2+1$ does not divide $ n!$ is fairly easy. Just find a prime $ p\equiv 1(mod 4)$ then since $ -1$ is a quadratic residue we can find a $ n$ such that $ p|n^2+1$. Obviously we can have $ n<p$ so $ p$ doesn't divide $ n!$. Moreover there are infinitely many primes $ p\equiv 1(mod 4)$ and if $ p|n^2+1$ then $ n^2+1\ge p$ so $ n$ can be arbitrarily large. I am not sure about the other part. It seems harder.

let $ n=2(5k+1)^2=50k^2+20k+2,$ then $ n^2+1=[2(5k+1)^2+2(5k+1)+1][2(5k+1)^2-2(5k+1)+1]=5(5k^2+6k+1)(50k^2+10k+1).$

I think i've seen this problem in a book which is written by Titu or someone, in the book, they use Pell Equation to tackle this problem, but i still don't understand

it's not difficult to find that if n satisfies the conclusion, $ n^{2}-n+1$satisfies the conclusion.Because n=18 satisfies the conclusion ,so there are infinitely n satisfy the conclusion.

Ronald Widjojo wrote: I think i've seen this problem in a book which is written by Titu or someone, in the book, they use Pell Equation to tackle this problem, but i still don't understand The equation $ n^2+1=5m^2$ is a Pell's equation and has a solution (2, 1). This means it has infinitely many solutions. If n is a solution we have $ n^2+1=5m.m$ and since both m<n and 5m<n (for n>5) we have $ n^2+1|n!$

http://www.mathlinks.ro/viewtopic.php?t=150399