Тест Ферма проверки чисел на простоту, числа Кармайкла — различия между версиями
(Новая страница: «{{В разработке}} {{Теорема |id=th1 |about=Малая теорема Ферма |statement= Если <tex>p</tex> простое и <tex>a</tex> л…») |
м (добавлена категория) |
||
| Строка 14: | Строка 14: | ||
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями. | Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями. | ||
| + | |||
| + | [[Категория: Теория чисел]] | ||
Версия 08:32, 29 июня 2010
Эта статья находится в разработке!
| Теорема (Малая теорема Ферма): |
Если простое и любое, то
в частности, если не делитель , то |
На основании этой теоремы можно построить достаточно мощный тест на простоту:
Тест Ферма
Для любого выбираем , вычисляем , если результат не , то составное, если , то — слабовозможно простое.
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания существует бесконечно много псевдопростых чисел по основанию . Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.
