Komentarz

XXII OM - I - Zadanie 1

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

\[<br /> \begin{split}<br /> \binom{n}{k} &= \frac{n(n-1)(n-2)\ldots(n-k+1)}{k!} =\\<br /> &=\frac{n}{k}\cdot \frac{(n-1)(n-2)\ldots((n-1)-(k-1)+1)}{(k-1)!} =\\<br /> &=\binom{n-1}{k-1}<br /> \end{split}<br /> \]

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

\[<br /> \begin{split}<br /> \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}=\\<br /> &=m \prod_{j=1}^{p^r-1}\frac{p^rm-j}{p^r-j}.<br /> \end{split}<br /> \]

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz