XL OM - I - Zadanie 1

Udowodnić, że jeśli liczby $ k $, $ n $ ($ k < n $) są względnie pierwsze, to liczba $ \binom{n-1}{k-1} $ jest podzielna przez $ k $.

Rozwiązanie

Oznaczmy:

\[<br />
N= \binom{n}{k}=\frac{n!}{k!(n-k)!}, \quad<br />
M=\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}.<br />
\]

Są to liczby całkowite. Zachodzi równość

\[<br />
\frac{N}{M}=\frac{n!}{k!(n-k)!}\cdot \frac{(k-1)!(n-k)!}{(n-1)!}=\frac{n}{k}<br />
\]

czyli $ M \cdot n = N \cdot k $. Zatem liczba $ k $ jako względnie pierwsza z $ n $, musi być
dzielnikiem $ M $; a to właśnie mieliśmy wykazać.