homechevron_rightУчебаchevron_rightМатематикаchevron_rightГеометрия

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

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

Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/3311/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

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

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.

Комментарии