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

Komentarze

Dodaj nową odpowiedź