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