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

Обратный элемент по модулю через расширенный алгоритм Евклида

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m

Схема Обратная подстановка для 17 и 43

Приведение −5 по модулю 43 даёт 38.

Обозначения

$a$: число, для которого ищется обратный остаток, безразмерная величина
$m$: модуль больше единицы, безразмерная величина
u, v: целые коэффициенты равенства Безу, безразмерная величина
$a⁻¹$: обратный элемент по модулю m, безразмерная величина

Условия применения

Модуль m — целое число больше единицы, a — целое, НОД(a,m)=1. Коэффициенты u и v целые. При этих условиях обратный остаток существует и единственен по модулю m; его обычно приводят к диапазону от 0 до m−1.

Ограничения

При НОД(a,m)>1 обратного элемента нет, хотя отдельное сравнение ax≡b может иметь решения. Запись a⁻¹ здесь не означает вещественную дробь 1/a. Отрицательный коэффициент Безу допустим, но для стандартного ответа его надо привести по модулю.

Подробное объяснение

Обычный алгоритм Евклида находит наибольший общий делитель последовательными делениями с остатком. Расширенный вариант дополнительно выражает каждый остаток как целочисленную комбинацию исходных a и m. Если последний ненулевой остаток равен единице, получается равенство Безу.

В равенстве au+mv=1 второе слагаемое кратно модулю и при переходе к сравнению исчезает. Остаётся au≡1, поэтому u является искомым обратным. Коэффициент при модуле нужен для проверки равенства, но не входит в итоговый класс вычетов.

Если общий делитель больше единицы, любое au+mv делится на него и не может равняться единице. Это объясняет необходимость взаимной простоты без перебора всех кандидатов. Простота самого модуля не обязательна: например, у 5 есть обратный по составному модулю 12.

Коэффициент u часто отрицателен. Добавление любого кратного m сохраняет произведение по модулю, поэтому отрицательное значение можно заменить стандартным неотрицательным остатком. При программировании стоит учитывать, что операция остатка для отрицательных чисел различается между языками.

Проверка результата очень короткая: вычислить a·u и убедиться, что остаток равен единице. Она независима от цепочки обратных подстановок и обнаруживает перепутанный коэффициент, ошибку знака или случайную подстановку коэффициента при m.

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

Выполните деления с остатком для a и m и убедитесь, что последний ненулевой остаток равен единице.
Обратными подстановками выразите единицу как целую комбинацию исходного числа a и модуля m.
Возьмите коэффициент именно при a и приведите его к неотрицательному остатку меньше модуля.
Умножьте найденный остаток на a и проверьте, что разность произведения и единицы делится на m.

Историческая справка

Алгоритм последовательных делений связан с евклидовой традицией нахождения общего делителя. Расширенная вычислительная форма сохраняет не только остатки, но и коэффициенты их представления через исходные числа. В современной теории чисел XX–XXI веков это один из базовых инструментов вычислений по модулю: он связывает НОД, тождество Безу и решение линейных сравнений. Названия отражают несколько исторических линий, поэтому современный программный алгоритм не следует буквально приписывать одному античному тексту. В университетских изложениях метод часто показывают обратной подстановкой, а в программах обновляют коэффициенты на каждом шаге. Обе формы выражают одну алгебраическую идею и дают проверяемое равенство, из которого получается обратный остаток.

Историческая линия формулы

Название алгоритма отсылает к евклидовой процедуре общего делителя, а представление единицы — к тождеству Безу. Применение этих идей к модульному обратному является стандартной связью в теории чисел; современная программная реализация не приписывается одному древнему автору.

Пример

Найдём обратный к 17 по модулю 43. Евклид: 43 = 2 · 17+9, 17 = 9+8, 9 = 8+1. Обратная подстановка даёт 1 = 2 · 43 − 5 · 17. Поэтому 17⁻¹≡ − 5≡38 (mod 43). Проверка: 17 · 38 = 646 = 15 · 43+1. Ответ — класс 38 по модулю 43. Коэффициент 2 при 43 не влияет на обратный класс: 2 · 43 кратно модулю и исчезает в сравнении. НОД(17,43) = 1, поэтому решение существует и единственно среди остатков 0,…,42. Умножение 17 на 38 даёт остаток 1, а не просто близкое значение. Таким образом, найденный коэффициент проверен и равен точному классу вычетов, а не десятичной аппроксимации.

Частая ошибка

Не заменяйте модульный обратный десятичной дробью 1/a. Не ищите обратный без проверки НОД. Не берите коэффициент при модуле вместо коэффициента при a. Не отвергайте отрицательный коэффициент: добавьте кратное m. Не делите сравнение на число, необратимое по модулю, как обычное уравнение.

Практика

Задачи с решением

Обратный к пяти

Условие. Найдите обратный к 5 по модулю 12.

Решение. 12=2·5+2, 5=2·2+1. Тогда 1=5−2(12−2·5)=5·5−2·12. Проверка: 25≡1 mod 12.

Ответ. 5

Невозможный обратный

Условие. Существует ли обратный к 6 по модулю 15?

Решение. НОД(6,15)=3. Любое произведение 6u и число 15v кратны 3, поэтому 6u+15v не равно 1.

Ответ. Не существует

Дополнительные источники

https://math.libretexts.org/Courses/Mount_Royal_University/Higher_Arithmetic/4%3A_Greatest_Common_Divisor_least_common_multiple_and_Euclidean_Algorithm/4.5%3A_Linear_Congruences
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_%28Kwong%29/05%3A_Basic_Number_Theory/5.07%3A_Modular_Arithmetic

Связанные формулы

Математика

Наибольший общий делитель

$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$

Наибольший общий делитель двух чисел равен произведению общих простых множителей, взятых в меньших степенях, и показывает самую большую общую меру чисел.

Математика

Функция Эйлера: произведение по простым делителям

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

Математика

Китайская теорема об остатках для двух взаимно простых модулей

$x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$

Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.