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