теория-чисел - ТЧ. Сравнимость биномиальных коэффициентов

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

Возьмём число сочетаний и запишем его как $%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}$%.