Вычисление мультипликативных обратных элементов по заданному модулю

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце Z_p.


Теорема

Пусть \bar a \in Z_p, тогда класс a имеет мультипликативный обратный элемент по модулю p тогда и только тогда, когда (a, p) = 1.


Теорема

Характеристика \lambda конечного поля – простое число.


Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.


Первый способ

Из условия (a, p) = 1 получаем a \cdot x + p \cdot y = 1 или a \cdot x \equiv 1 \pmod{p} и, следовательно, x – мультипликативный обратный к a по модулю p.


Второй способ

Напомним теорему Эйлера.

Определение

Функция Эйлера \varphi (n) — это количество чисел от 1 до n, взаимно простых с n.


Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с n равен единице.


Tеоремa Эйлера

Если a и p взаимно просты, то a^{\varphi(p)} \equiv 1 \pmod p, где \varphi (n) - функция Эйлера.


Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.

Доказательство

Пусть x_1, \dots, x_{\varphi(p)} — все различные натуральные числа, меньшие p и взаимно простые с ним.

Рассмотрим все возможные произведения x_i a для всех i от 1 до \varphi(p).

Поскольку a взаимно просто с p и x_i взаимно просто с p, то и x_i a также взаимно просто с p, то есть x_i a \equiv x_j\pmod p для некоторого j.

Отметим, что все остатки x_i a при делении на p различны. Действительно, пусть это не так, то существуют такие i_1 \neq i_2, что

x_{i_1} a \equiv x_{i_2} a\pmod p

или

(x_{i_1} - x_{i_2}) a \equiv 0\pmod p.

Так как a взаимно просто с p, то последнее равенство равносильно тому, что

x_{i_1} - x_{i_2} \equiv 0\pmod p или x_{i_1} \equiv x_{i_2}\pmod p.

Это противоречит тому, что числа x_1, \dots, x_{\varphi(p)} попарно различны по модулю p.

Перемножим все сравнения вида x_i a \equiv x_j\pmod p. Получим:

x_1 \cdots x_{\varphi(p)} a^{\varphi(p)} \equiv x_1 \cdots x_{\varphi(p)}\pmod p

или

x_1 \cdots x_{\varphi(p)} (a^{\varphi(p)}-1) \equiv 0\pmod p.

Так как число x_1 \cdots x_{\varphi(p)} взаимно просто с p, то последнее сравнение равносильно тому, что

a^{\varphi(p)}-1 \equiv 0\pmod p

или

a^{\varphi(p)} \equiv 1\pmod p.


В частном случае, когда p простое, теорема Эйлера превращается в так называемую малую теорему Ферма:

Малая теорема Ферма

Если p - простое число и a - произвольное целое число, не делящееся на p, то a^{p-1} \equiv 1 \pmod p .


Следствие

В кольце Z_p классов вычетов по модулю p из (\bar a, p) = 1 следует, что a^{-1} = a^{-{\varphi}(p)-1}.


Таким образом, для вычисления мультипликативного обратного к классу a по модулю p в случае, когда (\bar a, p) = 1, достаточно \bar a возвести в степень k, где k = p-2, если p – простое число, и k = {{\varphi}(p)-1} в противном случае.


При таком методе вычисления мультипликативного обратного элемента задача сводится к цепочке умножений и делений с остатком на модуль p. Эта задача решается без особых трудностей, если наименьший положительный вычет a \in \bar a, где (\bar a, p) = 1, представлен в СОК.

Однако, вообще говоря, {{\varphi}(p)-1} не является наименьшим показателем степени, для которого (\bar a)^{-1} = (\bar a)^{{\varphi}(p)-1}.

Разложение кольца вычетов

Из китайской теоремы об остатках следует

Утверждение

Пусть p = n_{1}^{l_1} \cdot n_{2}^{l_2} \cdot \ldots \cdot n_{k}^{l_k} - каноническое представление числа p. Тогда функция, которая каждому классу \bar x \in Z_m ставит в соответствие кортеж (x_1, x_2, \ldots, x_k), где  x \equiv x_i \pmod {p_{i}^{l_i}}, i=1, \ldots, k, является кольцевым изоморфизмом кольца Z_p класса вычетов по модулю p и кольца кортежей вида (x_1, x_2, \ldots, x_k), где \bar x \in Z_{p_i^k}, i=1, \ldots, k.

Более того, если обозначить через * любую из кольцевых операций + или \cdot , то

(x_1, x_2, \ldots, x_k)*(y_1, y_2, \ldots, y_k) = (x_1 * y_1, x_2 * y_2, \ldots, x_k * y_k).

Таким образом,

Z_p \cong Z_{n_1}^{l_1} \times Z_{n_2}^{l_2} \times \ldots \times Z_{n_k}^{l_k},

т.е. кольцо классов вычетов по модулю p раскладывается в прямое произведение колец классов вычетов по модулям n_{1}^{l_1}, n_{2}^{l_2}, \ldots, n_{k}^{l_k}. Это разложение колец индуцирует разложение групп их обратимых элементов:

U_p \cong U_{n_1}^{l_1} \times U_{n_2}^{l_2} \times \ldots \times U_{n_k}^{l_k}.


Можно сделать вывод о том, что произвольное целое положительное число A, 0 < A < P, где p = p_1 \cdot p_2 \cdot \ldots \cdot p_k и (p_i,p_j) = 1 для i \not = j, однозначно представимо своими наименьшими неотрицательными остатками по модулям p_i, причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.