Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 13 стр.

Глава 1. Простые числа                                                  14

1.3. Решето Эратосфена и критерии простоты
     Очевидно, что любое простое число, не равное 2, является нечетным.
Существуют признаки делимости целых чисел на различные простые числа,
например, чтобы число в десятичном виде делилось на 3 и 9 достаточно,
чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число
делилось на 5, достаточно, что его последняя цифра была 0 или 5.
      Такие частные признаки делимости можно использовать, если нужно
уменьшить множество кандидатов проверки на простоту или отсечь заведомо
составные числа. Альтернативным способом получения простых чисел
является решето Эратосфена, приписываемое древнегреческому ученому
Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э.
      Для нахождения множества простых до заранее выбранной верхней
границы B мы сначала выписываем последовательность всех нечетных чисел
от 3 до B . Затем выбираем первое число в списке, т.е. тройку, и оставляя
его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко
второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму
пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут
только простые числа.

Малая теорема Ферма

     Знаменитый французский математик Пьер Ферма (1601–1665) доказал
теорему, которая известна как малая теорема Ферма.

Теорема 1.2. (Малая теорема Ферма) Если число p–простое, то для
любого натурального числа, не сравнимого с p выполняется сравнение

                            ap−1 ≡ 1 ( mod p)                         (1.1)

      Эта теорема является частным случаем теоремы Лагранжа (теор.1.1).
Действительно, при простом p множество ненулевых элементов кольца Zp
образует группу по умножению, имеющую p − 1 элемент. Будем обозначать
это множество через Zp∗ . По теореме Лагранжа порядок любого элемента
a ∈ Zp∗ является делителем порядка p − 1, откуда ap−1 ≡ 1 ( mod p).