Малая теорема Ферма
Ошибка.
Попробуйте повторить позже
Малая теорема Ферма. Для любого простого 
и взаимно простого с 
числа 
верно, что 
(mod 
)
Подсказка 1
Попробуем доказать по индукции, что a^p - a делится на р. База a=1 очевидна. Как сделать переход от а к а+1?
Подсказка 2
Что мы можем сказать про делимость на p для биномиальных коэффициентов в выражении (а+1)^p?
Подсказка 3
p!/(k!(p-k)!) делится на р для всех k кроме 0 и р, поскольку числитель делится на р, а знаменатель - нет. Что тогда останется, если смотреть на выражение по модулю p?
Первое решение.
Давайте возьмем две разные ПрСВ по одному модулю 
и перемножим в каждой все числа. Так как наборы остатков одинаковые, то
получившиеся произведения будут сравнимы по модулю 
.
Тогда рассмотрим две такие ПрСВ: [1, 2, ..., 
] и [
, 
, ..., 
] (То, что написано справа - это 
ПрСВ) и перемножим в
каждой все числа.
Получаем, что 
(mod 
) или 
(mod 
). Теперь перепишем это через
разность, то есть 
делится на 
. Из-за того, что НОД(
, 
) = 1 следует, что 
делится на 
или 
(mod 
)
_________________________________________________________________________________________________________________________________________________________________________________
Второе решение.
Зафиксируем простое число 
Проверим базу индукции: 
Тогда действительно 
— делится на 
Пусть 
делится на 
Докажем, что 
делится на 
Докажем, что для 
число 
делится на 
Действительно, 
В каждом из факториалов 
и 
все сомножители меньше 
а потому взаимно просты
с 
Тогда, поскольку 
делится на 
то и 
делится на 
Благодаря этому утверждению и биному Ньютона,
получаем
По предположению индукции 
чтд.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
