2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Бином. коэффициенты от простых
Сообщение22.03.2020, 13:14 
Аватара пользователя


24/03/19
147
Пусть $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}.$$
Задача из недавно прошедшей олимпиады, хотя и относится к почтенному фольклору.

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 15:13 
Заслуженный участник


20/12/10
8858
SiberianSemion
К сожалению, чтобы решить эту задачу, достаточно слегка погуглить. Пишем в поисковой строке "binomial coefficients modulo p", попадаем в википедию, она нам подсовывает статью A. Cranville, в ней почти сразу натыкаемся на (очевидно, классический) результат Ljunggren (1952) $$C_{np}^{mp} \equiv C_{n}^m \pmod{p^3}$$ И задача решена. На все ушло примерно минута.

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 16:26 


21/05/16
4292
Аделаида
nnosipov в сообщении #1446296 писал(а):
$$C_{np}^{mp} \equiv C_{n}^m \pmod{p^3}$$

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 16:33 
Заслуженный участник
Аватара пользователя


15/10/08
11533

(Оффтоп)

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 17:28 
Заслуженный участник


20/12/10
8858
Утундрий

(Оффтоп)

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 17:30 


21/05/16
4292
Аделаида
nnosipov

(Оффтоп)

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение22.03.2020, 17:32 
Заслуженный участник


20/12/10
8858
kotenok gav

(Оффтоп)

Спасибо.

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение23.03.2020, 01:26 


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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение23.03.2020, 06:51 
Аватара пользователя


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

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

nnosipov в сообщении #1446296 писал(а):
Неужели это и есть прогресс?

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

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение23.03.2020, 07:15 
Заслуженный участник


20/12/10
8858
wrest в сообщении #1446405 писал(а):
Тогда надо переформулировать задачу и спросить для каких $n,p$ справедливо равенство.
Не надо, все равно ничего интересного не получится (еще один тип псевдопростых чисел, но их и так хватает).
SiberianSemion в сообщении #1446423 писал(а):
Одно из них приведено в статье Винберга про бином. коэффициенты в "Математическом просвещении" - в википедии есть как раз ссылка на эту статью.
Статья Винберга у меня была на тот случай, если бы википедии не хватило (кстати, я имел в виду вот эту статью https://en.wikipedia.org/wiki/Lucas's_theorem).
SiberianSemion в сообщении #1446423 писал(а):
при желании ознакомиться с соответствующими идеями и усвоить для себя нечто полезное или занимательное
Боюсь, это очень недолговечное знание (потому что получено без всяких усилий). Завтра уже забудется.

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение23.03.2020, 12:05 


05/09/16
11466
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$.

 Профиль  
                  
 
 Re: Бином. коэффициенты от простых
Сообщение23.03.2020, 13:04 
Заслуженный участник


20/12/10
8858
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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group