Калькулятор обратного элемента по модулю
Вычислите мультипликативный обратный элемент целого числа a по модулю m с помощью расширенного алгоритма Евклида.
Как работает этот калькулятор?
Обратный элемент числа a по модулю m — это целое число x из [0, m), при котором a·x ≡ 1 (mod m). Он существует только при gcd(a, m) = 1 и находится с помощью расширенного алгоритма Евклида с последующим приведением к положительному вычету. Если a и m имеют общий делитель, обратный элемент не существует.
Формула
How this is calculated
Число a приводится по модулю m к диапазону [0, m), а модуль m должен быть целым числом, большим 1. Затем к (a mod m, m) применяется расширенный алгоритм Евклида, который выдаёт как наибольший общий делитель gcd(a, m), так и коэффициент Безу x, удовлетворяющий уравнению a·x + m·y = gcd(a, m).
Обратный элемент по модулю существует только при gcd(a, m) = 1. Если это условие выполнено, необработанный коэффициент x может оказаться отрицательным, поэтому он приводится к диапазону [0, m) по формуле ((x mod m) + m) mod m. Возвращаемый обратный элемент удовлетворяет условию (a · x) mod m = 1, что отображается в поле проверки. Если gcd(a, m) ≠ 1, обратного элемента не существует, и вместо него выводится общий делитель.
Все вычисления выполняются с использованием BigInt для предотвращения потери точности при работе с большими целыми числами. Входные данные должны быть целыми числами; дробные значения отклоняются. Отрицательные значения a обрабатываются через приведение по модулю, поэтому, например, -8 mod 11 рассматривается как 3.
Часто задаваемые вопросы
Обратный элемент числа a по модулю m существует только тогда, когда a и m взаимно просты, то есть gcd(a, m) = 1. Если у них есть общий делитель, больший 1, то не существует целого числа x, удовлетворяющего a·x ≡ 1 (mod m).
Нет. Модуль может быть любым целым числом, большим 1. Если m простое, то у каждого a от 1 до m−1 есть обратный элемент, поскольку все они взаимно просты с m, но составные модули тоже работают для любого a, взаимно простого с m.
Число a сначала приводится к диапазону [0, m) перед запуском алгоритма, поэтому отрицательные входные данные обрабатываются через их положительный вычет. Полученный обратный элемент также нормализуется к диапазону [0, m).
Также известен как
TG we-Calculate Editorial Team. (2026). Калькулятор обратного элемента по модулю [Online calculator]. TG we-Calculate. https://we-calculate.com/ru/calculator/modular-inverse-calculator
TG we-Calculate Editorial Team. "Калькулятор обратного элемента по модулю." TG we-Calculate. 2026. https://we-calculate.com/ru/calculator/modular-inverse-calculator.
TG we-Calculate Editorial Team, "Калькулятор обратного элемента по модулю," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/ru/calculator/modular-inverse-calculator
@misc{wecalculate_modular_inverse_calculator, title = {Калькулятор обратного элемента по модулю}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/ru/calculator/modular-inverse-calculator}}, year = {2026}, note = {TG we-Calculate} }
Этот калькулятор вам помог?