Что такое обратный по модулю
Обратный к a по модулю m — целое x с a x ≡ 1 (mod m), то есть a x − 1 делится на m. Раздел: теория чисел.
Существует тогда и только тогда, когда a и m взаимно просты. Коэффициенты Безу без приведения по модулю — расширенный Евклид. Остаток без уравнения ax ≡ 1 — остаток.
Тест: 3x ≡ 1 (mod 11). 3·4 = 12 ≡ 1. Другой: 1·x ≡ 1 (mod 7) → x = 1. Для 2 и 4 НОД = 2 ≠ 1 — обратного нет.
ax ≡ 1 (mod m)
a x ≡ 1 (mod m) при НОД(a, m) = 1
Калькулятор берёт расширенный алгоритм Евклида для a и m, проверяет НОД = 1 и приводит коэффициент при a к диапазону 0…m−1. Отрицательный a сначала приводят по модулю: −1 ≡ m−1.
Как пользоваться
Введите a и модуль m ≥ 2. Если взаимной простоты нет, будет ошибка — это правильный отказ, не «баг». Проверка: (a·x − 1) делится на m, или остаток a x при делении на m равен 1.
Примеры
Базовый. 3 по модулю 11 → 4.
Единица. 1 по модулю 7 → 1.
Нет обратного. 2 по модулю 4.
Ещё обратные
5 по модулю 12: НОД(5, 12) = 1, 5·5 = 25 ≡ 1. x = 5. Число может совпасть с самим a.
7 по модулю 10: 7·3 = 21 ≡ 1, x = 3. Не 7: 49 ≡ 9.
Связь с φ(m): a^{φ(m)−1} ≡ a⁻¹ (mod m) при взаимной простоте. Для малых m быстрее Евклид, как здесь. Не считайте огромную степень вручную.
Система сравнений с неизвестным x использует обратный внутри китайской теоремы об остатках. На этой странице одно сравнение ax ≡ 1, не два модуля.
Отрицательный a = −3, m = 11: −3 ≡ 8, обратный к 8. Или сразу Евклид к −3. Ответ всё равно в 0…10.
Не путайте с обычным 1/a в дроби: 1/3 не равно 4. Здесь арифметика остатков, не рациональных чисел.
a = 0: 0·x ≡ 1 невозможно при m ≥ 2. Ошибка взаимной простоты (НОД = m).
Проверка умножением обязательна. Нашли x = 4, 3·4 = 12, 12 − 1 = 11, делится. Если остаток 0, вы искали «обнулить», это другое сравнение.
Обычный НОД без Безу не выдаёт x. Если нужен только признак «есть ли обратный», достаточно взаимной простоты; само x — эта страница.
Степень a^{−1} в школьной записи для модулей как раз и есть этот x. Отрицательный показатель на странице степени по модулю запрещён — сначала найдите обратный, затем возводите его.
Два разных обратных в 0…m−1 быть не может: кольцо вычетов при простом модуле — поле, при составном взаимно простом a тоже один класс.
Итог: взаимная простота обязательна, ответ один в диапазоне модуля, проверка умножением. Коэффициенты Безу целиком — соседний расширенный Евклид.
Ещё: 8 по модулю 13. 8·5 = 40 ≡ 1, потому что 39 = 3·13. x = 5. Не 8·2 = 16 ≡ 3.
11 по модулю 26: НОД(11, 26)=1. 11·19 = 209, 209/26 = 8*26=208, остаток 1. x = 19. Долгий перебор от 1 до 25 как раз то, что Евклид экономит.
Сравнение ax ≡ b (mod m) при b ≠ 1 сводят к обратному: x ≡ b·a⁻¹. Эта страница даёт только a⁻¹. Умножьте в тетради и приведите по модулю.
Простой модуль p: любое a не кратное p обратимо. Составной 15: обратимы 1, 2, 4, 7, 8, 11, 13, 14 — как раз φ(15)=8 штук. Совпадает с функцией Эйлера.
Не ищите обратный к 10 по модулю 25: НОД=5. Уравнение 10x ≡ 1 (mod 25) неразрешимо, хотя 10x ≡ 5 (mod 25) уже другое дело и не эта страница.
Школьные формулировки
«Найдите число, обратное к 3 по модулю 11» — эта страница, ответ 4. «Решите 3x ≡ 1 (mod 11)» — то же. «Решите 3x ≡ 2 (mod 11)» — сначала 4, затем 8 в тетради, не поле x.
«Доказать, что обратного нет» достаточно НОД ≠ 1. Калькулятор как раз останавливается. Не тратьте перебор x = 0…m−1, если НОД уже больше единицы.
Не путайте с обратной матрицей и определителем: там ad − bc, здесь одно сравнение. И не с 1/a в дроби.
Проверка умножением в обе стороны: 4·3 = 12 ≡ 1 (mod 11) и 3·4 то же. Если получили 12 ≡ 0, искали делитель, не обратный. Для модуля 11 вычеты 0…10, ответ 4 уже в диапазоне, приводить ещё раз не нужно.
Связка с КТО: внутри двух сравнений как раз нужен обратный к m₁ по модулю m₂ (после сокращения на НОД). Отдельно его можно посчитать здесь и подставить в тетради.
Ещё число: 9 по модулю 16. 9·9=81, 5·16=80, остаток 1. Обратный совпал с самим 9. Такое бывает и не требует отдельной кнопки «самообратный».
Типичные ошибки
- Ждать обратный при чётных a и m.
- Путать x с обычной дробью 1/a.
- Оставлять отрицательный x, не приведя по модулю.
- Искать два сравнения на этой странице.
- Ставить модуль 1 или 0.
Частые вопросы
- Что такое обратный элемент по модулю m?
- Такое x, что a x ≡ 1 (mod m). Для 3 и 11 получите 4, потому что 12 даёт остаток 1 при делении на 11.
- Когда обратного нет?
- Если НОД(a, m) ≠ 1. Пример: 2 и 4. Сначала можно проверить взаимную простоту.
- Чем страница отличается от расширенного Евклида?
- Там ищут НОД и пару Безу ax + by = g. Здесь нужен только случай g = 1 и ответ x по модулю m. Полные коэффициенты — расширенный алгоритм Евклида.
- Нужна ли степень по модулю?
- aᵉ mod m считает степень по модулю. Обратный — показатель не нужен, только сравнение с 1.
- В каком диапазоне ответ?
- x от 0 до m − 1. Для a = 1 всегда x = 1 при m ≥ 2.
- Можно ли m = 1?
- Нет. Модуль должен быть ≥ 2. По модулю 1 любое целое сравнимо с 0, обратного к 1 в обычном смысле нет.