Пример [1]. Найти натуральное число, которое при делении на $ 3_{} $ дает в остатке $ 2_{} $, при делении на $ 7_{} $ дает в остатке $ 3_{} $, а при делении на $ 10_{} $ — в остатке $ 9_{} $.

Решение. Пусть $ u,v,w $ — частные от деления неизвестного числа на $ 3, 7 $ и $ 10_{} $ соответственно. Имеем: $$ 3\,u+2=7\,v+3,\ 3\,u+2=10\, w+9,\ 7\,v+3=10\, w+9 \ . $$ Решаем последнее уравнение в целых числах, применяя рассуждения, приведенные ☞ ЗДЕСЬ: $$ w=7\,t_1-2,\ v=10\,t_1-2 \quad npu \quad \forall t_1 \in \mathbb Z \ . $$ Подставим найденное выражение для $ v_{} $ в первое уравнение $ 3\,u+2=7\,v+3 $: $$ 3\,u-70\, t_1=-13 \ , $$ которое также можно решить: $ u=19+70\, t_2 $ при $ \forall t_2 \in \mathbb Z $. Следовательно, общий вид искомых чисел: $$ 3\,u+2=3 (19+70\, t_2)+2=59+210\, t_2 \quad npu \quad \forall t_2 \in \mathbb Z \ . $$ Наименьшее положительное число получается при $ t_2=0 $.

Ответ. $ 59 $.

Теорема [Китайская теорема об остатках (КТО)]. Пусть числа $ M_1 , M_2, \dots, M_k $ — попарно взаимно простые, и $$ M= M_1 M_2 \times \dots \times M_k \ .$$ Тогда система

$$ x \equiv B_1 \pmod{M_1},\ x \equiv B_2 \pmod{M_2}, \dots,\ x \equiv B_k \pmod{M_k} $$ имеет единственное решение среди чисел $ \{0,1,\dots,M-1 \} $, и это решение может быть представлено в одном из следующих видов:
1. либо $ x = x_1 \pmod{M} $ при $$ x_1= \frac{M}{M_1} B_1 y_1 +\frac{M}{M_2} B_2 y_2+ \dots + \frac{M}{M_k} B_k y_k $$ и $ y_j $ обозначающем число, обратное числу $ M\big/ M_j $ относительно умножения по модулю $ M_j $: $$\frac{M}{M_j} y_j \equiv 1 \pmod{M_j} \ ;$$ 2. либо $ x = x_2 \pmod{M} $ при $$ x_2= B_1 +z_1M_1+z_2M_1M_2 +\dots + z_{k-1}M_1M_2\times \dots \times M_{k-1} \ , $$ и числах $ z_1,\dots,z_{k-1} $ последовательно определяемых из сравнений $$ \begin{array}{lcl} B_1+z_1M_1 &\equiv B_2 \pmod{M_2} \, , & \\ B_1 +z_1M_1+z_2M_1M_2 &\equiv B_3 \pmod{M_3} \, ,& \\ \dots & \dots & \\ B_1 +z_1M_1+z_2M_1M_2 +\dots + z_{k-1}M_1M_2\times \dots \times M_{k-1} & \equiv B_k \pmod{M_k} \, . & \end{array} $$

Доказательство. 1. При любых целых числах $ y_2,\dots,y_k $ число $ x_{1} $, определяемое формулой 1 , удовлетворяет сравнению $$x_1\equiv \frac{M}{M_1} B_1 y_1 \pmod{M_1}$$ (поскольку числа $ M/M_2,\dots,M/M_k $ делятся на $ M_{1} $). Пусть число $ y_1\in \{ 1, \dots ,M_1-1 \} $ удовлетворяет сравнению $$\frac{M}{M_1} y_1 \equiv 1 \pmod{M_1}$$ (на основании теоремы существования и предположений доказываемой теоремы такое число существует и оно единственно). Тогда $ x_1\equiv B_1 \pmod{M_1} $, т.е. удовлетворяет первому из сравнений системы. Аналогично показывается справедливость остальных сравнений.

2. Фактически, этот алгоритм заключается в последовательном решении сравнений системы. Решение первого имеет вид $ B_1+M_1t_1 $ при $ t_1\in \mathbb Z $; оно подставляется во второе, из которого находим представление для $ t_1 $ в виде $ t_1=z_1+M_2t_2 $ при $ t_2\in \mathbb Z $, и т.д. Формально: число $ x_2 $, определяемое формулой 2 , очевидно удовлетворяет первому из сравнений системы: $ x_2 \equiv B_1 \pmod{M_1} $. Далее, $ x_2\equiv B_1+ z_1M_1 \pmod{M_2} $ и сравнение $ x_2 \equiv B_2 \pmod{M_2} $ будет выполнено, если $ z_1 $ удовлетворяет сравнению $ B_1+ z_1M_1 \equiv B_2 \pmod{M_2} $. Поскольку $ \operatorname{HOD} (M_1,M_2)=1 $, то на основании теоремы существования, такое число существует и оно единственно при условии $ z_1\in \{ 1, \dots ,M_2-1 \} $. Установив его, продолжаем далее по индукции.

В заключение покажем, что любые два решения $ \tilde{x} $ и $ \tilde{\tilde{x}} $ системы сравнимы между собой по модулю $ M_{} $. В самом деле: $$ \tilde{x} \equiv B_j \pmod{M_j},\ \tilde{\tilde{x}} \equiv B_j \pmod{M_j} \ \Rightarrow \ \tilde{x} - \tilde{\tilde{x}} \equiv 0 \pmod{M_j} $$ для $ \forall j \in \{1,\dots, k \} $. Поскольку числа $ M_1,\dots,M_{k} $ попарно взаимно просты, то на основании теоремы 4, приведенной ☞ ЗДЕСЬ, имеем: $ \tilde{x} - \tilde{\tilde{x}} \equiv 0 \pmod{M_1\times \dots \times M_k} $. ♦

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

Пример 1. Решить систему сравнений

$$x \equiv 7 \pmod{8},\ x \equiv -1 \pmod{11},\ x \equiv 3 \pmod{15} \ .$$

Решение. Проиллюстрируем оба способа из теоремы. Для представления 1 сначала решаем сравнения $$165 \cdot y_1 \equiv 1 \pmod{8} ,\quad 120 \cdot y_2 \equiv 1 \pmod{11} ,\quad 88 \cdot y_3 \equiv 1 \pmod{15} \ , $$ которые, очевидно, эквивалентны следующим: $$ 5 \cdot y_1 \equiv 1 \pmod{8} ,\quad 10 \cdot y_2 \equiv 1 \pmod{11} ,\quad 13 \cdot y_3 \equiv 1 \pmod{15} \ . $$ Алгоритм решения линейного сравнения даст решения в виде $$y_1=5, \quad y_2=10 , \quad y_3=7 \ . $$ По формуле 1 получаем $$x_1= \underbrace{7\cdot 5 \cdot 165 + (-1)\cdot 10 \cdot 120 + 3 \cdot 7 \cdot 88}_{6423} = 1143+1320\times 4 \equiv 1143 \pmod{1320} \ .$$

Для 2 решением сравнения $ 7+ 8\, z_1 \equiv -1 \pmod{11} $ очевидно является $ z_1 \equiv_{_{11}} -1 \equiv_{_{11}} 10 $. Сравнение $ 7+8 \cdot 10 + 8\cdot 11 \, z_2 \equiv 3 \pmod{15} $ эквивалентно $ 13\, z_2 \equiv 6 \pmod{15} $ и имеет решение $ z_2=12 $. Окончательно $$x_2= 87 + 8\cdot 11 \cdot 12 =1143 \ .$$

Ответ. $ x \equiv 1143 \pmod{1320} $.

При вычислениях по формуле 1 один из коэффициентов $ y_jM/{M_j} $ можно легко установить, если все остальные уже вычислены:

Доказать, что при условиях (и в обозначениях) теоремы имеет место сравнение

$$ \frac{M}{M_1} y_1 +\frac{M}{M_2} y_2+ \dots + \frac{M}{M_k} y_k \equiv 1 \pmod{M} \ . $$

Какой из алгоритмов теоремы — 1 или 2 — предпочтителен при расчетах ?

Для фиксированной системе сравнений эти алгоритмы равноэффективны. Однако если идет речь о решении серии однотипных систем с изменением входящих в них параметров, то проявляются преимущества каждого из алгоритмов. Рассмотрим сначала серию систем сравнений $$ x \equiv B_1 \pmod{M_1},\ x \equiv B_2 \pmod{M_2}, \dots,\ x \equiv B_k \pmod{M_k} $$ при фиксированном их числе $ k_{} $ и фиксированных же модулях $ M_1,\dots,M_{k} $, но варьируемых $ B_1,\dots,B_{k} $. В этом случае имеет смысл использовать представление решения в форме 1 , поскольку для получения решения каждой новой системы серии нужно будет произвести лишь пересчет суммы при уже вычисленных ранее величинах $ y_1,\dots,y_k $. С другой стороны, если решается серия систем сравнений, в которой каждая следующая система получается из предыдущей добавлением одного нового сравнения — т.е., например, система дополняется сравнением $ x\equiv B_{k+1} \pmod{M_{k+1}} $ — то более удобным для вычисления решения становится вариант 2 , так как при его использовании приходится дополнительно решать лишь одно новое сравнение относительно $ z_{k} $ и добавить соответствующее слагаемое в сумму — т.е. просто прибавить его к решению стартовой системы.

Пример 2. Решить системы сравнений

а) $ x \equiv 3 \pmod{8},\ x \equiv 1 \pmod{11},\ x \equiv 12 \pmod{15} $;

б) $ x \equiv 7 \pmod{8},\ x \equiv -1 \pmod{11},\ x \equiv 3 \pmod{15},\ x \equiv 4 \pmod{7} $.

Решение. Обе системы могут рассматриваться как вариации одной и той же системы примера 1, и решение каждой из этих систем может быть получено модифицированием соответствующего варианта решения того примера. Так, для системы а) получить решение не представляет труда, если были заранее вычислены величины $ y_1,y_2 $ и $ y_3 $: $$x_1= \underbrace{3\cdot 5 \cdot 165 + 1\cdot 10 \cdot 120 + 12 \cdot 7 \cdot 88}_{11\,067} \equiv 507 \pmod{1320} \ .$$ А для системы б) удобнее использовать алгоритм 2 теоремы, тем более, что решение системы из первых трех сравнений у нас уже имеется. $$ 1320\, z_4 \equiv 4 \pmod{7} \quad \Rightarrow \quad z_4 =4 \quad \Rightarrow \quad x_2 =1143+1320\, z_4 =6423 \ . $$

Ответ. а) $ x \equiv 507 \pmod{1320} $; б) $ x \equiv 6423 \pmod{9240} $.

Определить число $ x_{} $ солдат китайской армии, если

а) $ x \equiv 3 \pmod{7},\ x \equiv 1 \pmod{11}, \ x \equiv 12 \pmod{13},\ x \equiv 10 \pmod{17} $;

б) $ x \equiv 3 \pmod{7},\ x \equiv 1 \pmod{11}, \ x \equiv 12 \pmod{13},\ x \equiv 11 \pmod{17} $.

Доказать, что если $ p_1,p_2,p_3 $ — различные простые числа, то а) решение системы

$$ x \equiv B_1 \pmod{p_1},\ x \equiv B_2 \pmod{p_2}, \ $$ можно представить в виде $$ x \equiv p_2^{p_1-1}B_1 + p_1^{p_2-1}B_2 \pmod{p_1p_2} \ , $$ а б) решение системы $$ x \equiv B_1 \pmod{p_1},\ x \equiv B_2 \pmod{p_2}, \ x \equiv B_3 \pmod{p_3} $$ — в виде $$ x \equiv p_2^{p_1-1}p_3^{p_1-1} B_1 + p_1^{p_2-1} p_3^{p_2-1} B_2 + p_1^{p_3-1}p_2^{p_3-1} B_3 \pmod{p_1p_2p_3} \ . $$ Решить эти системы при $ B_1=1,B_2=2,B_3=3 $ и $ p_1=7,p_2=11,p_3=17 $.

Cистема сравнений может иметь решения и при нарушении условий КТО.

[Фибоначчи]. Крестьянка несла на базар корзину яиц. Неосторожный всадник, обгоняя женщину, задел корзину, и все яйца разбились. Желая возместить ущерб, всадник спросил у крестьянки, сколько яиц было в корзине. Женщина ответила, что числа яиц не знает, но когда она раскладывала их по два, по три, по четыре, по пять и по шесть, то каждый раз одно яйцо оставалось лишним, а когда она разложила по семь, лишних яиц не осталось. Сколько яиц несла крестьянка на базар?

Теорема. Система

$$ x \equiv B_1 \pmod{M_1},\ x \equiv B_2 \pmod{M_2}, \dots,\ x \equiv B_k \pmod{M_k} $$ разрешима тогда и только тогда, когда числа $$ B_j-B_{\ell} \qquad \mbox{ делятся на } \qquad \operatorname{HOD}(M_j,M_{\ell}) \quad \mbox{ при } \quad \{j,{\ell}\} \subset \{1,\dots,k\} \quad . $$ Если это условие выполнено, то решение единственно по модулю $ \operatorname{HOK}(M_1,M_2,\dots,M_k) $.

По поводу КТО см. оригинальный результат ☞ ЗДЕСЬ.

Решить систему сравнений

$$ x \equiv M_1-1 \pmod{M_1},\ x \equiv M_2-1 \pmod{M_2}, \dots,\ x \equiv M_k-1 \pmod{M_k} \ . $$

Читатель, знакомый с проблемой интерполяции, безусловно заметит аналогию вариантов 1 и 2 китайской теоремы об остатках с формами соответственно Лагранжа и Ньютона представления интерполяционного полинома $ y_{}=f(x) $, составляемого по таблице значений $$ \begin{array}{c|ccc} x & M_1 & \dots & M_k \\ \hline f(x) & B_1 & \dots & B_k \end{array} $$ Действительно, задачу интерполяции можно «перевести на язык остатков»: найти полином $ f(x)_{} $, дающий при делении на $ x-M_1 $ в остатке число $ B_{1} $, при делении на $ x-M_2 $ в остатке $ B_{2} $ и т.д.

Пример. Верно ли равенство $$ \left| \begin{array}{rrrr} 51239 & 79922 & 55538 & 29177 \\ 46152 & 16596 & 37189 & 82561 \\ 71489 & 23165 & 26563 & 61372 \\ 44350 & 42391 & 91185 & 64809 \end{array} \right|=0 \ ? $$

Решение. Фактическое вычисление подобного определителя — каким бы методом мы не воспользовались — задача довольно трудоемкая. Однако вопрос ставится не о фактическом значении, а о равенстве его нулю. Это обстоятельство может упростить вычисления. Обозначим неизвестное значение определителя через $ x_{} $; очевидно это число целое. Если $ x=0_{} $, то и его остаток при делении на любое число $ M\in \mathbb Z $ тоже должен быть равным нулю. Если же хоть для одного $ M\in \mathbb Z $ выполнится условие $ x\not\equiv 0 \pmod M $, то и $ x\ne 0 $. Вычисление определителя фактически сводится к умножению элементов определителя. Если же мы ставим задачу определения остатка от деления этого выражения на $ M_{} $, то имеет смысл сразу же «сократить» каждый элемент определителя до его остатка от деления на $ M_{} $.

Возьмем сначала $ M=10 $, т.е. от каждого элемента определителя оставляем только последнюю цифру: $$ \left| \begin{array}{rrrr} 9 & 2 & 8 & 7 \\ 2 & 6 & 9 & 1 \\ 9 & 5 & 3 & 2 \\ 0 & 1 & 5 & 9 \end{array} \right| \equiv_{_{10}} \left| \begin{array}{rrrr} -1 & 2 & -2 & -3 \\ 2 & -4 & -1 & 1 \\ -1 & 5 & 3 & 2 \\ 0 & 1 & 5 & -1 \end{array} \right| = \left| \begin{array}{rrrr} -1 & 2 & -2 & -3 \\ 0 & 0 & -5 & -5 \\ 0 & 3 & 5 & -5 \\ 0 & 1 & 5 & -1 \end{array} \right|= $$ $$ =- \left| \begin{array}{rrr} 0 & -5 & -5 \\ 3 & 5 & -5 \\ 1 & 5 & -1 \end{array} \right| \equiv_{_{10}} 0 \ . $$ Итак, полученный ответ является необходимым, но не достаточным условием равенства определителя нулю. Сделаем еще одну проверку: возьмем $ M=7 $. $$ \left| \begin{array}{rrrr} 6 & 3 & 0 & 1 \\ 1 & 6 & 5 & 3 \\ 5 & 2 & 5 & 3 \\ 5 & 6 & 3 & 3 \end{array} \right|\equiv_{_{7}} 3 \ne 0 \ . $$

Ответ. Равенство неверно.

Понятно, что если бы определитель был равен нулю, то каждое вычисление по модулю только «увеличивало бы достоверность» этого события.

Можно ли на основе серии модулярных вычислений установить истинное значение определителя?

Попробуем это сделать для определителя из примера. Прежде всего, оценим сверху абсолютную величину определителя. Каждое слагаемое в разложении определителя по формуле из его определения представляет собой произведение четырех пятизначных чисел; очевидно, это произведение не превосходит $ 10^{24} $. Всего таких слагаемых $ 24_{} $, из них половина — с отрицательным знаком. Поэтому $ |x|<1.2\cdot 10^{25} $. Берем теперь все последовательные простые числа²⁾ $ p_j $, так чтобы их произведение превысило эту оценку: $$L = \underbrace{2\cdot 3 \cdot 5 \times \dots \times 67 \cdot 71}_{20} > 1.2\cdot 10^{25} $$ и вычисляем остатки $ B_{p_j }= x \pmod{p_j} $: $$B_2=0, B_3=0, B_5=0, B_7=3, B_{11}=7,\dots, B_{67}=64, B_{71}=39 \ .$$ Китайская теорема об остатках позволяет однозначно определить величину $ x_{} $ если она находится в пределах $ 0<x< L $: $$x=+557940821520864633874788300 \ . $$ Однако, поскольку мы не знаем знака определителя, то должны предложить еще один вариант ответа — из полученного положительного значения следует вычесть величину $ L_{} $: $$x=-8605834327092627090 \ . $$ Из двух получившихся вариантов только один — именно последний — удовлетворяет оценке $ |x|<1.2\cdot 10^{25} $. Это и есть величина нашего определителя.

Остатки от деления числа $ x_{} $ на последовательность целых чисел

$$ x \equiv 1 \pmod{7},\ x \equiv 4 \pmod{8},\ x \equiv 4 \pmod{9}, $$ $$ \ x \equiv 2 \pmod{10},\ x \equiv 2 \pmod{11},\ x \equiv 5 \pmod{13} $$ вычислены с ошибками; известно, однако, что не более двух остатков ложные. Установите число $ x_{} $.

Материал настоящего пункта является естественным продолжением соответствующего пункта из раздела МОДУЛЯРНАЯ АРИФМЕТИКА.

Пример. Вычислить $ 888888^{777777} \pmod{1488659} $.

Решение. Вычисление «в лоб» по алгоритму квадрирования-умножения кажется чудовищным; упрощение, предложенное в ☞ ПУНКТЕ, в данном конкретном случае не сработает: $ 777777 < \phi (1488659)= 1449216 $.

Заметим, однако, что при вычислении значения функции Эйлера от числа $ 1488659 $ нам пришлось разложить последнее на простые сомножители $ 97 $ $ \times 103 $ $ \times 149 $ ; и эти сомножители оказались сравнительно небольшими. Это наблюдение наводит на мысль, что можно попробовать найти неизвестное нам число по его остаткам от деления на эти три сомножителя. Иными словами, мы сводим задачу вычисления $ A^B \pmod{M} $ к трем аналогичным задачам существенно меньшего размера: $ A^B \pmod{p_j} $: $$ x \equiv A^B \pmod{M} \quad \Rightarrow \quad (x-A^B) \vdots p_1p_2p_3 \quad \Rightarrow \quad (x-A^B) \vdots p_j \quad npu \quad \forall j\in\{1,2,3\} \ . $$ Используем общее правило упрощения: $$ A^B \equiv (A \pmod{p_j})^{B \pmod{p_j-1}} \pmod{p_j} \ . $$ В нашем случае: $$ x\equiv 77^{81} \pmod{97}, \ x \equiv 101^{27} \pmod{103}, \quad x \equiv 103^{37} \pmod{149} . $$ Ну а уж эти вычисления можно проделывать «вручную»: $$ x \equiv 20 \pmod{97}, \ x \equiv 27 \pmod{103}, \quad x \equiv 148 \equiv -1 \pmod{149} . $$ Теперь восстанавливаем число по КТО: $$ x\equiv 20\cdot 37 \cdot 15347+27\cdot 25 \cdot 14453-1\cdot 56 \cdot 9991 = 20553059 \ . $$

Ответ. $ 1200492_{} $.

Использование этой схемы в криптографии см. ☞ ЗДЕСЬ.

Приведенные в предыдущих пунктах примеры позволяют сформулировать основной принцип практического использования КТО: элементарные операции с большими числами подменяются аналогичными операциями над их остатками при делении на небольшие числа $ M_j $. Можно образно сказать, что мы действуем с «проекциями» чисел на множества остатков $ \{0,1,\dots,M_j-1\} $.

Вычислить $ 456789^{-1} \pmod{1488659} $ .

☞ ЗДЕСЬ

[1]. Малининъ А., Буренинъ К. Руководство алгебры и собранiе алгебраическихъ задачъ для гимназiй, реальныхъ училищъ и учительскихъ институтовъ. Изданiе седьмое. М. Издание книжнаго магазина наследников бр. Салаевыхъ. 1884.

[2]. Бухштаб А.А. Теория чисел. М. Просвещение. 1966

[3]. LeVeque W.J. Topics in Number Theory. V.1. Addison-Wesley. Mass. 1956.

[4]. Утешев А.Ю., Калинина Е.А. Лекции по высшей алгебре. Часть I. Учеб. пособие. СПб. «СОЛО». 2007. 246 c.