Proof that $n!$ is divisible by $(n+1)^2$ for $n=xy+x+y$

Question

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?

Answer 1

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.

Answer 2

$\color{Green}{\text{Question}}$ : Find all integers $n$; such that $\color{Green}{(n+1)! \mid n!} $ .

---

---

$\color{Blue}{\star \ \ \ \ \text{condition}}$ :

Now suppose that $n+1$ can be written in the form $n+1=ab$; with $2 < a,b$. Also assume that one of the following occures:

• If $a= b$; then $5 \leq a=b$.

• If $a=2b$; then $5 \leq b $.

• If $2a=b$; then $5 \leq a $.

---

With the condition as in $\color{Blue}{\star}$ ; we claim that the assertion is $\color{Blue}{\text{true}}.$

---

Let $n, a, b$ to be fixed as above in $\color{Blue}{\star}$ . Notice that if we let $x:=a-1$ and $y:=b-1$ then one can easilly see that: $$n=xy+x+y.$$

---

---

$\color{Blue}{\text{Remark(I)}}$ : With the notation as in $\color{Blue}{\star}$;

• If $a=b$ , with $5 \leq a$ then we have: $$b < 2b < 3b < 4b < ab=n+1 \Longrightarrow b < 2b < 3b <4b \leq n=ab-1 \ ; $$ so we can conclede that: $$(b)(2b)(3b)(4b)=24(ab)^2=24(n+1)^2 \mid n! ;$$ which implies that: $(n+1)^2 \mid n! \ \ $ .

---

• If $a=2b$ ; with $5 \leq b$ then we have: $$b < 2b < 3b < 4b < ab=n+1 \Longrightarrow b < 2b < 3b <4b \leq n=ab-1 \ ; $$ so we can conclede that: $$(b)(2b)(3b)(4b)=6(ab)^2=6(n+1)^2 \mid n! ;$$ which implies that: $(n+1)^2 \mid n! \ \ $ .

---

• If $2a=b$ ; with $5 \leq a$ then we have: $$a < 2a < 3a < 4a < ba=n+1 \Longrightarrow a < 2a < 3a <4a \leq n=ba-1 \ ; $$ so we can conclede that: $$(a)(2a)(3a)(4a)=6(ab)^2=6(n+1)^2 \mid n! ;$$ which implies that: $(n+1)^2 \mid n! \ \ $ .

---

• If $a \neq b$ and $a \neq 2b$ and $2a \neq b$ ; then we have: $$b < 2b < ab=n+1 \Longrightarrow b < 2b \leq n=ab-1 \ ; $$ $$a < 2a < ab=n+1 \Longrightarrow a < 2a \leq n=ab-1 \ ; $$ so we can conclede that: $$(b)(2b)(a)(2a)=4(ab)^2=4(n+1)^2 \mid n! ;$$ which implies that: $(n+1)^2 \mid n! \ \ $ .

---

---

---

---

---

---

Remark(II): Integer $N$ can not be written in the form $N=ab$; with $2 < a,b$; if and only if $N$ is prime or twice a prime.

---

Remark(III): We can split the integres in three cases:

1. $\color{Red}{ n+1 = \text{prime numbers and twice of prime numbers; for which the assertion is wrong!} }.$

2. $\color{Purple}{ n+1= a.a \ \ \ \text{for} \ \ \ a \in \{ 1, 2, 3, 4 \} }.$ This case has only four numbers; which can you check out that the assertion is $\color{Blue}{\text{true}}$ only for $\color{Blue}{n+1=16}$ and $\color{Blue}{n+1= 1}$ .

3. $\color{Purple}{ n+1= a.(2a) \ \ \ \text{for} \ \ \ a \in \{ 1, 2, 3, 4 \} }.$ This case has only four numbers; which can you check out that the assertion is $\color{Blue}{\text{true}}$ only for $\color{Blue}{n+1=18}$ and $\color{Blue}{n+1=32}$ .

---

$\color{Green}{\text{Remark(IV)}}$ : Except for the following cases; for which the assertion is $\color{Red}{\text{wrong}}$

1.$\color{Red}{ n+1 = \text{prime numbers and twice of prime numbers } }.$

2.$\color{Red}{ n+1= 4, 9, 2, 8 } .$

for all the other cases the assertion is $\color{Blue}{\text{true}}$ .

---

---

---

---

---

---

$\color{Red}{\text{Remark(V)}}$ : Let $p$ to be an odd prime number; then we have: $p^2 \color{Red}{\nmid} (2p-1)! \ \ . $

---

For example let $p$ to be an odd prime number; and let's define: $$n:=2p-1 \ \ \ \text{and} \ \ \ x:=1 \ \ \ \text{and} \ \ \ y:=p-1.$$

Notice that we have: $n=xy+x+y$

---

We calaim that $(2p)^2 \color{Red}{\nmid} (2p-1)!$.

[ Suppose on contrary that $(2p)^2 \mid (2p-1)!$ , on the otherhand notice that $p^2 \mid (2p)^2$. So we must have $p^2 \mid (2p-1)!$ ; which has an obvious contradiction with the above $\color{Red}{\text{Remark(V)}}$. ]