homechevron_rightУчебаchevron_rightМатематикаchevron_rightАлгебра

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

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

Эта страница существует благодаря следующим персонам

Timur
Timur

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

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.

Комментарии