Калькулятор мультипликативного обратного по модулю

Введите расчет

Целое число a

Модуль m

Результатов

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

4

a^-1 mod m

НОД(a, m)	1
Обратный элемент существует	Да

Что такое мультипликативный обратный элемент по модулю m?

Мультипликативный обратный по модулю элемент целого числа a по модулю m — это такое целое число x в диапазоне от 1 до m−1, что \((a \cdot x) \bmod m = 1\). Иными словами, если умножить a на x и поделить результат на m, в остатке получится ровно 1. По сути это аналог деления на a в модулярной арифметике, и именно он лежит в основе теории чисел и криптографии: генерации ключей RSA, хеширования, китайской теоремы об остатках и многого другого.

Modular arithmetic wraps the number line into a circle of m positions.

Как пользоваться калькулятором

Введите целое число a и модуль m (m должно быть не меньше 2). Калькулятор приводит a по модулю m, запускает расширенный алгоритм Евклида и возвращает обратный элемент, если он существует. Отрицательные значения a обрабатываются автоматически — они приводятся к диапазону от 0 до m−1.

Разбираем формулу

Обратный элемент существует тогда и только тогда, когда НОД(a, m) = 1, то есть у a и m нет общих делителей, кроме единицы (они взаимно простые).

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$

Расширенный алгоритм Евклида находит целые числа s и t, для которых выполняется равенство \(a \cdot s + m \cdot t = \gcd(a, m)\). Если НОД равен 1, то коэффициент s, приведённый по модулю m, и есть искомый обратный элемент. Если же НОД(a, m) ≠ 1, обратного элемента не существует.

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

Разбор примера

Найдём обратный элемент к 3 по модулю 11. Нам нужно такое x, что \((3 \cdot x) \bmod 11 = 1\). Подбором: \(3 \cdot 4 = 12\), а \(12 \bmod 11 = 1\). Значит, обратный элемент равен 4. Расширенный алгоритм Евклида даёт тот же ответ мгновенно, ведь \(\gcd(3, 11) = 1\).

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

Частые вопросы

Когда обратного элемента не существует? Когда a и m не являются взаимно простыми. Например, у числа 4 нет обратного по модулю 8, потому что \(\gcd(4, 8) = 4 \neq 1\).

Обязательно ли модуль должен быть простым числом? Нет. Подходит любой модуль, лишь бы a был взаимно прост с ним. Если же m — простое число, то обратный элемент есть у каждого ненулевого a от 1 до m−1.

Почему результат всегда лежит между 1 и m−1? Потому что мы приводим обратный элемент по модулю m, чтобы получить канонический наименьший положительный представитель.