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

Калькулятор вычисляет обратный элемент по модулю.

Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.

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

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

Обратный элемент
 

Обратным к числу a по модулю m называется такое число b, что:
ab \equiv 1 \pmod m,
Обратный элемент обозначают как a^{-1}.

Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.

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

Для того, чтобы показать это, рассмотрим следующее уравнение:

ax + my = 1

Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если {\rm gcd}(a,m)=1.
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:

ax = 1 \pmod m

Таким образом, найденное x и будет являться обратным к a.

Ссылка скопирована в буфер обмена
PLANETCALC, Обратный элемент в кольце по модулю

Комментарии