Что такое обратный элемент по модулю?
Мультипликативный обратный элемент целого числа 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.
Пошагово: расширенный алгоритм Евклида вручную
Обратный элемент числа a по модулю m — это число x, для которого \(a \cdot x \equiv 1 \pmod{m}\). Он существует только при \(\gcd(a, m) = 1\). Расширенный алгоритм Евклида находит его за три шага.
- Последовательное деление. Разделите m на a, затем предыдущий делитель на остаток и так далее, пока остаток не станет равен 0. Последний ненулевой остаток — это НОД. Если он не равен 1, обратного элемента не существует.
- Представьте 1 как линейную комбинацию. Двигайтесь назад (обратная подстановка) или отслеживайте коэффициенты по ходу вычислений, чтобы записать \(1 = a \cdot x + m \cdot y\). Это тождество Безу.
- Приведите 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\)), тогда как расширенный алгоритм Евклида этого не требует, поэтому для произвольных модулей он обычно быстрее.