УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу МОДУЛЯРНАЯ АРИФМЕТИКА


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

П

Пример [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)(孫子, ок. 400 — ок. 460), о котором не известно ничего, кроме того, что он является автором этой книги; годы его жизни устанавливались историками науки на основе анализа текста.

Задача 26 главы 3. Предположим, что имеется неизвестное количество объектов. Разбив их на тройки, получаем в остатке 2, разбив на пятерки — 3, разбив на семерки — 2. Сколько имеется объектов?

После решения этой конкретной задачи, в книге приводится алгоритм решения и общей — при произвольных остатках:

«Умножь число остатков при делении на тройки на 70, добавь к полученному произведение числа остатков при делении на пятерки на 21, и затем добавь произведение числа остатков при делении на семерки на 15. Если результат равен 106 или более — вычти кратное 105.»

Эти рассуждения фактически соответствуют представлению решения системы формулой 2 .

Некоторые специалисты полагают, что алгоритм решения системы сравнений позволял китайским генералам пересчитывать армию без особых усилий последовательностью однотипных распоряжений:

«В колонну по 7_{} становись!»

По выполнении команды, подсчитывалось количество солдат, стоящих в последнем ряду. Затем производились аналогичные подсчеты по результатам выполнения команд:

«В колонну по 11 становись!»

«В колонну по 13 становись!»

«В колонну по 17 становись!»

В соответствии с утверждением теоремы, по четырем остаткам однозначно восстанавливается число солдат, если оно не превосходит 17017=7\times 11\times 13 \times 17.

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

П

Пример 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 делятся на \qquad \operatorname{HOD}(M_j,M_{\ell}) \quad при \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}. Берем теперь все последовательные простые числа2) 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}. Это и есть величина нашего определителя.

§

На самом деле, в только что решенном примере эффективность применения КТО в сравнении с методом вычисления определителя 4_{}-го порядка, основанном на формуле из его определения, не очень очевидна: первый способ из КТО содержит сумму в 20 слагаемых — по сравнению с 24 из определения определителя, но каждое из этих слагаемых более громоздко! Можно, однако, слегка уменьшить количество этих слагаемых — скажем, до 17, если воспользоваться оценкой величины определителя по неравенству Адамара: |x|<1.6\times 10^{21}.

§

Вычислительные эксперименты с определителями порядка 16 с ОЧЕНЬ БОЛЬШИМИ элементами ЗДЕСЬ.

?

Остатки от деления числа 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.

1) Это имя принадлежит и другому знаменитому историческому лицу — китайскому стратегу и военачальнику, жившему в IV веке до н.э.; автору «Трактата о военном искусстве».
2) В соответствии с условием КТО достаточно было бы взять попарно взаимно простые числа, но для объяснения идеи мне здесь не хочется заморачиваться с дополнительными проверками.

2016/08/31 10:26 редактировал au