Opravovatelia

Mišo M. [email protected]

Sebik [email protected]

Na to, aby boli dve tvrdenia ekvivalentné, musí z jedného vyplývať druhé a z druhého prvé. Ukážeme teda postupne tieto dve implikácie.

Najprv predpokladajme, že máme nejaké kladné celé čísla $m, n$, pričom žiadne prvočíslo $p \leq n$ nie je deliteľom čísla $m$. Chceme ukázať nejakú vlastnosť kombinačného čísla. Zvoľme teda $k \leq n$ ľubovoľne a pozrime sa na to, ako bude dané kombinačné číslo vyzerať.

$${m + k - 1 \choose k} = \frac{(m + k - 1)!}{(m - 1)! \cdot k!} = \frac{(m+k-1) \cdot (m+k-2) \cdot \cdots \cdot (m+1) \cdot m}{k \cdot (k-1) \cdot \cdots \cdot 1}$$

Vieme, že kombinačné číslo je celé, takže menovateľ sa vykráti s čitateľom. Nás zaujíma, či po tomto vykrátení bude výsledok deliteľný číslom $m$. Pozrime sa teda na prvočísla, ktoré sa vyskytujú v menovateli. Pre každé takéto prvočíslo $q$ platí, že $q \leq k$, keďže $q$ je deliteľom čísla menšieho alebo rovného $k$. Potom nutne $q \leq n$, a teda podľa predpokladu platí, že $q$ nie je deliteľom čísla $m$. Keďže je to prvočíslo, z čísla $m$ v čitateli sa nič nevykráti a výsledná hodnota bude skutočne násobkom $m$. Takže máme prvú implikáciu dokázanú.

Pozrime sa teraz na druhú implikáciu. Tu predpokladáme, že čísla $m$ a $n$ spĺňajú, že pre každé $k \leq n$ je číslo ${m+k-1 \choose k}$ násobkom $m$. Na základe tohto predpokladu by sme chceli dokázať niečo pre prvočísla, ktoré sú menšie alebo rovné $n$.

Vezmime si teda ľubovoľné prvočíslo $p \leq n$. Zjavne preň platí, že ${m+p-1 \choose p}$ je násobok čísla $m$. Rozpíšme si toto kombinačné číslo rovnako ako vyššie.

$${m+p-1 \choose p} = \frac{(m + p - 1) \cdot (m + p - 2) \cdot \cdots \cdot (m + 1) \cdot m}{p \cdot (p - 1) \cdot \cdots \cdot 1}$$

Keďže je to násobok $m$, po vydelení týmto číslom musíme opäť dostať celé číslo. To bude mať tvar $$\frac{(m + p - 1) \cdot (m + p - 2) \cdot \cdots \cdot (m + 1)}{p \cdot (p - 1) \cdot \cdots \cdot 1}.$$

Keďže sa všetko musí vykrátiť a keďže $p$ je prvočíslo, tak musí byť deliteľom jedného z čísel v čitateli. Môžeme označiť, že $p$ je deliteľom $m + a$, kde $1 \leq a \leq p - 1$. Potom však platí, že číslo $m$ má zvyšok $p - a$ po delení $p$. Keďže $a \neq 0$ ani $a \neq p$, tak číslo $m$ nie je násobkom $p$. Toto platí bez ohľadu na voľbu $p$, takže sme dokázali aj druhú implikáciu.