Тест Ферма проверки чисел на простоту, числа Кармайкла — различия между версиями
м (добавлена категория) |
|||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 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
Эта статья находится в разработке!
| Теорема (Малая теорема Ферма): |
Если простое и не делится на , то |
На основании этой теоремы можно построить достаточно мощный тест на простоту:
Тест Ферма
Для любого выбираем , вычисляем , если результат не , то составное, если , то — слабовозможно простое.
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания существует бесконечно много псевдопростых чисел по основанию . Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.
