Обратный элемент в кольце по модулю

Нахождение с помощью Бинарного возведения в степень

Воспользуемся теоремой Эйлера:

$a ^ {\phi(m)} \equiv 1 \pmod m,$

которая верна как раз для случая взаимно простых

и .

Кстати говоря, в случае простого модуля

мы получаем ещё более простое утверждение — малую теорему Ферма:

$a^{m-1} \equiv 1 \pmod m.$

$a^{-1}$

Умножим обе части каждого из уравнений на , получим:

$a^{\phi(m)-1} \equiv a^{-1} \pmod m,$

$a^{m-2} \equiv a^{-1} \pmod m.$

Таким образом, мы получили формулы для непосредственного вычисления обратного.