This chapter hasn’t been translated into English yet, so here is the Russian original. Your browser can translate the page; the formulas and widgets work the same. Back to the English contents →

Решатель

Решение сравнений по модулю онлайн

Линейные сравнения, системы по китайской теореме об остатках, остатки больших степеней и обратные элементы — с решением по шагам и проверкой.

Примеры: 3x ≡ 4 (mod 7) x ≡ 2 (mod 3); x ≡ 3 (mod 5); x ≡ 2 (mod 7) 3^100 mod 7 17^-1 mod 43 6x ≡ 4 (mod 10) x^2 ≡ 4 (mod 15) 123456789 mod 9

Загружаем решатель…

Что можно ввести

Сравнение первой степени: 3x ≡ 4 (mod 7), в том числе с неизвестной в обеих частях: 5x + 3 ≡ 2x − 1 (mod 11).
Систему — через точку с запятой или с новой строки: x ≡ 2 (mod 3); x ≡ 3 (mod 5).
Остаток степени или выражения: 3^100 mod 7, (2^10 + 3^5) mod 7, 123456789 mod 9.
Обратный элемент: 17^-1 mod 43 или обратный к 17 по модулю 43.
Сравнение высокой степени: x^2 ≡ 4 (mod 15) — его решатель решает перебором всех остатков (для модуля до $20\,000$).

Знак $\equiv$ можно заменить обычным «$=$», а «$(\mathrm{mod}\ 7)$» — словами «mod 7» или «по модулю 7». На телефоне символы есть на кнопках под полем.

Что такое сравнение

Запись $a \equiv b \pmod m$ читается «$a$ сравнимо с $b$ по модулю $m$» и означает, что $a$ и $b$ дают одинаковые остатки при делении на $m$, или, что то же самое, их разность делится на $m$. Так, $17 \equiv 5 \pmod 6$: оба числа дают остаток $5$, а $17 - 5 = 12$ делится на $6$. Обозначение ввёл Гаусс в «Арифметических исследованиях» (1801).

Удобно думать о циферблате с $m$ делениями: числа, сравнимые по модулю $m$, попадают на одно деление. Часы — это арифметика по модулю $12$: через $15$ часов после девяти будет $9 + 15 = 24 \equiv 0$, то есть снова полночь или полдень.

Со сравнениями можно обращаться почти как с уравнениями: прибавлять к обеим частям одно и то же, умножать обе части на одно и то же, заменять любое число его остатком. «Почти» — потому что делить обе части можно не всегда. Об этом — главная ловушка ниже.

Как решать $ax \equiv b \pmod m$

Переносим всё с неизвестной влево, числа вправо, заменяем коэффициенты остатками: получаем $ax \equiv b \pmod m$.
Находим $d = \text{НОД}(a, m)$ алгоритмом Евклида.
Если $b$ не делится на $d$ — решений нет.
Если делится — делим на $d$ всё сразу: $a$, $b$ и модуль. Теперь коэффициент взаимно прост с модулем.
Умножаем обе части на обратный к коэффициенту: он находится обратным ходом алгоритма Евклида.

НОД коэффициента и модуля. Всё, что можно получить в виде $ax - km$, делится на $d$.

Правая часть. Если $d \mid b$, решений ровно $d$ по модулю $m$: одно решение $x_0$ по модулю $m/d$ и его сдвиги $x_0 + \frac{m}{d}k$.

Пример: $6x \equiv 4 \pmod{10}$. $\text{НОД}(6, 10) = 2$, и $2 \mid 4$ — решения есть. Делим всё на $2$: $3x \equiv 2 \pmod 5$. Обратный к $3$ по модулю $5$ — это $2$ ($3 \cdot 2 = 6 \equiv 1$), значит, $x \equiv 2 \cdot 2 = 4 \pmod 5$. По модулю $10$ это два решения: $4$ и $9$. А у $6x \equiv 5 \pmod{10}$ решений нет: $6x - 10k$ всегда чётно.

Обратный элемент к $a$ по модулю $m$ — такое $a^{-1}$, что $a \cdot a^{-1} \equiv 1 \pmod m$. Он существует ровно тогда, когда $\text{НОД}(a, m) = 1$, и находится из соотношения Безу: если $ax + my = 1$, то $ax \equiv 1$ и $x$ — обратный. Умножить на обратный — всё равно что разделить на $a$; поэтому по простому модулю делить можно на всё, кроме нуля.

Системы: китайская теорема об остатках

В трактате «Сунь-цзы суань цзин» (III–V века) есть задача: число при делении на $3$ даёт остаток $2$, на $5$ — остаток $3$, на $7$ — остаток $2$; найти его. Ответ $23$, и других нет, если не считать чисел, отличающихся на кратное $105$.

Взаимно простые модули. Тогда решение есть при любых остатках $r_1$, $r_2$.

Единственное решение от $0$ до $m_1 m_2 - 1$. Решатель находит его подстановкой: из первого сравнения $x = r_1 + m_1 t$, подставляем во второе и решаем линейное сравнение относительно $t$.

Новый модуль. Если модули не взаимно просты, система разрешима не всегда, а модулем ответа будет не произведение, а НОК.

Пример: $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$. Из первого $x = 2 + 3t$. Во втором: $2 + 3t \equiv 3$, то есть $3t \equiv 1 \pmod 5$, откуда $t \equiv 2$. Значит, $x = 2 + 3 \cdot 2 = 8$, и $x \equiv 8 \pmod{15}$.

Для трёх и более сравнений так же: объединяем первые два в одно, потом добавляем третье. Картинка решателя для двух сравнений — «китайская таблица»: число $n$ стоит в строке своего остатка от деления на $m_1$ и в столбце остатка от деления на $m_2$. Когда модули взаимно просты, в каждой клетке ровно одно число — это и есть теорема.

Остатки больших степеней

Число $3^{100}$ содержит $48$ цифр, но его остаток при делении на $7$ находится в уме. Два инструмента.

Малая теорема Ферма (1640; первое опубликованное доказательство — у Эйлера, 1736): если $p$ простое и $a$ на него не делится, то $a^{p-1} \equiv 1 \pmod p$. По модулю $7$ имеем $3^6 \equiv 1$, а $100 = 6 \cdot 16 + 4$, поэтому $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 3^4 = 81 \equiv 4$. Для составного модуля вместо $p - 1$ берут функцию Эйлера $\varphi(m)$ — количество чисел от $1$ до $m$, взаимно простых с $m$.

Быстрое возведение в степень: показатель записывают в двоичной системе, $100 = 64 + 32 + 4$, считают $a, a^2, a^4, a^8, \ldots$ — каждое следующее как квадрат предыдущего, сразу беря остатки, — и перемножают нужные. Вместо $99$ умножений хватает шести возведений в квадрат и двух умножений. Этим способом компьютеры считают степени с показателями в сотни цифр — на нём работает шифр RSA.

Разобранные примеры

Пример 1. $3x \equiv 4 \pmod 7$

$\text{НОД}(3, 7) = 1$, решение одно. Обратный к $3$ по модулю $7$: $3 \cdot 5 = 15 = 2 \cdot 7 + 1$, значит, $3^{-1} \equiv 5$. Умножаем обе части на $5$: $x \equiv 4 \cdot 5 = 20 \equiv 6 \pmod 7$.

Проверка: $3 \cdot 6 = 18 = 2 \cdot 7 + 4$. Все решения — $x = 6 + 7k$: $\ldots, -1, 6, 13, 20, \ldots$

Пример 2. Задача Сунь-цзы

$x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. Первые два сравнения дают $x \equiv 8 \pmod{15}$ (см. выше). Теперь $x = 8 + 15s$ и $8 + 15s \equiv 2 \pmod 7$. Так как $15 \equiv 1$, получаем $s \equiv 2 - 8 = -6 \equiv 1 \pmod 7$. Значит, $x = 8 + 15 = 23$, и $x \equiv 23 \pmod{105}$.

Проверка: $23 = 3 \cdot 7 + 2 = 5 \cdot 4 + 3 = 7 \cdot 3 + 2$.

Пример 3. Обратный к 17 по модулю 43

Алгоритм Евклида: $43 = 2 \cdot 17 + 9$, $17 = 1 \cdot 9 + 8$, $9 = 1 \cdot 8 + 1$. Обратный ход:

$$1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17.$$

Значит, $17 \cdot (-5) \equiv 1 \pmod{43}$, и $17^{-1} \equiv -5 \equiv 38$. Проверка: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$.

Пример 4. $x^2 \equiv 4 \pmod{15}$

Формулы, как для линейных сравнений, здесь нет, поэтому перебираем остатки от $0$ до $14$: $x^2 \bmod 15$ равно $4$ при $x = 2, 7, 8, 13$. Четыре решения у квадратного сравнения — не ошибка: модуль составной, и по модулям $3$ и $5$ у сравнения по два решения ($x \equiv \pm 2$), а $2 \cdot 2 = 4$ их комбинации по китайской теореме. По простому модулю у сравнения степени $n$ решений не больше $n$.

Типичные ошибки

Делят обе части, не трогая модуль. Из $2x \equiv 2 \pmod 4$ не следует $x \equiv 1 \pmod 4$ — теряется решение $x = 3$. Если общий множитель делит и модуль, модуль тоже делят: $x \equiv 1 \pmod 2$.
Делят на число, не взаимно простое с модулем. По модулю $10$ на $6$ «разделить» нельзя: $6 \cdot 2 \equiv 6 \cdot 7 \equiv 2$, хотя $2 \not\equiv 7$. Сначала делят на НОД, потом умножают на обратный.
Сокращают показатель по модулю. $3^{100} \bmod 7$ — это не $3^{100 \bmod 7} = 3^2$. Показатель приводят по модулю $p - 1$ (или $\varphi(m)$), а не по $m$, и только если основание взаимно просто с модулем.
Оставляют отрицательный остаток. $-7 \bmod 3 = 2$, потому что $-7 = 3 \cdot (-3) + 2$. Остаток по модулю $m$ всегда берут от $0$ до $m - 1$ (калькуляторы и языки программирования здесь иногда расходятся).
Для системы берут произведение модулей, когда они не взаимно просты. У $x \equiv 1 \pmod 4$, $x \equiv 3 \pmod 6$ ответ $x \equiv 9 \pmod{12}$, а не по модулю $24$; а система $x \equiv 1 \pmod 4$, $x \equiv 2 \pmod 6$ вообще не имеет решений: первое требует нечётного $x$, второе — чётного.
Ищут обратный, которого нет. У $6$ по модулю $9$ обратного не существует: $6x$ всегда делится на $3$ и не может дать остаток $1$.

Что ещё посмотреть

Циферблаты остатков, малая теорема Ферма, функция Эйлера, китайская теорема и то, как из них собирается шифр RSA, — в главе «Арифметика остатков и шифры». Алгоритм Евклида и соотношение Безу, на которых держится поиск обратного элемента, — в главе о делимости и в решателе НОД и НОК. Признаки делимости на $3$, $9$ и $11$ — это тоже сравнения: $10 \equiv 1 \pmod 9$ и $10 \equiv -1 \pmod{11}$. Разложить модуль на простые множители поможет решатель разложения.