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

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

Растущий AI Skill PRO

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

Результаты

Обратный по модулю
4
x, при котором (a·x) mod m = 1
Обратный элемент существует Да
НОД(a, m) 1

Математическая формула

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
Статистика использования

Реклама

Сообщить об ошибке на этой странице

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

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

Числовая прямая, обёрнутая вокруг круглого кольца модуля как у часов, где a умножить на x попадает в 1
Обратный по модулю элемент x при умножении возвращает a к 1, замыкаясь вокруг модуля m.

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

Введите число 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.

Реклама
Плоская блок-схема шагов расширенного алгоритма Евклида, дающая НОД и коэффициенты
Расширенный алгоритм Евклида даёт коэффициенты, образующие обратный элемент, когда gcd(a, m) = 1.

Пример с решением

Найдём обратный элемент числа 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.

Пошагово: расширенный алгоритм Евклида вручную

Обратный элемент числа a по модулю m — это число x, для которого \(a \cdot x \equiv 1 \pmod{m}\). Он существует только при \(\gcd(a, m) = 1\). Расширенный алгоритм Евклида находит его за три шага.

  1. Последовательное деление. Разделите m на a, затем предыдущий делитель на остаток и так далее, пока остаток не станет равен 0. Последний ненулевой остаток — это НОД. Если он не равен 1, обратного элемента не существует.
  2. Представьте 1 как линейную комбинацию. Двигайтесь назад (обратная подстановка) или отслеживайте коэффициенты по ходу вычислений, чтобы записать \(1 = a \cdot x + m \cdot y\). Это тождество Безу.
  3. Приведите x по модулю. Возьмите \(x \bmod m\). Если x отрицательно, прибавляйте m (при необходимости несколько раз), чтобы получить число из диапазона от 0 до m − 1.

Разобранный пример: a = 7, m = 40.

Шаг Деление Частное q Остаток
1 40 = 5·7 + 5 5 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

Последний ненулевой остаток равен 1, поэтому \(\gcd(7, 40) = 1\), и обратный элемент существует.

Обратная подстановка:

$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$

Итак, \(7 \cdot (-17) + 40 \cdot 3 = 1\), откуда \(x = -17\).

Итеративная проверка (коэффициент t при a): начните с \(t_0 = 0\) (для m = 40) и \(t_1 = 1\) (для a = 7), затем используйте \(t_{k+1} = t_{k-1} - q_k \, t_k\).

Остаток Использованное q t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

Строка, где остаток становится равен 1, даёт \(t = -17\). Приведём его по модулю: \(-17 + 40 = \)23.

Проверка: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), так что \(161 \bmod 40 = 1\). ✓

Тот же метод работает и для больших чисел. Для a = 17, m = 3120 он даёт x = 2753, поскольку \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). Эта пара — классический учебный пример для RSA.

Реклама

Примеры входных данных и их обратных элементов

Каждый обратный элемент ниже удовлетворяет условию \((a \cdot x) \bmod m = 1\). Если \(\gcd(a, m) > 1\), обратного элемента не существует.

a m НОД(a, m) Обратное x Проверка
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 Нет 4x по модулю 6 всегда чётно, но никогда не равно 1
6 9 3 Нет 6x по модулю 9 всегда кратно 3, но никогда не равно 1

Обратите внимание, что 5 является обратным самому себе по модулю 12. В общем случае \(x^2 \equiv 1 \pmod{m}\) имеет решения, отличные от 1, поэтому некоторые числа являются самообратными.

Ключевые термины: взаимная простота, НОД, сравнение и вычет

  • Модуль (m): положительное целое число, при достижении которого значения «обнуляются», как на циферблате часов.
  • Сравнение (≡): запись \(a \equiv b \pmod{m}\) означает, что m делит \(a - b\), то есть a и b дают одинаковый остаток при делении на m.
  • НОД: наибольший общий делитель, наибольшее целое число, которое делит оба числа.
  • Взаимно простые (относительно простые): два целых числа, НОД которых равен 1. Именно это условие необходимо для существования обратного элемента по модулю.
  • Тождество Безу: для целых чисел a и m существуют целые x и y, такие что \(a \cdot x + m \cdot y = \gcd(a, m)\). Когда НОД равен 1, приведение этого равенства по модулю m даёт \(a \cdot x \equiv 1\), поэтому x является обратным элементом.
  • Класс вычетов: множество всех целых чисел, имеющих одинаковый остаток по модулю m. Обратный элемент однозначен как класс вычетов, а калькулятор выводит представитель из диапазона от 0 до m − 1.
  • Мультипликативный обратный элемент по модулю: вычет \(x = a^{-1} \bmod m\), для которого \(a \cdot x \equiv 1 \pmod{m}\).

Теорема Эйлера: если \(\gcd(a, m) = 1\), то \(a^{\varphi(m)} \equiv 1 \pmod{m}\), где \(\varphi\) — функция Эйлера. Поэтому обратный элемент можно также вычислить как \(a^{\varphi(m)-1} \bmod m\).

Малая теорема Ферма: когда m = p — простое число, \(\varphi(p) = p - 1\), поэтому \(a^{-1} \equiv a^{p-2} \pmod{p}\) для любого a, не делящегося на p. Пример: \(3^{9} = 19683 = 1789 \cdot 11 + 4\), значит \(3^{-1} \equiv 4 \pmod{11}\), что совпадает с таблицей выше. Формула со степенью требует разложения m на множители (чтобы найти \(\varphi\)), тогда как расширенный алгоритм Евклида этого не требует, поэтому для произвольных модулей он обычно быстрее.

Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика