Изменения
Нет описания правки
|about=Малая теорема Ферма
|statement=
Если <tex>p</tex> простое и <tex>a</tex> любое, то <tex>a^p\equiv a\pmod p</tex> в частности, если не делится на <tex>p</tex> не делитель <tex>a</tex>, то <tex>a^{p-1}\equiv 1\pmod p</tex>
}}
На основании этой теоремы можно построить достаточно мощный тест на простоту:
===Тест Ферма===
Для любого <tex>n>1</tex> выбираем <tex> a>1</tex>, вычисляем <tex>a^{n-1}\(mod n) </tex>, если результат не <tex>1</tex>, то <tex>n</tex> составное, если <tex>1</tex>, то <tex>n</tex> {{---}} слабовозможно простое.
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.
[[Категория: Теория чисел]]
