XL OM - I - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

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:

$ N= \binom{n}{k}=\frac{n!}{k!(n-k)!}, \quad M=\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}. $

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

$ \frac{N}{M}=\frac{n!}{k!(n-k)!}\cdot \frac{(k-1)!(n-k)!}{(n-1)!}=\frac{n}{k} $

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ć.