http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=77.87.101.148&*Викиконспекты - Вклад участника [ru]2026-04-24T19:39:48ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D1%81%D1%82_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B8_%D1%87%D0%B8%D1%81%D0%B5%D0%BB_%D0%BD%D0%B0_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%83,_%D1%87%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%80%D0%BC%D0%B0%D0%B9%D0%BA%D0%BB%D0%B0&diff=71745Тест Ферма проверки чисел на простоту, числа Кармайкла2019-07-18T15:25:08Z<p>77.87.101.148: </p>
<hr />
<div>{{В разработке}}<br />
{{Теорема<br />
|id=th1<br />
|about=Малая теорема Ферма<br />
|statement=<br />
Если <tex>p</tex> простое и <tex>a</tex> не делится на <tex>p</tex>, то <tex>a^{p-1}\equiv 1\pmod p</tex><br />
}}<br />
На основании этой теоремы можно построить достаточно мощный тест на простоту:<br />
<br />
===Тест Ферма===<br />
Для любого <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> {{---}} слабовозможно простое.<br />
<br />
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.<br />
<br />
[[Категория: Теория чисел]]</div>77.87.101.148