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ší.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze