XXI OM - III -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

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

$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $

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

$ (1) \qquad n! = \binom{n}{k} k!(n-k)!. $

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

$ \binom{n}{p} = \frac{n(n-1)(n-2) \ldots (n -(p-1))}{p!} $

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

$ (1) \qquad sp! = (n- 1)(n-2)\ldots(n- (p- 1)). $

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