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

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

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

Элемент

Модуль

Рассчитать

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

 

 Ссылка  Сохранить  Виджет

Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .

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

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

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

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

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