Что такое обратный элемент по модулю?
Мультипликативный обратный элемент целого числа a по модулю m — это такое целое число x, что \((a \cdot x) \bmod m = 1\). По сути это операция «деления» в модульной арифметике, играющая ключевую роль в теории чисел, криптосистеме RSA и многих алгоритмах теории кодирования. Наш калькулятор находит x с помощью расширенного алгоритма Евклида.
Как пользоваться калькулятором
Введите число a и модуль m (при условии m ≥ 2). Инструмент вернёт наименьший неотрицательный обратный элемент x в диапазоне 0 ≤ x < m, подтвердит, существует ли обратный элемент, и покажет НОД(a, m). Если НОД(a, m) ≠ 1, обратного элемента не существует, и в результате выводится «Нет».
Разбор формулы
Обратный элемент существует только тогда, когда \(\gcd(a, m) = 1\), то есть когда a и m взаимно просты. Расширенный алгоритм Евклида находит такие целые числа x и y, что $$a \cdot x + m \cdot y = \gcd(a, m).$$ Если НОД равен 1, то приведение x по модулю m даёт искомый обратный элемент. Результат нормализуется до положительного значения: если он отрицателен, к нему прибавляется m.
Пример с решением
Найдём обратный элемент числа 3 по модулю 11. Нам нужно такое x, что \(3x \equiv 1 \pmod{11}\). Проверим: $$3 \times 4 = 12 = 11 + 1,$$ поэтому \(12 \bmod 11 = 1\). Значит, x = 4. Расширенный алгоритм Евклида даёт тот же ответ, а \(\gcd(3, 11) = 1\) подтверждает, что обратный элемент существует.
Частые вопросы
Когда обратного элемента не существует? Когда у a и m есть общий делитель больше 1 — например, у числа 4 по модулю 6 (НОД = 2) обратного элемента нет.
Обязательно ли m должно быть простым? Нет. m может быть любым целым числом ≥ 2; важна только взаимная простота a и m.
В каком диапазоне находится ответ? Обратный элемент выводится как наименьший неотрицательный вычет — в диапазоне от 0 до m − 1.
