# Prove that $(k^3)!$ is divisible by $(k!)^{k^2 + k + 1}$. Proof using properties of greatest integer function?

I came across this problem in a regional Olympiad Exam. I'm giving the outline of my solution and a question related to it.

Problem

Let $k$ be any positive integer. Prove that $(k^3)!$ is divisible by $(k!)^{k^2 + k + 1}$.

Question

My first approach was to use the fact that for any prime $p \leq k$, the highest power of $p$ contained in $k!$ is given by $\sum _{j=1}^{\infty} \big[ \frac{k}{p^j}\big]$, where $[.]$ is the greatest integer (floor) function, then somehow use the properties of this function to show that for every prime $p$ contained in $k!$, it's power in $k^3!$ is at least $k^2+k+1$ times that in $k!$.

However, this approach did not lead me anywhere beyond a couple of steps. The reason might be that I'm missing some properties of the greatest integer function. Please post your proof if you can make this approach work.

I finally gave up this approach and came up with the following solution.

Solution

I somehow managed to prove a generalized statement using induction.

We will prove that $\forall k,n \in \mathbb{Z}^+$, $(k^n)!$ is divisible by $(k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$.

Let $P(k,n)$ be the statement that $(k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1} \mid (k^n)!$.

$P(k,1)$ is obviously true for all $k \in \mathbb{Z}^+$.

Chose any $k$ and assume that $P(k,n)$ is true for some positive integer $n$.

Now, $(k^{n+1})!$ can be written as follows:

$$\begin{eqnarray*} (k^{n+1})! &=& \Big(1 \cdot 2 \cdot 3 \cdots k^n \Big) \cdot % \Big((k^n + 1) \cdot (k^n + 2) \cdots (2k^n) \Big) \cdot % \Big((2k^n + 1) \cdot (2k^n + 2) \cdots (3k^n) \Big) \cdots % \Big(((k - 1)k^n + 1) \cdot ((k-1)k^n + 2) \cdots (k\cdot k^n) \Big) \\ &=& \alpha_1 \cdot \alpha_2 \cdot \alpha_3 \cdots \alpha_k \end{eqnarray*}$$

where

$$\begin{eqnarray*} \alpha_j &=& \big((j - 1)k^n + 1\big) \cdot \big((j-1)k^n + 2\big) \cdots \big(j\cdot k^n \big) \\ &=& \prod \limits_{m = 1}^{k^n} \big((j - 1)k^n + m\big) \\ &=& j \cdot k^n \cdot \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \end{eqnarray*}$$

Now, $\; \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \;$ is a product of $(k^n - 1)$ consecutive integers. Hence $(k^n - 1)! \;$ divides $\; \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big) \;$. Therefore, $(k^n)! \quad$ divides $\quad k^n \cdot \prod \limits_{m = 1}^{k^n -1} \big((j - 1)k^n + m\big)$. Therefore, $\alpha_j$ can be written as

$$\alpha_j = j \cdot \beta_j \cdot (k^n)!$$ for some $\beta_j \in \mathbb{Z}^+$.

By the inductive hypothesis, $(k^n)! = \nu \cdot (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$ for some $\nu \in \mathbb{Z}^+$. Thus,

$$\alpha_j = j \cdot \beta_j \cdot \nu \cdot (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1}$$

Thus,

$$\begin{eqnarray*} (k^{n+1})! &=& \alpha_1 \cdot \alpha_2 \cdots \alpha_k \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot \Big(\prod \limits_{j = 1}^{k} j \Big) \cdot % \Big( (k!)^{k^{n-1} + k^{n-2} + \cdots + k^2 + k + 1} \Big)^k \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot (k!) \cdot % \Big( (k!)^{k^{n} + k^{n-1} + \cdots + k^3 + k^2 + k} \Big) \\ &=& \nu^k \cdot \Big(\prod \limits_{j = 1}^{k} \beta_j \Big) % \cdot % \Big( (k!)^{k^{n} + k^{n-1} + \cdots + k^3 + k^2 + k + 1} \Big) \end{eqnarray*}$$

Thus $P(k,n+1)$ is true if $P(k,n)$ is true.

• I am curious if there is a way to prove the divisibility relation with group actions. Perhaps ${\rm Sym}([k]^3)$ acts freely on some structure like ${\rm Map}([k]^3,[k^2+k+1])$. Or there might be a group-theoretic proof when we restrict to $k=p$ prime, in which case $p$, $p^3$, $p^2+p+1$ represent $\Bbb F_p$, $\Bbb F_p^3$, $\Bbb P(\Bbb F_p^3)$ respectively. Jul 3, 2017 at 21:07
• @arctictern I think there might be a similar approach by noting that $\frac{(k^3)!}{(k!)^{k^2}}$ is a multinomial coefficient and then exploiting its symmetries to show that it's divisible by $(k!)^{k+1}$. Jul 3, 2017 at 21:38

Look at $G=S_{k^3}$ which has order $n=k^3!$. Look at the subgroup $H$ of $G$ isomorphic to $(S_k)^{k^2}$ which has order $m=(k!)^{k^2}$. Now you can "permute" the $k^2$ different copies of $S_k$ in $H$ in $l=(k^2)!$ ways, which gives you a supgroup $I$ with order $ml$ with $H\subset I$, so we established $ml|n$. Now looking at $S_{k^2}$ and using the exact same idea gives you $(k!)^{k+1}|(k^2)!=l$. Now combine these results to complete the proof.
In the interval $[1,k^3]$ there are $k^3-k^2$ numbers $\not\equiv 0\pmod{k}$, $k^2-k$ numbers that are $\equiv 0\pmod{k}$ but $\not\equiv 0\pmod{k^2}$, $k-1$ numbers that are $\equiv 0\pmod{k^2}$ but $\not\equiv 0\pmod{k^3}$ and just $1$ element that is a multiple of $k^3$. In particular $(k^3)!$ is for sure a multiple of
$$k^3 \cdot k^{2(k-1)} \cdot k^{k^2-k} =k^{k^2+k+1}.$$ The product of $(k-1)$ consecutive numbers $\neq 0\pmod{k}$ is always a multiple of $(k-1)!$, since $$\frac{1}{(k-1)!}\prod_{j=1}^{k-1}(a+j) = \binom{a+k-1}{k-1} = \binom{a+k-1}{a}\in\mathbb{Z}.$$ It follows that the product of the elements of $[1,k^3]$ that are not $\equiv 0\pmod{k}$ is a multiple of $(k-1)!^{k^2}$ and the claim simply follows by rearranging the remaining terms and applying the considerations above. It is enough to consider that $$(k!)^{k^2+k+1} = k^{k^2+k+1}\cdot (k-1)!^{k^2+k+1}.$$