Мультипликативная инверсия

Решение

Пример

Найдите все взаимно обратные пары по сложению в Z₁₀.

Даны шесть пар аддитивных инверсий — (0, 0), (1, 9), (2, 8), (3, 7), (4, 6) и (5, 5). В этом списке 0 — инверсия самому себе; так же и 5. Обратите внимание: аддитивные инверсии сложения обратны друг другу; если 4 — аддитивная инверсия 6, тогда 6 — также аддитивная инверсия числу 4.

В Z_n два числа a и b мультипликативно инверсны друг другу, если

a × b 1(mod n)

Например, если модуль равен 10, то мультипликативная инверсия 3 есть 7. Другими словами, мы имеем .

В модульной арифметике целое число может иметь или может не иметь мультипликативную инверсию. Целое число и его мультипликативная инверсия сравнимы с 1 по модулю n.

Может быть доказано, что a имеет мультипликативную инверсию в Z_n, если только НОД(n, a) = 1. В этом случае говорят, что a и n взаимно простые.

Дата добавления: 2014-01-03