Просмотр исходного текста страницы Тест Ферма проверки чисел на простоту, числа Кармайкла

{{В разработке}}
{{Теорема
|id=th1
|about=Малая теорема Ферма
|statement=
Если <tex>p</tex> простое и <tex>a</tex> не делится на <tex>p</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>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.

[[Категория: Теория чисел]]