Factorial divisibility
Task number: 3849
Prove that \((k!)^n\) divides \((kn)!\).
Solution
We first show that \( k! \) divides every product of \( k \) consecutive numbers.
This is due to the fact that \(\binom{m}{k}=\frac{m(m-1)\cdots(m-k+1)}{k!}\) is an integer fraction of \( k \) consecutive numbers \( m-k + 1, m-k + 2,…, m \) and \( k! \).
Then \( (kn)! \) can be divided into \( n \) sections, each of which forms a \( k \)-tuple of consecutive numbers. We already know that each of these sections is divided by \( k! \) and therefore the whole product \( (kn)! \) is divisible by \((k!)^n\).
Another, slightly more complicated procedure leading to the same conclusion: If we calculate for each prime number \( p \), by what highest power divides \( k! \), and if we compare it with the highest power of \( p \) dividing \( (kn)! \), then we may realize that by \( (kn)! \) this power is at least \( n \) times greater.
