Бином. коэффициенты от простых

[SiberianSemion]

Пусть $n -$ положительное целое. Для любого простого $p > 3$ показать, что

$$C_{np}^{p}-C_{np}^{2p}+C_{np}^{3p}-C_{np}^{4p}+\cdots+(-1)^{n-1}C_{np}^{np}\equiv 1 \pmod {p^3}.$$

Задача из недавно прошедшей олимпиады, хотя и относится к почтенному фольклору.

[nnosipov]

SiberianSemion
К сожалению, чтобы решить эту задачу, достаточно слегка погуглить. Пишем в поисковой строке "binomial coefficients modulo p", попадаем в википедию, она нам подсовывает статью A. Cranville, в ней почти сразу натыкаемся на (очевидно, классический) результат Ljunggren (1952)

$$C_{np}^{mp} \equiv C_{n}^m \pmod{p^3}$$

И задача решена. На все ушло примерно минута.

Неужели это и есть прогресс?

[kotenok gav]

nnosipov в сообщении #1446296 писал(а):

$$C_{np}^{mp} \equiv C_{n}^m \pmod{p^3}$$

Встречал этот факт в Википедии. У него есть какое-то название и есть еще название для простых $p$, не удволетворяющих этому сравнению для $p^4$.

[Утундрий]

(Оффтоп)

Не это ли свойство биномиальных коэффициентов на заре своей карьеры открыл профессор Мориарти?

[nnosipov]

Утундрий

(Оффтоп)

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

[kotenok gav]

nnosipov

(Оффтоп)

"Последнее дело Холмса". Холмс упоминает, что Мориарти написал трактат о биноме Ньютона.

[nnosipov]

kotenok gav

(Оффтоп)

Спасибо.

[wrest]

Тогда надо переформулировать задачу и спросить для каких $n,p$ справедливо равенство.
Ясно, что оно верно не только для простых $p>3$ и целых $n$

[SiberianSemion]

Задача эта не крепкий орешек, а скорее конфета Фереро Рошер)

Факт, лежащий в основе решения, восходит аж к теореме Вольстенхольма 1862 года. Он не содержит таких уж глубоких идей, и наверняка у таких мэтров, как Кнут или Слоан, она значится как нетрудная разминка. Но он допускает доказательства, которые не лишены изящества. Одно из них приведено в статье Винберга про бином. коэффициенты в "Математическом просвещении" - в википедии есть как раз ссылка на эту статью. Там же в википедии есть доказательство в комбинаторном духе.

nnosipov в сообщении #1446296 писал(а):

Неужели это и есть прогресс?

Да, видимо . То, что практически любой за минуту может найти необходимый факт, при желании ознакомиться с соответствующими идеями и усвоить для себя нечто полезное или занимательное, есть, безусловно, прогресс.

[nnosipov]

wrest в сообщении #1446405 писал(а):

Тогда надо переформулировать задачу и спросить для каких $n,p$ справедливо равенство.

Не надо, все равно ничего интересного не получится (еще один тип псевдопростых чисел, но их и так хватает).

SiberianSemion в сообщении #1446423 писал(а):

Одно из них приведено в статье Винберга про бином. коэффициенты в "Математическом просвещении" - в википедии есть как раз ссылка на эту статью.

Статья Винберга у меня была на тот случай, если бы википедии не хватило (кстати, я имел в виду вот эту статью https://en.wikipedia.org/wiki/Lucas's_theorem).

SiberianSemion в сообщении #1446423 писал(а):

при желании ознакомиться с соответствующими идеями и усвоить для себя нечто полезное или занимательное

Боюсь, это очень недолговечное знание (потому что получено без всяких усилий). Завтра уже забудется.

[wrest]

nnosipov в сообщении #1446424 писал(а):

Не надо, все равно ничего интересного не получится (еще один тип псевдопростых чисел, но их и так хватает).

А мне показалось, что для нечетных $n$ сумма остатков всех слагаемых кроме поледнего равна нулю, и соответственно остаток суммы равен остатку последнего слагаемого, т.е. независимо от $p$,

$$C_{np}^{p}-C_{np}^{2p}+C_{np}^{3p}-C_{np}^{4p}+\cdots+(-1)^{n-1}C_{np}^{np} = (-1)^{n-1}C_{np}^{np} = C_{np}^{np}=1$$

Это следует из
$C_{np}^{kp}=C_{np}^{(n-k)p}$ которые в сумме идут с разными знаками, т.е. взаимно сокращаются, и простота $p$ тут никакая не нужна.
Остается последнее слагемое $(-1)^{n-1}C_{np}^{np}$ равное единице в случае нечетного $n$.

[nnosipov]

wrest в сообщении #1446450 писал(а):

А мне показалось, что для нечетных $n$ ...

Да, для нечетных $n$ все тривиализуется. Но в случае четного $n$ вряд ли что-то упростится.

Вообще, можно заняться одним сравнением (from Ljunggren), а про сумму забыть. Там тоже можно рассматривать составные $p$. Вот конкретный вопрос: для данного $n$ существует ли составное $p$, для которого

$$C_{np}^{mp} \equiv C_{n}^m \pmod{p^3}$$

для всех $m$, $1 \leqslant m \leqslant n$?

Кстати, вот пример утверждения, показывающий, что на подобный вопрос может быть и отрицательный ответ: число $n \geqslant 2$ является простым тогда и только тогда, когда $C_{n-1}^k \equiv (-1)^k \pmod{n}$ для всех $k$, $0 \leqslant k \leqslant n-1$.