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

Малая теорема Ферма (МТФ)

Утверждение: (Малая теорема Ферма)
Пусть $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