Сравнение с биномиальным коэффициентом и простота числа

[caxap]

Задача. Доказать, что $p$ простое $\iff$ $\binom{p-1}k\equiv (-1)^k\pmod p$, $k=0,...,p-1$.

Мысли.
$(\Rightarrow)$ Если подходить наивно, то, поскольку $p-k\equiv -k\pmod p$, получаем

$$\binom{p-1}{k}=\frac{(p-1)\cdots(p-k)}{k!}\equiv \frac{(-1)^k k!}{k!}=(-1)^k\pmod p\,.$$

Но это ведь неправильно, т. к. во-первых, мы даже не использовали простоту $p$, а во-вторых, почему мы можем заменять числитель дроби на сравнимый?

(Пример)

$p=4$, $k=2$, $\binom 32=\frac{3\cdot 2}{2}=3\not\equiv 1 \pmod 4$. Тут нельзя заменить числитель $6$ на $2\equiv 6\pmod 4$.

$(\Leftarrow)$ не могу сообразить, как доказать. Тут надо как-то использовать то, что сравнение должно быть верно для всех $k=0,...,p-1$. (Для непростых $p$ сравнение может верно для некоторых $k$; например, для $p=4$ сравнение нарушается только при $k=2$.)

[Sonic86]

Простоту $p$ Вы неявно используете в переходе

сахар писал(а):

$$\frac{(p-1)\cdots(p-k)}{k!}\equiv \frac{(-1)^k k!}{k!}=(-1)^k\pmod p\,.$$

То есть в числителе получаете многочлен от $p$, но при этом считаете, что $p$ взаимно просто с $k!$

сахар писал(а):

во-вторых, почему мы можем заменять числитель дроби на сравнимый?

Вот это как раз оно! Разбиваете числитель на 2 слагаемых, в первом выносите $p$, и тогда уже заменяете его на 0 именно потому, что $k!$ взаимно просто с $p$.

-- Сб июн 04, 2011 15:13:07 --

Доказать обратное можно по контрапозиции: для $C^k_{n-1}$ взять $q|n$ и $k=q$ и показать, что соотношение неверно.

сахар писал(а):

(Для непростых $p$ сравнение может верно для некоторых $k$; например, для $p=4$ сравнение нарушается только при $k=2$.)

Контрпример как бы намекает: $2$ делит $4$.

[caxap]

Sonic86 в сообщении #453898 писал(а):

Разбиваете числитель на 2 слагаемых, в первом выносите $p$, и тогда уже заменяете его на 0 именно потому, что $k!$ взаимно просто с $p$.

Ааа, ясно. Спасибо.

-- 04 июн 2011, 13:42 --

Sonic86 в сообщении #453898 писал(а):

Доказать обратное можно по контрапозиции: для $C^k_{n-1}$ взять $q|n$ и $k=q$ и показать, что соотношение неверно.

Спасибо! Получилось