XXI OM - III -Zadanie 3

Udowodnić, że $ n > 1 $ jest liczbą pierwszą wtedy i tylko wtedy, gdy dla każdego naturalnego $ k $, takiego że $ 1 \leq k \leq n - 1 $, współczynnik dwumianowy

\[<br /> \binom{n}{k} = \frac{n!}{k!(n-k)!}<br /> \]

dzieli się przez $ n $.

Rozwiązanie

Jeśli $ n $ jest liczbą pierwszą, to dla $ 1 \leq k \leq n - 1 $ liczby $ k $ i $ n - k $ są mniejsze od $ n $ i wobec tego liczby $ k! $ i $ (n - k)! $ nie są podzielne przez $ n $.

Ze wzoru $ \displaystyle \binom{n}{k} = \binom{n!}{k!(n-k)!} $ otrzymujemy

\[<br /> (1) \qquad n! = \binom{n}{k} k!(n-k)!.<br /> \]

Ponieważ lewa strona (1) jest podzielna przez liczbę pierwszą $ n $, a $ k! $ i $ (n - k)! $ nie są podzielne przez $ n $, więc liczba $ \binom{n}{k} $ jest podzielna przez $ n $.

Przypuśćmy z kolei, że $ n $ jest liczbą złożoną i oznaczmy przez $ p $ pewien dzielnik pierwszy tej liczby. Gdyby liczba $ \binom{n}{p} $ była podzielna przez $ n $, to dla pewnej liczby naturalnej $ s $ mielibyśmy $ \binom{n}{p}= ns $. Wtedy ze wzoru

\[<br /> \binom{n}{p} = \frac{n(n-1)(n-2) \ldots (n -(p-1))}{p!}<br /> \]

otrzymalibyśmy $ s =\frac{(n-1)(n-2) \ldots (n -(p-1))}{p!} $, czyli

\[<br /> (1) \qquad sp! = (n- 1)(n-2)\ldots(n- (p- 1)).<br /> \]

Ponieważ $ p \mid n $, więc liczby $ n - 1, n - 2, \ldots, n - (p - 1) $ nie są podzielne przez $ p $. Zatem prawa strona równości (1) nie jest podzielna przez $ p $, a lewa strona jest oczywiście podzielna przez $ p $.

Otrzymana sprzeczność dowodzi, że liczba $ \binom{n}{p} $ nie jest podzielna przez $ n $.

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

Komentarze

Dodaj nową odpowiedź