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

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

1. Простые числа
      Натуральное число называется простым, если оно делится только на
себя и на 1. Число, не являющееся простым, называется составным.
      В этой главе мы дадим описание простейших алгоритмов проверки
простоты. Однако, прежде чем приступить к описанию основных алгоритмов,
дадим некоторые сведения из элементарной теории чисел.


1.1. Модулярная арифметика
      Пусть Z обозначает множество целых чисел, а p ≥ 2–целое число.
Условие, что целое число a делится нацело на b будем записывать через b|a.

Определение 1.1. Говорят, что два целых числа a и b сравнимы по
модулю p, записывается,

             a ≡ b ( mod p),

если p|(a − b).

      Отношение сравнения по модулю натурального числа обладает
следующими свойствами:
       1. Симметричность: a ≡ a ( mod p).
       2. Рефлексивность: a ≡ b ( mod p) → b ≡ a ( mod p).
       3. Транзитивность: a ≡ b ( mod p) & b ≡ c ( mod p) → a ≡ c ( mod p).

      Значит отношение сравнения по модулю является отношением
эквивалентности на множестве целых чисел. Классы эквивалентности,
образованные целыми числами по этому отношению, называются вычетами.
Вычет, содержащий число k , обозначается k . Множество классов вычетов
по модулю числа натурального n > 0 содержит ровно n элементов,
записываемых как Z n = {0, 1, ... n − 1}.
      Над вычетами можно выполнять арифметические операции сложения,
вычитания, умножения и возведения в степень, а если число n простое или