Малая теорема Ферма: различия между версиями

Текущая версия на 06:22, 16 сентября 2019

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

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

@@ Строка 19: / Строка 19: @@
 $a^{p-1} \equiv 1 \mod p$.
 }}
-МТФ используют для вероятностной проверки чисел на простоту. Например, чтобы проверить, является ли число $n$ простым, возьмем какой-нибудь остаток $a$ по модулю $n$ и проверим, выполняется ли для этой пары чисел МТФ: если $a^{n - 1} \ne 1 \mod n$, то число $n$ точно составное. Иначе если
-$a^{n - 1} \equiv 1 \mod n$, то есть повод считать число $n$ простым. В таком случае число $a$ называют <em>свидетелем простоты числа $n$</em>. Чем больше свидетелей простоты, тем больше вероятность того, что число $n$ действительно простое.
 {{Автор|Полина Романченко|Romanchenko}}
 [[Категория:Конспект]]
 [[Категория:Теория чисел]]