XXII OM - I - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Udowodnić twierdzenie: Współczynnik dwumianowy $\binom{n}{k}$ ma przy każdym naturalnym $k < n$ ten sam czynnik wspólny z $n$ większy od jedności wtedy i tylko wtedy, gdy $n$ jest potęgą liczby pierwszej.

Rozwiązanie

Udowodnimy, że jeżeli liczba $n$ jest potęgą liczby pierwszej $p$ , $n = p^r$ , to każdy ze współczynników dwumianowych , gdzie $1 \leq k < n$ , jest podzielny przez $p$ .

Mamy

$ \begin{split} \binom{n}{k} &= \frac{n(n-1)(n-2)\ldots(n-k+1)}{k!} =\\ &=\frac{n}{k}\cdot \frac{(n-1)(n-2)\ldots((n-1)-(k-1)+1)}{(k-1)!} =\\ &=\binom{n-1}{k-1} \end{split} $

Stąd $k\binom{n}{k}=n \binom{n-1}{k-1}$ Zatem liczba $n$ jest dzielnikiem liczby $k\binom{n}{k}$ Ponieważ $k < n$ , więc $n$ nie jest dzielnikiem $k$ i wobec tego istnieje
wspólny dzielnik liczb $n$ i $\binom{n}{k}$ większy od jedności. Jeżeli $n = p^r$ , to każdy dzielnik liczby $n$ większy od jedności jest podzielny przez $p$ i wobec tego p jest wspólnym dzielnikiem liczb $n$ i $\binom{n}{k}$ .

Udowodnimy z kolei, że jeżeli liczba $n > 1$ nie jest potęgą liczby pierwszej, to żadna liczba pierwsza $p$ dzieląca $n$ nie jest wspólnym dzielnikiem liczb $\binom{n}{k}$ , gdzie $1 \leq k < n$ .

Niech $n = p^rm$ , gdzie liczba $m > 1$ nie jest podzielna przez $p$ . Udowodnimy, że liczba $\binom{n}{p^k}$ nie jest podzielna przez $p$ .
\spos{1} Mamy

$ \begin{split} \binom{n}{p^r}&=\binom{p^rm}{p^r}=\frac{p^rm(p^rm-1)(p^rm-2)\ldots(p^rm-p^r+1)}{p^r(p^r-1)(p^r-2)\ldots1}=\\ &=m \prod_{j=1}^{p^r-1}\frac{p^rm-j}{p^r-j}. \end{split} $

Niech $p^s$ będzie dzielnikiem liczby $p^rm - j$ , gdzie $1 \leq j \leq p^r - 1$ Gdyby $s \geq r$ , to również $p^r$ byłoby dzielnikiem liczby $p^rm - j$ , a więc i liczby $j$ . Jest to niemożliwe, ponieważ $j < p^r$ . Zatem $s < r$ .

Ponieważ $p^r-j = (p^rm-j)- (m-1)p^r$ i oba składniki po prawej stronie są podzielne przez $p^s$ , więc i liczba $p^r - j$ jest podzielna przez $p^s$ .

Udowodniliśmy więc, że jeżeli licznik ułamka $\frac{p^rm-j}{p^r-j}$ jest podzielny przez pewną potęgę liczby $p$ , to przez tę samą potęgę jest też podzielny jego mianownik. Zatem przedstawiając ten ułamek w postaci skróconej stwierdzamy, że jego licznik nie będzie podzielny przez $p$ . Ponieważ liczba $\binom{n}{p^r}$ jest iloczynem liczby $m$ i takich ułamków o licznikach nie podzielnych przez $p$ , więc nie jest ona podzielna przez $p$ .