<s>[INST] Proof that $n!$ is divisible by $(n+1)^2$ for $n=xy+x+y$ I noticed the other day that for $n>8, n\in\mathbb{N}$, the factorial $n!$ seems to be divisible by $(n+1)^2$ when $n$ can be written in the form $xy+x+y$ (where $x,y\geq1$ and $\in\mathbb{N}$). Some examples:


*

*$n=14=2 \times 4+2+4$ (i.e. $x=2$, $y=4$), and we have $14!|15^2$

*$n=15=3 \times 3+3+3$ (i.e. $x=y=3$), and we have $15!|16^2$,

*$n=19=3 \times 4+3+4$ (i.e. $x=3$, $y=4$), and we have $19!|20^2$,

*...


This seems to hold for the first $15$ values I checked, so it seemed natural to try to prove it for all $n=xy+x+y$, however I could not find a proof. Here is my attempt:
Plugging $xy+x+y$ into the expressions above and noticing that $xy+x+y+1=(x+1)(y+1)$, we need to prove that
$$
(xy+x+y)!|(x+1)^2(y+1)^2,
$$
or
$$
\Gamma((x+1)(y+1))|(x+1)^2(y+1)^2.
$$
It is easy to prove that 
$$
\Gamma((x+1)(y+1))|(x+1)(y+1)
$$
however I am struggling to prove the same for $(x+1)^2(y+1)^2$. Any hints?
 [/INST] Wlog. $x\le y$.
If we are lucky, we find $x+1,2(x+1),y+1,2(y+1)$ as different elements among the factors $1,2,3,\ldots, n$ and we are done.
How can we fail to be lucky? The four candidates may be too large or not be different after all. As we assume $x\le y$, the following list is exhaustive:


*

*It may happen that $2(y+1)>n=xy+x+y$. This implies $x=1$. And indeed, $x=1$, $y=2$ gives $n=5$ and $36$ does not divide $5!$. More generally if $y+1$ is prime, then $(2y+1)!$ is not divisible by $(y+1)^2$.

*It may happen that $x+1=y+1$, which of course means that $x=y$. If $x\le 3$, we have $n\le 8$, which is excluded. If $x\ge 4$,  we can use the factors $x+1,2(x+1),3(x+1),4(x+1)$ instead. These are guaranteed to be different and we have $4(x+1)\le xy+y<n$.

*It may happen that $2(x+1)=y+1$. Then we can use $x+1,2(x+1)=y+1, 3(x+1), 2(y+1)$ instead.


Thus

If $n=xy+x+y>8$ with positive integers $x,y$ then $(n+1)^2\mid n!$ except when $n+1$ is twice a prime.

</s>