$n \in \Bbb N$ such that $n!$ is divisible by $n^2+1$

Question

Prove that exist infinitely many natural numbers $n \in \Bbb N$ such that $n!$ is divisible by $n^2+1$.

It's obvious when n is large enough $n!$ grows larger than $n^2+1$, so $n!>n^2+1$. Is it somehow beneficial in proof?

Answer 1

Hint:

Take $n=2(5k-2)^2$ for any $k\in\mathbb N$.

Then $n^2+1$ can be written as the product of three relatively prime factors less than $n$ as follows:

$5(10k^2-6k+1)(50k^2-50k+13).$

Answer 2

One way to approach it is to look for solutions of the equation $x^2-5y^2=-1$. If we have a solution to that modified Pell equation, we can factor $x^2+1=5\cdot y \cdot y$. As $y \lt \frac x2$, $x!$ will have a term $y$ and another term $2y$, so if $x \gt 5$ we have $(x^2+1)|x!$

We observe $x=2,y=1$ is a solution but the factor $5$ spoils this one. We can use Brahmagupta's identity to find more. Given an $(x,y)$ pair, the next is $(9x+20y,4x+9y)$, so the next is $(38,17)$ and we can produce as many as we want. We have $38^2+1=1445=5\cdot 17 \cdot 17$ divides $38!$ because $38!$ has $5,17,34$ among the numbers multiplied to form it.

We could choose any other constant than $5$ which is greater than $4,$ nonsquare, and for which the modified Pell equation can be solved.