Пусть $%p$% – простое, $%m \ge 1$%, $%0\le k\le p–1$%. Докажите, что $%C_{mp+k}^p \equiv m \pmod p$%.

[Это тоже из готовящейся книжки по ТЧ. Желательно найти максимально простое решение в смысле простоты той техники, которая применяется в нём. Отдельно приветствуются комбинаторные решения]

задан 24 Сен '15 15:57

изменен 24 Сен '15 15:58

10|600 символов нужно символов осталось
3

Рассмотрим два доказательства. Первое -- теоретико-числовое.

Возьмём число сочетаний и запишем его как $%C_{mp+k}^p=\frac{(mp+k)\ldots mp\ldots}{p!}$%. Сократим $%p$% в числителе и знаменателе и домножим обе части сравнения на $%(p-1)!$%, что взаимно просто с $%p$%, поэтому получится равносильное сравнение.

В числителе исходной дроби присутствует $%p$% сомножителей, дающих разные остатки от деления на $%p$%. У всех чисел кроме $%mp$% эти остатки в каком-то порядке принимают значения от $%1$% до $%p-1$%, поэтому их произведение равно $%(p-1)!$% по модулю $%p$%. Таким образом, в левой части сравнения, равносильного исходному, будет $%m(p-1)!$%, а правая часть у нас такая же. Следовательно, сравнение верно.

Заметим, что теорема Вильсона здесь не использовалась.

Второе доказательство -- комбинаторное. Числа от $%1$% до $%mp+k$% разобьём на части $%A_1$%, ... , $%A_m$%, $%A$%, где каждая из частей вида $%A_i$% состоит из $%p$% подряд идущих чисел, а в $%A$% находятся последние $%k$% чисел. Нас интересует число способов выбрать $%p$% элементов множества $%A_1\cup\ldots\cup A_m\cup A$%. Среди них сразу выделяется $%m$% способов выбрать какую-то из частей вида $%A_i$% целиком. Докажем, что если мы никакую из этих частей целиком не забираем, то количество способов выбора делится на $%p$%.

Все способы выбора разобьём на группы "симметричных" друг другу, где в каждой группе будет $%p$% подмножеств из $%p$% элементов. Поскольку $%k < p$%, мы заведомо берём что-то из объединения $%A_1\cup\ldots\cup A_m$%. Пусть $%i$% -- наименьшее число, для которого мы что-то взяли из $%A_i$%. Подмножество $%B$% элементов, взятых из $%A_i$%, собственное непустое. Рассмотрим его циклические сдвиги $%B$%, $%B+1$%, ... , $%B+p-1$%, где сложение осуществляется по модулю $%p$%, а элементы $%A_i$% отождествляются с остатками от деления на $%p$%. Легко видеть, что все сдвиги попарно различны, поскольку $%p$% простое, и собственное непустое подмножество не может иметь нетривиального периода.

Тем самым, все способы выбора $%p$% элементов из общего количества, помимо $%m$% из них, мы разбили на группы равной численности по $%p$% элементов в каждой, откуда $%C_{mp+k}^p\equiv m\pmod{p}$%.

ссылка

отвечен 24 Сен '15 16:53

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×844
×50
×14

задан
24 Сен '15 15:57

показан
443 раза

обновлен
24 Сен '15 16:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru