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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email