Малая теорема Ферма

Первое решение.

Давайте возьмем две разные ПрСВ по одному модулю и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю .

Тогда рассмотрим две такие ПрСВ: [1, 2, ..., ] и [, , ..., ] (То, что написано справа - это ПрСВ) и перемножим в каждой все числа.

Получаем, что (mod ) или (mod ). Теперь перепишем это через разность, то есть делится на . Из-за того, что НОД(, ) = 1 следует, что делится на или (mod )

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Зафиксируем простое число Проверим базу индукции: Тогда действительно — делится на Пусть делится на Докажем, что делится на Докажем, что для число делится на Действительно, В каждом из факториалов и все сомножители меньше а потому взаимно просты с Тогда, поскольку делится на то и делится на Благодаря этому утверждению и биному Ньютона, получаем

По предположению индукции чтд.