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

Линейное сравнение: решения через НОД коэффициента и модуля

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

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

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

Формула

ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1

Схема Два класса после сокращения модуля

14x ≡ 8 mod 30 → x ≡ 7 mod 15

Обозначения

$a,b$: целые коэффициент и правая часть сравнения, безразмерные целые
$m$: положительный целый модуль, безразмерное целое
$d$: наибольший общий делитель a и m, положительное целое
$x_0$: одно решение после сокращения по модулю m/d, целый класс
$k$: номер восстановления класса по исходному модулю, целое от 0 до d−1

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

Даны целые a,b и модуль m > 1. Сначала проверяют d = gcd(a,m) и делимость b на d. При m/d > 1 сокращённый коэффициент a/d обратим по m/d; при m/d = 1 и выполненном условии подходят все классы исходного модуля. Делить нужно одновременно коэффициент, правую часть и модуль.

Ограничения

Сокращение только коэффициента и правой части с сохранением прежнего модуля меняет задачу. Один класс по m/d разворачивается в d классов по m. При d ∤ b решений нет, даже если приблизительное вещественное деление выглядит возможным. Отрицательные представители приводят к выбранному диапазону остатков.

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

Сравнение означает, что ax−b кратно m, то есть ax+my = b для некоторого целого y с подходящим знаком. Любая линейная комбинация a и m делится на их НОД d, поэтому делимость b на d необходима. Обратно, тождество Безу показывает, что при такой делимости целочисленное решение существует.

Если d делит b, делим всё равенство на d. Получается (a/d)x ≡ b/d по модулю m/d. У сокращённых коэффициента и модуля НОД равен единице, поэтому можно найти обратный элемент и получить один класс x₀ по меньшему модулю.

Но исходная задача задана по m, а не по m/d. Все числа x₀+k·m/d удовлетворяют сокращённому сравнению и исходному равенству. При k от 0 до d−1 они дают разные классы по m; следующий шаг повторяет первый. Это объясняет точное количество решений.

Если d = 1, формула возвращается к привычному единственному классу через обратный элемент. Если a кратно m, сокращённый модуль равен единице: при b, кратном m, подходит любой x, иначе не подходит ни один. Этот крайний случай лучше обработать явно, не вызывая программу поиска обратного по модулю один.

Проверять результат нужно в исходном сравнении. После сокращения легко потерять часть классов или неверно оставить старый модуль. Подстановка каждого восстановленного остатка показывает, что ax−b делится на первоначальное m, и независимо подтверждает список решений.

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

Найдите d = gcd(a,m) и проверьте делимость b на d; если остаток ненулевой, сразу запишите отсутствие решений.
При делимости сократите одновременно a, b и m на d; отдельно обработайте вырожденный сокращённый модуль один.
Найдите обратный коэффициент в сокращённом сравнении и получите один класс x₀ по модулю m/d.
Восстановите d классов по исходному m с шагом m/d и подставьте каждый ответ в первоначальное сравнение.

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

Линейные сравнения связывают арифметику остатков с целочисленными уравнениями и алгоритмом Евклида. В современном учебном изложении, например у Порица в разделе Linear Congruences, решаемость выводится из НОД, а обратимый коэффициент появляется только после корректного сокращения. Это продолжает традицию систематического изучения сравнений в теории чисел XIX века: операции над классами требуют условий, отличных от обычного вещественного деления. Тождество Безу даёт конструктивный мост между критерием существования и поиском решения. При этом древний алгоритм Евклида, современная модульная запись и программное перечисление классов относятся к разным этапам развития языка и вычислений; их не следует объединять в одно утверждение о персональном авторстве.

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

Критерий формулируется через НОД и тождество Безу, а вычисляется расширенным алгоритмом Евклида. Это стандартный результат элементарной теории чисел. Имена в этих связях обозначают математические инструменты, а не единственного автора всей процедуры решения и перечисления классов.

Пример

Решим 14x ≡ 8 mod 30. НОД(14,30) = 2, и 8 делится на 2, поэтому решений по модулю 30 будет два. Сокращаем всё сравнение: 7x ≡ 4 mod 15. Обратный к 7 остаток равен 13, поскольку 7·13 = 91 ≡ 1 mod 15. Получаем x ≡ 13·4 ≡ 7 mod 15. В исходном диапазоне от 0 до 29 это x = 7 и x = 22. Проверка: 14·7−8 = 90 = 3·30; 14·22−8 = 300 = 10·30. Оба класса подходят и различаются на m/d = 15. Ответ x ≡ 7 mod 15 допустим как описание всех целых решений, но при перечислении классов по модулю 30 нужно явно назвать оба остатка.

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

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

Практика

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

Три класса

Условие. Решите 6x ≡ 9 mod 15.

Решение. d = 3 делит 9. После сокращения 2x ≡ 3 mod 5, обратный к 2 равен 3, поэтому x ≡ 9 ≡ 4 mod 5. По модулю 15 получаем 4,9,14.

Ответ. x ≡ 4, 9, 14 mod 15.

Решения отсутствуют

Условие. Решите 6x ≡ 7 mod 15.

Решение. НОД(6,15) = 3, но 3 не делит 7. Любое 6x−15q кратно 3, поэтому равенство с правой частью 7 невозможно.

Ответ. Решений нет.

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

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/02%3A_Congruences/2.02%3A_Linear_Congruences
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_the_Theory_of_Numbers_%28Moser%29/01%3A_Chapters/1.05%3A_Congruences

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

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Математика

Теорема Эйлера: сокращение степени по составному модулю

$a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

Математика

Мультипликативный порядок: минимальный период степеней

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.