Dělitelnost faktoriálu
Úloha číslo: 3674
Ukažte, že \((k!)^n\) dělí \((kn)!\).
Řešení
Ukážeme nejprve, že \(k!\) dělí součin každých \(k\) po sobě jdoucích čísel.
To plyne např. z faktu, že \(\binom{m}{k}=\frac{m(m-1)\cdots(m-k+1)}{k!}\) je celočíselný podíl \(k\) po sobě jdoucích čísel \(m-k+1,m-k+2,…,m\) a \(k!\).
Potom \((kn)!\) si lze rozdělit na \(n\) úseků, z nichž každý tvoří \(k\)-tici po sobě jdoucích čísel. Již víme, že každý tento úsek je dělitený \(k!\) a proto je i celý součin \((kn)!\) dělitelný \((k!)^n\).
Jiný, mírně komplikovanější postup vedoucí ke stejnému cíli: Spočítáme-li si pro každé prvočíslo \(p\), jakou nejvyšší mocninou dělí \(k!\), a porovnáme-li ji s nejvyšší mocninou \(p\) dělící \((kn)!\), tak u \((kn)!\) je tato mocnina alespoň \(n\)-krát větší.