Как решить сравнение по модулю: 42x = 30 (mod 78)

Дано: сравнение $42x \equiv 30 \pmod{78}$. Найти: все его решения, то есть все классы вычетов по модулю 78, при которых сравнение обращается в верное.

Линейное сравнение решается по жёсткой схеме из четырёх ходов: считаем $d = \gcd(a, m)$, проверяем делимость правой части на $d$, сокращаем сравнение вместе с модулем и находим единственный корень по уменьшенному модулю, а затем разворачиваем его обратно в $d$ классов по исходному модулю. Здесь $d = \gcd(42, 78) = 6$, число 30 на 6 делится, значит решения есть, и их ровно шесть: $x \equiv 10,\ 23,\ 36,\ 49,\ 62,\ 75 \pmod{78}$. Калькулятор сверху прогоняет ту же цепочку для любых $a$, $b$, $m$ и рисует остатки $ax \bmod m$ по всем вычетам, ниже разбор по шагам.

Решение по шагам

Дано. $a = 42$, $b = 30$, $m = 78$.

Найти. Все целые $x$, для которых $42x \equiv 30 \pmod{78}$.

Шаг 1. Считаем НОД коэффициента и модуля. Лестница Евклида занимает три деления:

$$78 = 1 \cdot 42 + 36, \qquad 42 = 1 \cdot 36 + 6, \qquad 36 = 6 \cdot 6 + 0.$$

Последний ненулевой остаток равен 6, поэтому $d = \gcd(42, 78) = 6$. Если лестница вызывает вопросы, она подробно разобрана в задаче как найти НОД двух чисел.

Шаг 2. Проверяем разрешимость. Сравнение $ax \equiv b \pmod m$ имеет решения тогда и только тогда, когда правая часть делится на $d$. Проверяем: $30 = 6 \cdot 5$, остатка нет. Критерий выполнен, решения существуют, и их будет ровно $d = 6$ штук.

Шаг 3. Сокращаем сравнение на $d$. Делим на шестёрку всё сразу: обе части и модуль. Модуль тоже делится, и это главное отличие сравнения от обычного уравнения.

$$42x \equiv 30 \pmod{78} \quad\Longleftrightarrow\quad 7x \equiv 5 \pmod{13}.$$

Теперь $\gcd(7, 13) = 1$, поэтому у сокращённого сравнения корень по модулю 13 ровно один.

Шаг 4. Находим обратный элемент к 7 по модулю 13. Расширенный алгоритм Евклида даёт разложение единицы через 7 и 13:

$$13 = 1 \cdot 7 + 6, \quad 7 = 1 \cdot 6 + 1 \quad\Longrightarrow\quad 1 = 7 - 6 = 7 - (13 - 7) = 2 \cdot 7 - 13.$$

Отсюда $2 \cdot 7 \equiv 1 \pmod{13}$, то есть двойка и есть обратный к семёрке по модулю 13.

Шаг 5. Умножаем обе части на обратный элемент.

$$x \equiv 2 \cdot 5 \equiv 10 \pmod{13}.$$

Шаг 6. Разворачиваем ответ к исходному модулю. Один класс по модулю 13 распадается на шесть классов по модулю 78: к найденному корню последовательно прибавляем шаг $m / d = 78 / 6 = 13$, пока не выйдем за модуль.

$$x = 10 + 13k, \qquad k = 0, 1, 2, 3, 4, 5.$$

Шаг 7. Проверяем подстановкой. Каждый корень обязан давать остаток 30 при делении на 78.

Ответ. $x \equiv 10,\ 23,\ 36,\ 49,\ 62,\ 75 \pmod{78}$, то есть шесть классов вычетов с шагом 13.

Формула и откуда она берётся

Запись $ax \equiv b \pmod m$ по определению означает, что разность $ax - b$ делится на $m$. Значит найдётся такое целое $y$, что $ax - b = my$, а это обычное линейное уравнение в целых числах:

$$ax - my = b.$$

Диофантово уравнение с двумя неизвестными разрешимо ровно тогда, когда его правая часть кратна НОД коэффициентов, и решение уравнения в целых числах устроено по тому же критерию. В одну сторону он очевиден: и $ax$, и $my$ делятся на $d = \gcd(a, m)$, поэтому вся левая часть кратна $d$, и никакое $b$, не кратное $d$, получиться не может. В другую сторону работает соотношение Безу: найдутся целые $u$ и $v$ с $au + mv = d$, и если $b = dt$, то умножение этого равенства на $t$ даёт готовое решение.

Число решений тоже выводится, а не запоминается. После сокращения на $d$ получается сравнение $a'x \equiv b' \pmod{m'}$, где $a' = a/d$, $b' = b/d$, $m' = m/d$ и $\gcd(a', m') = 1$. Взаимная простота гарантирует существование обратного элемента, поэтому корень по модулю $m'$ единственный. Остаётся понять, во что он превращается по модулю $m$: один класс вычетов по меньшему модулю $m'$ содержит ровно $m / m' = d$ классов по большему модулю $m$. Отсюда и ответ: решений либо нет вовсе, либо ровно $d$ штук.

Заодно видно, зачем при сокращении делить и модуль. Сравнение $42x \equiv 30 \pmod{78}$ и сравнение $7x \equiv 5 \pmod{78}$ неравносильны: у второго $\gcd(7, 78) = 1$, значит корень был бы один, а у исходного их шесть. Делить обе части, оставив модуль нетронутым, можно только на число, взаимно простое с модулем.

Когда решений нет: посмотрите на второй график

Возьмём сравнение $6x \equiv 4 \pmod 9$. Здесь $d = \gcd(6, 9) = 3$, а правая часть 4 на 3 не делится, поэтому решений нет ни одного. Перебирать девять вычетов не нужно, но полезно один раз посмотреть, почему перебор ничего не даст: произведение $6x$ по модулю 9 пробегает только значения 0, 6, 3, и все они кратны тройке.

Именно это показывает второй режим калькулятора сверху. Столбики стоят не над всеми правыми частями, а только над кратными $d$, и высота у каждого одинаковая и равна $d$. Для нашей основной задачи с модулем 78 столбики стоят над числами 0, 6, 12, 18 и так далее с шагом 6, каждый высотой 6, а число 30 в эту решётку попадает, потому и решений шесть. Если сдвинуть ползунок правой части на 31, столбик исчезнет, и калькулятор честно сообщит, что корней нет.

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

Система сравнений и китайская теорема об остатках

Когда неизвестное связано сразу несколькими условиями, работает та же техника, только применённая последовательно. Классическая постановка выглядит так: найти $x$, дающее остаток 2 при делении на 5 и остаток 3 при делении на 7.

$$\begin{cases} x \equiv 2 \pmod 5, \\ x \equiv 3 \pmod 7. \end{cases}$$

Из первого сравнения выражаем $x = 2 + 5t$ и подставляем во второе: $2 + 5t \equiv 3 \pmod 7$, откуда $5t \equiv 1 \pmod 7$. Это уже знакомое линейное сравнение, его корень $t \equiv 3 \pmod 7$, потому что $5 \cdot 3 = 15 = 2 \cdot 7 + 1$. Подставляем обратно: $x = 2 + 5 \cdot 3 = 17$, а общий ответ $x \equiv 17 \pmod{35}$.

Китайская теорема об остатках утверждает, что так будет всегда, если модули попарно взаимно просты: решение существует, единственно по модулю произведения модулей и находится именно такой последовательной подстановкой. Для нашего примера произведение равно $5 \cdot 7 = 35$, и 17 действительно единственный подходящий вычет среди тридцати пяти. Если же модули имеют общий делитель, система разрешима не всегда: остатки должны согласовываться по этому общему делителю.

Частые ошибки

• Сокращают сравнение, не трогая модуль. Переход от $42x \equiv 30 \pmod{78}$ к $7x \equiv 5 \pmod{78}$ меняет задачу: вместо шести корней остаётся один. Модуль делится на $d$ вместе с обеими частями.
• Делят обе части на число, не взаимно простое с модулем. Сокращать на $c$ без деления модуля разрешено только при $\gcd(c, m) = 1$, иначе часть решений теряется.
• Считают, что решение всегда одно. Единственность бывает лишь при $\gcd(a, m) = 1$. При $d > 1$ корней ровно $d$, и ответ из одного числа засчитан не будет.
• Ищут обратный элемент при $\gcd(a, m) > 1$. Обратного к 42 по модулю 78 не существует вовсе, поэтому сначала сокращение, потом поиск обратного, а не наоборот.
• Пропускают проверку делимости и «решают» неразрешимое сравнение. Если $b$ не кратно $d$, любые дальнейшие выкладки дадут число, которое не пройдёт подстановку.
• Выдают за ответ одно число вместо класса вычетов. Решением сравнения является весь класс: не $x = 10$, а $x \equiv 10 \pmod{13}$, что по модулю 78 разворачивается в шесть вычетов.

FAQ

Чем сравнение отличается от обычного уравнения? Неизвестное в сравнении ищется не среди всех чисел, а среди классов вычетов, поэтому решений всегда либо ноль, либо конечное число классов, каждый из которых содержит бесконечно много целых чисел. И арифметика другая: делить на произвольное число нельзя, а деление на взаимно простое с модулем заменяется умножением на обратный элемент.

Можно ли просто перебрать все вычеты? Для маленького модуля да: подставить $x = 0, 1, \dots, m-1$ и отобрать подходящие. При $m = 78$ это 78 подстановок против четырёх шагов алгоритма, а при модуле в сотни знаков, как в криптографии, перебор невозможен физически. Проверка же найденного ответа подстановкой обязательна в любом случае.

Что делать, если правая часть отрицательна или больше модуля? Заменить её остатком от деления на модуль, ответ от этого не изменится. Сравнение $42x \equiv 108 \pmod{78}$ равносильно исходному, потому что $108 - 30 = 78$; точно так же $-48$ заменяется на 30. Приводить к промежутку от 0 до $m-1$ удобно сразу, до всех вычислений.

Как связаны сравнения и остатки от деления? Запись $x \equiv r \pmod m$ при $0 \le r < m$ означает ровно то, что $x$ даёт остаток $r$ при делении на $m$. Поэтому задачи вида «найти остаток от деления большой степени» сводятся к сравнениям, а считают их быстрым возведением в степень по модулю.

Коротко

1. Считаем $d = \gcd(a, m)$ алгоритмом Евклида: $\gcd(42, 78) = 6$.
2. Проверяем критерий разрешимости $d \mid b$: число 30 делится на 6, значит решения есть и их ровно 6.
3. Сокращаем на $d$ обе части и модуль: $42x \equiv 30 \pmod{78}$ переходит в $7x \equiv 5 \pmod{13}$.
4. Находим обратный к 7 по модулю 13 расширенным алгоритмом Евклида: он равен 2, откуда $x \equiv 10 \pmod{13}$.
5. Разворачиваем корень с шагом $m/d = 13$ и проверяем подстановкой: $x \equiv 10,\ 23,\ 36,\ 49,\ 62,\ 75 \pmod{78}$.