Решение

Пример

Найти все мультипликативные обратные пары в Z₁₁.

Мы имеем семь пар: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9) и (10, 10). При переходе от Z₁₀ к Z₁₁ число пар увеличивается. При Z₁₁ НОД (11, a) = 1 (взаимно простые) для всех значений a, кроме 0. Это означает, что все целые числа от 1 до 10 имеют мультипликативные инверсии.

Целое число a в Z_n имеет мультипликативную инверсию тогда и только тогда, если НОД (n, a) = 1(mod n)

Расширенный алгоритм Евклида, который мы обсуждали ранее в этой лекции, может найти мультипликативную инверсию b в Z_n, когда даны n и b и инверсия существует. Для этого нам надо заменить первое целое число a на n (модуль). Далее мы можем утверждать, что алгоритм может найти s и t, такие, что . Однако если мультипликативная инверсия b существует, НОД (n, b) должен быть 1. Так что уравнение будет иметь вид

(s × n) + (b × t) = 1

Теперь мы применяем операции по модулю к обеим сторонам уравнения. Другими словами, мы отображаем каждую сторону к Z_n. Тогда мы будем иметь

(s × n + b × t) mod n =1 mod n

[(s × n) mod n] + [(b × t) mod n] = 1 mod n

0 + [(b × t) mod n ] = 1

(b × t) mod n =1 Это означает, что t – это мультипликативная инверсия b в Z_n

Обратите внимание, что на третьей строке — 0, потому что, если мы делим , частное — s, а остаток — 0.

Расширенный алгоритм Евклида находит мультипликативные инверсии b в Z_n, когда даны n и b и НОД (n, b) = 1. Мультипликативная инверсия b — это значениеt, отображенное в Z_n.

Рисунок показывает, как мы находим мультипликативную инверсию числа, используя расширенный алгоритм Евклида.

Пример

Найти мультипликативную инверсию 11 в Z₂₆.