Доказать сравнение.

[moscow5]

$\frac{-(k-1)(modp) ... 1(modp)}{(k-1)!(modp)}=-1^{k-1}(modp)$
И как теперь это связать с $C_p^k$
$\frac{C_p^k}{(-1)^{k-1}}=\frac{p}{k}$

[nnosipov]

Ну, свяжите как-нибудь между собой два биномиальных коэффициента $C_{p-1}^{k-1}$ и $C_p^k$. Индексы у них близки --- вот за это и цепляйтесь.

-- Пн фев 04, 2013 23:40:37 --

moscow5 в сообщении #680006 писал(а):

$\frac{C_p^k}{(-1)^{k-1}}=\frac{p}{k}$

Это что такое написано?

[moscow5]

$\frac{C_p^k}{C_{p-1}^{k-1}}=\frac{p}{k}$

[AKM]

$2\equiv7\pmod{5}$

$2\equiv7\pmod{5}$

post443191.html#p443191

[nnosipov]

Вот. То, что надо. Теперь возвращайтесь к сумме, которая в левой части сравнения, которое Вы хотите доказать. Попробуйте её преобразовать.

[moscow5]

Я не могу понять как расписать левую часть сравнения, используя взаимоотношение $C_p^k и C_{p-1}^{k-1}$
Расписываем каждое слагаемое по типу $ C_{n}^{n-3}=C_{n-1}^{n-4} \cdat \frac{n}{n-3}$ и так пока не получится что-то похожее на $ C_{3}^{0} * \frac{4}{1}$.

[nnosipov]

Левая часть --- это сумма $\sum_{k=1}^{p-1} \frac{(-1)^{k-1}}{k}$. А $(-1)^{k-1}$ по модулю $p$ мы можем заменить на ... что?

[moscow5]

Заменить на $C_{p-1}^{k-1}$?

[nnosipov]

Да, именно так. (Я умудрился спутать левую часть сравнения с правой, но Вы меня правильно поняли.) А дальше будут только тождественные преобразования, сравнения уже не понадобятся.

[moscow5]

Я запустался в ходе решения. Сначала мы представляем левую часть как у меня в первом посте (разложили на бином, вычли 2 и сократили на p). Потом правую часть представляем как сумму, делаем вашу замену и пытаемся как то привести к тому что получилось с левой частью сравнения?

[nnosipov]

Имеем

$$\sum_{k=1}^{p-1} \frac{(-1)^{k-1}}{k} \equiv \sum_{k=1}^{p-1} \frac{C_{p-1}^{k-1}}{k}=\sum_{k=1}^{p-1} \frac{C_p^k}{p}=\text{тому, что надо}\pmod{p}$$

Убедитесь в этом.

[moscow5]

$$\sum_{k=1}^{p-1}\frac{C_p^k}{p}=\sum_{k=1}^{p-1} \frac{C_{p-1}^{k-1}}{k}\equiv\sum_{k=1}^{p-1} \frac{(-1)^{k-1}}{k} =1-\frac{1}{2}+\frac{1}{3}...-\frac{1}{p-1}\pmod{p}$$

Спасибо за помощь!