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

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

является некоторой степенью простого числа, то и деление. Будем обозначать
множество вычетов по модулю n через Zn .
      Отметим, что для любых a и b выполняется формула a + b = a + b
(то же для других перечисленных выше операции), поэтому операции над
вычетами выполняются как над обычными числами, приводя результат к
значению, принадлежащему интервалу [0, n−1] путем выполнения операции
вычисления остатка от деления результата на число n (т.е. операции,
обозначаемой mod n). Например, в множестве Z7 2 · 5 = 10 = 3 ( mod 7).
Чаще пишут просто: 2 · 5 = 3 ( mod 7).
      Множество классов вычетов по модулю n образует структуру,
являющуюся кольцом. Кольцом            K    называется непустое множество
элементов, на котором определены две арифметические операции сложения
+ и умножения ·, относительно которых выполняются следующие формулы:

1. Ассоциативность по сложению: (∀a, b, c ∈ K) a + (b + c) = (a + b) + c,
2. Существование нулевого элемента: (∃0 ∈ K)(∀a ∈ K) a + 0 = 0 + a = a,
3. Существование обратного элемента:        (∀a ∈ K)(∃b ∈ K) a + b = b + a =0,
4. Ассоциативность по умножению: (∀a, b, c ∈ K) a · (b · c) = (a · b) · c,
5. Дистрибутивность: (∀a, b, c ∈ K) a · (b + c) = a · b + a · c,
(b + c) · a = b · a + c · a.

      Обратный по сложению к a элемент обозначается через (−a).
Множество элементов, удовлетворяющих только первым трем свойствам,
называется группой. Если в группе < G, + > выполняется свойство
коммутативности a + b = b + a, то группа называется коммутативной или
абелевой. Очевидно, что группа по сложению кольца Z n является абелевой
группой.
      Если модуль n является простым числом или степенью простого числа
n = pk , где k ≥ 1–натуральное число, то множество ненулевых элементов
кольца Z n (обозначаемое через Z ∗n ) образует коммутативную группу по
умножению, т.е. существует нейтральный элемент 1 a·1=1·a, и для каждого
элемента a имеется обратный по умножению a−1 со свойством a · a−1 =1.