Вычисление обратных величин

В арифметике дествительных чисел нетрудно вычислить мультипликативную обратную величину а^–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 ³ имеет 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 = 18 элементов.

Число элементов в приведенном наборе вычетов характеризует функция Эйлера j(n).

Таблица 1.3.1 – Функция Эйлера j(n)

Модуль n	Функция j(n)
n n ² ... n^r	n – 1 n • (n – 1) ... n ^{r – 1} • (n – 1)
p • q (p, q - простые) ... ... _i^eⁱ (p _i- простые)	(p – 1) • (q – 1) ... ... _i^eⁱ (p _i– 1)

Иначе говоря, функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.

Малая теорема Ферма: если n – простое и НОД (а, n) = 1, то

а ^{n – 1}º 1 (mod n).

Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (а, n) = 1, то

а ^j⁽ⁿ⁾º 1 (mod n).

Если n – простое число, то предыдущий результат, учитывая, что j(n) = n – 1, приводится к виду (малой теоремы Ферма)

а ^{n – 1}º 1 (mod n).