В арифметике дествительных чисел нетрудно вычислить мультипликативную обратную величину а–1 для ненулевого а:
а –1 = 1 / а или а • а –1 = 1.
Пример: мультипликативная обратная величина от числа 4 равна
1 / 4, поскольку
4 • 1 / 4 = 1.
В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения
4 • х ≡ 1 (mod 7)
эквивалетно нахождению таких значений х и k, что
4 • х ≡ 7 • k + 1,
где х и k – целые числа.
Общая формулировка этой задачи – нахождение такого целого числа х, что
а • х (mod n) = 1.
Можно также записать
а –1 ≡ х (mod n).
Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, т.к.
5 • 3 = 15 ≡ 1 (mod 14).
С другой стороны, число 2 не имеет обратной величины по модулю 14.
Вообще сравнение
а –1 ≡ х (mod n)
Имеет единственное решение, если а и n – взаимно простые числа.
Если числа а и n – не являются взаимно простыми, тогда сравнение
а –1 ≡ х (mod n)
не имеет решения.
Сформулируем основные способы нахождения обратных величин. Пусть целое число а Î {0, 1, 2, …, n - 1}.
Если НОД (а, n) = 1, то а • i (mod n) при i = 0, 1, 2, …, n – 1 является перестановкой множества {0, 1, 2, …, n - 1}.
Пример. Если а = 3 и n = 7 (НОД (3, 7) = 1), то 3 • i (mod 7)
при i = 0, 1, 2, …, 6 является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества {0, 1, 2, …, 6}.
Это будет неверным, когда НОД (а, n) ¹ 1.
Пример. Если а = 2 и n = 6, то 2 • i (mod 6) º 0, 2, 4, 0, 2, 4 при
i = 0, 1, 2, …, 5.
Если НОД (а, n) = 1, тогда существует обратное число а–1,
0 < а –1 < n, такое, что
а • а –1 º 1 (mod n).
Действительно, а • i (mod n) является перестановкой 0, 1, 2, …, n – 1, поэтому существует i такое, что
а • i º 1 (mod n).
Как отмечалось выше, набор целых чисел от 0 до n – 1 называется полным набором вычетов по модулю n. Это означает, что для любого целого числа а (а > 0) его вычет r = a (mod n) – это некоторое целое число в интервале от 0 до n – 1.
Выделим из полного набора вычетов подмножество вычетов взаимно простых с n. Такое подмножество называют приведенным набором вычетов.
Пример. Пусть модуль n = 11 – простое число. Полный набор вычетов по модулю 11: {0, 1, 2, …, 10}. При формировании приведенного набора вычетов из них удаляется только один элемент: 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10 элементов.
Таким образом, в общем случае приведенный набор вычетов по модулю простого числа n имеет n – 1 элемент.
Пример. Пусть модуль n = 10. Полный набор вычетов по модулю 10: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:
| (один элемент), | |
| кратные 2 | (четыре элемента), |
| кратные 5 | (один элемент), |
т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 6 = 4. Таким образом, в приведенном наборе вычетов четыре элемента.
Для произведения простых чисел p • q = n приведенный набор вычетов имеет ( p – 1) • (q – 1) элементов.
Пример. При n = p • q = 2 • 5 = 10 число элементов в приведенном наборе будет (p – 1) • (q – 1) = (2 – 1) • (5 – 1) = 4.
Пример. Приведенный набор вычетов по модулю 27 = 3 3 имеет 18 элементов: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}. Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов).
Отсюда: Для модуля в виде простой степени n r приведенный набор вычетов имеет n r – 1 • (n – 1) элемент.
При n = 3, r = 3 получаем 3 3 –1 • (3 – 1) = 3 2 • 2 = 18 элементов.
Число элементов в приведенном наборе вычетов характеризует функция Эйлера j(n).
Таблица 1.3.1 – Функция Эйлера j(n)
| Модуль n | Функция j(n) |
| n n 2 ... n r | n – 1 n • (n – 1) ... n r – 1 • (n – 1) |
p • q (p, q - простые)
...
...
 i ei (p i - простые)
| (p – 1) • (q – 1)
...
...
i ei (p i – 1)
|
Иначе говоря, функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.
Малая теорема Ферма: если n – простое и НОД (а, n) = 1, то
а n – 1 º 1 (mod n).
Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (а, n) = 1, то
а j(n) º 1 (mod n).
Если n – простое число, то предыдущий результат, учитывая, что j(n) = n – 1, приводится к виду (малой теоремы Ферма)
а n – 1 º 1 (mod n).
