Малая теорема Ферма
Малая теорема Ферма (МТФ)
Утверждение: (Малая теорема Ферма)
Пусть $p$ - простое число, $a$ - целое число, которое не делится на $p$. Тогда $a^{p - 1} \equiv 1 \mod p$.
Доказательство:
Рассмотрим числа $a, 2a, 3a, ... ,(p - 1)a$. Заметим, что в данном наборе присутствуют все остатки от $1$ до $p - 1$ (доказательство остается читателю в качестве упражнения).
Перемножим эти числа: слева остались числа в исходном виде, а справа мы пользуемся тем, что данный набор содержит все остатки от $1$ до $p - 1$.
$a \cdot 2a \cdot 3a \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \dots \ \cdot (p - 1) \mod p$
$(p-1)!a^{p-1} \equiv (p-1)! \mod p$
Так как $p$ - простое число, то оно взаимно просто с любым числом от $1$ до $p - 1$, то есть и с $(p - 1)!$. Поэтому мы можем сократить факториал в двух частях равенства. Получим:
$a^{p-1} \equiv 1 \mod p$.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko