Основы модулярной арифметики

Модулярная арифметика оперирует остатками.

Пусть $a$ — какое-то целое число. Мы хотим разделить с остатком $a$ на целое число $m$ . Разделить с остатком $a$ на $m$ — значит найти два таких целых числа $c$ и $r$ , что

a = c \cdot m + r \quad\text{и при этом}~ 0 \le r < m

Число $c$ называется неполным частным, а число $r$ называется остатком при делении $a$ на $m$ .

c = \left\lfloor \frac{a}{m} \right\rfloor \quad\text{и}\quad r = a - \left\lfloor \frac{a}{m} \right\rfloor

Для остатка $r$ такую громоздкую запись $r = a - \lfloor a/m \rfloor$ заменяют обозначением $r \defeq a \bmod m$ .

Сравнение по модулю

Возьмем множество целых чисел $\ZZ$ . Зафиксируем какой-то модуль $m$ .

Отношение «иметь один остаток при делении на $m$ » является отношением эквивалентности. Обозначается $\eqmod{m}$ . То есть, если $a$ и $b$ имеют один и тот же остаток при делении на $m$ , пишут $a \eqmod{m} b$ или $a \equiv b \pmod m$ .

Действительно, это отношение рефлексивно, так как $a \eqmod{m} a$ , симметрично, так как $a \eqmod{m} b \Leftrightarrow b \eqmod{m} a$ и транзитивно, так как $a \eqmod{m} b \land b \eqmod{m} c \Rightarrow a \eqmod{m} c$ .

Поскольку $\eqmod{m}$ — отношение эквивалентности на $\ZZ$ , то оно делит множество $\ZZ$ на классы эквивалентности $[r]$ .

[r] \defeq \{ x \cdot m + r \mid \forall\, x \in \ZZ \}

Класс эквивалентности $[r]$ содержит все числа, имеющие остаток $r$ при делении на $m$ . Эти классы эквивалентности ещё называют вычетами по модулю $m$ .

Всего таких классов $m$ : от $0$ до $m-1$ . Значит, фактормножество

\ZZ \big/ {\eqmod{m}} = \bigl\{ [0], [1], [2], \dotsc, [m-2], [m-1] \bigr\}

Сравнимость по модулю и делимость тесно связаны

a \equiv b \pmod m \iff m \divides (a - b)

Отсюда выводятся очень важные свойства. Пусть $a \equiv a' ~\text{и}~ b \equiv b' \pmod m$ . Тогда

a + b \equiv a' + b' \pmod m \quad\text{и}\quad a \cdot b \equiv a' \cdot b' \pmod m

Более того, для любого многочлена $P(x, y)$

P(a, b) \equiv P(a', b') \pmod m

Китайская теорема об остатках

Можно составлять и решать уравнения по модулю, например $x \equiv r \pmod m$ . Такие уравнения называются сравнениями (говорят, соответственно, решать сравнение, система сравнений и так далее).

Решать сравнения гораздо сложнее, чем обычные уравнения, потому что большинство операций у нас урезано. Например, решением тривиального сравнения $x \equiv r \pmod m$ служат все числа вида $r + nm$ , где $n$ — любое целое число. А вот сравнение $x^2 \equiv r \bmod p$ уже не решается стандартными методами.

Давайте пока посмотрим на системы тривиальных сравнений. О том, как выглядят все решения систем сравнений говорит китайская теорема об остатках:

Китайская теорема об остатках

Пусть $m_1, m_2, \dotsc m_n$ — попарно простые натуральные числа, то есть

m_i \rprime m_j \quad\text{для всех}~ i \neq j

Система из $n$ модулярных уравнений

\cases{x \equiv r_1 \pmod{m_1} \\ x \equiv r_2 \pmod{m_2} \\ \vdots \\ x \equiv r_n \pmod{m_n} }

имеет ровно одно решение по модулю $m_1 m_2 \dotsm m_n$

x = \sum\limits_{k=1}^n r_k \cdot M_k \cdot M_k^{-1}

где $M_k = \prod\limits_{j=1}^n m_j \Big/ m_k$ , и $M_k^{-1}$ — мультипликативно обратный к $M_k \bmod m_k$ в кольце $\ZZ_{m_k}$ .

Доказательство здесь конструктивное. Точнее, достаточно проверить, что такие $x$ действительно являются решением системы сравнений.

Подставив $x = \sum\limits_{k=1}^n r_k \cdot M_k \cdot M_k^{-1}$ в $j$ -ое сравнение системы, получим, что все члены суммы, кроме $r_j \cdot M_j \cdot M_j^{-1}$ обнулятся, так как в каждом $M_k$ будет множитель $m_j$ . А оставшийся член $r_j \cdot M_j \cdot M_j^{-1}$ по модулю $m_j$ даст $r_j$ , ведь $M_j$ и $M_j^{-1}$ мультипликативно взаимнообратны в кольце вычетов $\ZZ_{m_j}$ , и $M_j \cdot M_j^{-1} = 1 \pmod {m_j}$