В ☞ ПУНКТЕ обсуждается вопрос делимости нацело данного числа $ A_{} $ на некоторое другое число $ M_{} $. Используемый подход заключается не в непосредственном выполнении деления $ A_{} $ на $ M_{} $, а в построении нового числа $ A_{1} $, меньшего (желательно, много меньшего) числа $ A_{} $ и такого, что делимость $ A_{} $ на $ M_{} $ была эквивалентна делимости $ A_{1} $ на $ M_{} $. Эта идея распространяется и на случай, когда число $ A_{} $ не делится нацело на $ M_{} $:

Теорема. Остаток от деления числа $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $ на $ 11_{} $ совпадает с остатком от деления на $ 11_{} $ числа

$$ {\mathfrak a}_{s+1}-{\mathfrak a}_s +{\mathfrak a}_{s-1}+\dots+ (-1)^{s-1} {\mathfrak a}_2+ (-1)^{s} {\mathfrak a}_1 \ . $$

Задача. Определить остаток от деления произвольного целого числа $ A_{} $ на заданное натуральное число $ M_{} $, не выполняя деления непосредственно (т.е. не вычисляя частного).

Очевидно, что искомый остаток находится среди чисел $ 0,1,\dots,M-1 $ (см. определение ☞ ЗДЕСЬ ). Таким образом, множество $ \mathbb Z_{} $ всех целых чисел можно разбить на подмножества, каждое из которых содержит числа, имеющие одинаковый остаток от деления на $ M_{} $. Поставленная задача может быть переформулирована в терминах этих составляющих подмножеств: какому именно из них принадлежит данное число $ A_{} $?

Зафиксируем некоторое число $ M\in \mathbb N $, назовем его модулем. Каждому $ A\in \mathbb Z $ соответствует определенный остаток от деления его на $ M_{} $. Назовем два числа $ A_{} $ и $ B_{} $ равноостаточными по модулю $ M_{} $ или сравнимыми по модулю $ M_{} $, если при делении на $ M_{} $ они дают одинаковый остаток. Этот факт записывают: $$ A \equiv B \pmod{M} \quad \mbox{ или } \quad A \equiv_{_M} B \ , $$ и читают: «$ A_{} $ сравнимо с $ B_{} $ по модулю $ M_{} $».

Пример.

$$ 32 \equiv 21 \pmod{11} ,\ 112 \equiv -5 \pmod 9 , 176432 \not\equiv 54897 \pmod{5528} \ . $$

Теорема. $ A_{} $ сравнимо с $ B_{} $ по модулю $ M_{} $ тогда и только тогда, когда:

1. $ A_{} $ можно представить в виде $ A=B+Mt $ при $ t\in \mathbb Z $,

или

2. $ A-B_{} $ делится на $ M_{} $.

Теорема. Сравнения можно почленно складывать и почленно перемножать: если

$$A_1 \equiv B_1 \pmod{M},\ A_2 \equiv B_2 \pmod{M}, \dots, A_k \equiv B_k \pmod{M} \ , $$ то $$ \begin{array}{ccc} A_1+A_2+\dots+A_k &\equiv& B_1 +B_2+\dots+B_k \pmod{M} \ , \\ A_1A_2\times \dots \times A_k &\equiv& B_1 B_2 \times \dots \times B_k \pmod{M} \ . \end{array} $$

Доказательство. Если каждое из чисел $ A_j-B_j $ делится на $ M_{} $, то и их сумма делится на $ M_{} $.

Далее для доказательства $$ A_1A_2\times \dots \times A_k \equiv B_1 B_2 \times \dots \times B_k \pmod{M} $$ рассмотрим сначала случай $ k=2 $. $$A_1A_2-B_1B_2=A_1A_2-A_1B_2+A_1B_2-B_1B_2=A_1(A_2-B_2)+B_2(A_1-B_1) \ ,$$ и, поскольку $ A_j-B_j $ делится на $ M_{} $, то $ A_1A_2 \equiv B_1B_2 \pmod{M} $. Выдвинув в качестве индукционного предположения справедливость сравнения для $ k_{} $ cомножителей, преобразуем разность $$A_1A_2 \times \dots \times A_kA_{k+1}-B_1B_2 \times \dots \times B_kB_{k+1}= $$ $$ \begin{array}{lll} =A_1A_2 \times \dots \times A_kA_{k+1}& -B_1B_2 \times \dots \times B_kA_{k+1}+ & \\ & +B_1B_2 \times \dots \times B_kA_{k+1}- B_1B_2 \times \dots \times B_kB_{k+1}= & \end{array} $$ $$ =(A_1A_2 \times \dots \times A_k - B_1 B_2 \times \dots \times B_k)A_{k+1}+ B_1B_2 \times \dots \times B_k(A_{k+1}-B_{k+1}) \ . $$ При условии $ A_{k+1} \equiv B_{k+1} \pmod{M} $ правая часть будет делиться на $ M_{} $, следовательно, разность $ A_1A_2 \times \dots \times A_kA_{k+1} - B_1 B_2 \times \dots \times B_kB_{k+1} $ делится на $ M_{} $. ♦

Если $ A \equiv B \pmod{M} $, то

$$ \begin{array}{cccr} A+k &\equiv& B+k \pmod{M} & npu \quad \forall k \in \mathbb Z, \\ A^k &\equiv& B^k \pmod{M} & npu \quad \forall k \in \mathbb N. \end{array} $$

Если $ A \equiv B \pmod{M} $, то $ f(A) \equiv f(B) \pmod{M} $, где $ f_{}(x) $ — произвольный полином с целыми коэффициентами.

Последние результаты объясняют, почему для записи сравнений выбран знак $ {\color{Red} \equiv} $, напоминающий знак равенства $ {\color{Red} =} $ . Все привычные нам манипуляции в отношении числовых равенств — их можно складывать, перемножать, возводить в степени и т.п. — оказываются справедливыми и относительно сравнений.

Можно ли сравнение сокращать на общий множитель: $$ Ad\equiv Bd \pmod{M} \quad \Rightarrow \quad A \equiv B \pmod{M} \ ? $$ А вот так: $$ Ad\equiv Bd \pmod{Md} \quad \Rightarrow \quad A \equiv B \pmod{M} \ ? $$

В дальнейшем запись $$x= A \pmod{M} $$ будем понимать в смысле, что переменной $ x_{} $ присваивается значение остатка от деления числа $ A_{} $ на $ M_{} $; таким образом, $ x\in \{0,1,\dots,M-1 \} $.

В формализме сравнений теорему, приведенную в начале настоящего раздела, можно переформулировать так:

Теорема.

$$ \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} \equiv {\mathfrak a}_{s+1}-{\mathfrak a}_s +{\mathfrak a}_{s-1}+\dots+ (-1)^{s-1} {\mathfrak a}_2+ (-1)^{s} {\mathfrak a}_1 \pmod{11} \ . $$

Доказательство. В самом деле, на основании предыдущей теоремы: $$ \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}}= \sum_{j=1}^{s+1}{\mathfrak a}_j 10^{s+1-j} = \sum_{j=1}^{s+1}{\mathfrak a}_j (11-1)^{s+1-j} \equiv \sum_{j=1}^{s+1} (-1)^{s+1-j}{\mathfrak a}_j \pmod{11} \ . $$ ♦

На той же идее основан и известный с древности критерий проверки правильности выполненных алгебраических операций, называемый «отбрасывание девяток». Пусть над двумя целыми числами в десятичном представлении произведена некоторая элементарная алгебраическая операция $ \ast $ (т.е. $ \ast \in \{+,-,\times, \div \} $), результатом которой стало некоторое новое целое число: $$ \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} \ast \underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_t {\mathfrak b}_{t+1}}= \underline{{\mathfrak c}_1{\mathfrak c}_2 \dots {\mathfrak c}_u {\mathfrak c}_{u+1}} $$ (в случае, когда $ \ast=\div $, предполагается, что деление произвелось нацело). Требуется проверить правильность выполнения этой операции.

Теорема. Если результат операции $ \ast $ верен, то справедливо сравнение

$$({\mathfrak a}_1+ \dots +{\mathfrak a}_s +{\mathfrak a}_{s+1}) \ast ({\mathfrak b}_1+ \dots +{\mathfrak b}_t +{\mathfrak b}_{t+1}) \equiv ({\mathfrak c}_1 +\dots +{\mathfrak c}_u +{\mathfrak c}_{u+1}) \pmod{9} \ . $$

Пример. Проверить результаты следующих арифметических операций:

а) $ 12347\times 54323 =670726081 $; б) $ 123811566370524395\ \colon \ 689603=179543353465 $.

Решение. а) $ 1+2+3+4+7=17,\ 1+7=8 \ \Rightarrow \ 12347 \equiv 8 \pmod 9 $. Аналогично устанавливается, что $$ 54323\equiv 8 \pmod{9} \ , \ 670726081 \equiv 1 \pmod{9} \ .$$ Поскольку $ 8\times 8 \equiv 1 \pmod{9} $, то тест «отбрасывания девяток» не обнаруживает ошибку в операции.

б). $$ 123811566370524395 \equiv 8 \pmod{9},\ 689603 \equiv 5 \pmod{9} , $$ $$ 179543353465 \equiv 1 \pmod{9} \, .$$ Однако $ 8 \not \equiv 5 \times 1 \pmod{9} $, т.е. результат операции неверен. ♦

Еще одна историческая задача — о вечном календаре — имеет отношение к модулю $ M=7 $:

Задача. Определить день недели по дате.

Задача может быть решена буквально «на пальцах», если мы обладаем календарем хотя бы за какой-то год.

Пример. Установить день недели для 9 мая 1945 г.

Решение. Предположим, что у нас имеется календарь за 2011 г. и, согласно ему, 9 мая 2011 г. падает на понедельник. Теперь посчитаем полное число дней, отделяющих эту дату от нас интересующей. Между ними — ровно $ 66_{} $ лет, включая $ 16 $ високосных ( $ 1948, 1952,\dots, 2008 $). Полное число дней, разделяющих эти даты — $$ 66 \times 365 + 16 \ . $$ Что нам делать с этим числом — вычислять его? — В этом нет необходимости: его надо «намотать на неделю». Начать отсчет с понедельника и отсчитать от него «в обратном направлении» (т.е. в прошлое) упомянутое количество дней. Если перевести на язык чисел, то можно формализовать задачу так: $ 1_{}= $ понедельник, $ 2_{}= $ вторник,…, $ 0_{} = $ воскресенье; и нас интересует число $$ 1- (66 \times 365 + 16) \pmod{7} \ . $$ Для его вычисления можно делать любые упрощения, используя приведенные выше результаты: $$ 66 \equiv 3 \pmod{7},\quad 365 \equiv 1 \pmod{7},\quad 16 \equiv 2 \pmod{7} \quad \Rightarrow $$ $$ 1- (66 \times 365 + 16) \equiv_{_7} 1 - (3\times 1 +2 ) = - 4 \equiv_{_7} 3 \ . $$

Ответ. Среда.

Теорема [2]. День недели по дате устанавливается следующей формулой Целлера¹⁾

Д + $ \lfloor 2.6_{} \times $ M $ ^{*} - 0.2_{} \rfloor + $ Г $ + \lfloor $ Г/4 $ \rfloor + \lfloor $ В/4 $ \rfloor - 2_{}\times $ В $ \pmod 7_{} $

Здесь $ \lfloor_{} \mbox{ } \rfloor_{} $ означает целую часть числа, а полученный результат следует интерпретировать:

• Д - число (дата);
• В - первые две цифры года (полное число столетий);
• Г - последние две цифры года;
• M $ ^{ * } $ - номер месяца в соответствии со следующим правилом
  • январь считается 11-м месяцем предыдущего года (т.е. для января $ 1987_{} $ года следует положить Г $ = 86_{} $, M $ ^{*}=11_{} $),
  • февраль считается 12-м месяцем предыдущего года,
  • март считается 1-м месяцем настоящего года: M $ ^{*}=1_{} $, и далее последовательно:

Пример. Установить день недели для 17 октября 1962 г.

Решение. Имеем: Д $ = 17_{} $, М$ ^{*}=8_{} $, Г $ =62_{} $, В $ =19_{} $. Подставляем в формулу:

$$ 17 + \lfloor 2.6 \times 8 - 0.2 \rfloor + 62 + \lfloor 62/4 \rfloor + \lfloor 19/4 \rfloor - 2 \times 19 \pmod 7 \equiv $$ $$ \equiv 3 + 20 + 6 + 15 + 4 - 3 \pmod 7_{} =3 \ . $$

Ответ. Среда.

Определение даты Пасхи по году ☞ ЗДЕСЬ.

Перейдем теперь от задач, представляющих, скорее, исторический интерес, к задачам, порожденным эпохой компьютеров.

Задача. Вычислить $ A^{B} \pmod M $. Предполагается, что число $ A^{B} $ существенно больше числа $ M_{} $: $ A^B >> M $.

Верно ли утверждение:

$$ k_1 \equiv k_2 \pmod{M} \ \Rightarrow \ A^{k_1} \equiv A^{k_2} \pmod{M} \ ? $$

Ответ, к сожалению, отрицателен…

Пример. Найти остаток от деления числа

$$ (77685^{98}+919)^{155} \quad \mbox{ на } \ 132 \, . $$

Решение. Число $ 77685^{98} $ можно посчитать с помощью современного ПК — результатом будет число, состоящее из $ 480 $ цифр. Заметим, однако, что наша конечная цель состоит не в точном вычислении выражений $ A^B_{} $, а в нахождении их остатков от деления на $ 132 $. И эта последняя задача может быть решена с помощью обычного калькулятора. В самом деле, на основании свойств сравнений, выражение $ A^B \pmod{M} $ может быть заменено на $ A_{1}^B \pmod{M} $, где $ A_{1} $ — остаток от деления $ A_{} $ на $ M_{} $, т.е. число, меньшее $ 132 $. В нашем примере $ 77685\equiv 69 \pmod{132} $, поскольку $ 77685=588\times 132 + 69 $. Далее, число $ 69^{98} $ тоже достаточно велико, но вычисление его остатка от деления на $ 132 $ может быть произведено последовательными выделениями остатков более низких степеней: $$69^{98}=69^{2\times 49}=\left(69^2 \right)^{49} \equiv 9^{49} \pmod{132} \ , $$ так как $ 69^2=4761 \equiv 9 \pmod{132} $. Далее, $ 9^3=729 \equiv 69 \pmod{132} $ и $$9^{49} = 9 \times 9^{48} = 9 \times \left( 9^3 \right)^{16} \equiv 9\times 69^{16} \equiv_{_{132}} 9 \times \left(69^2 \right)^{8} \equiv_{_{132}} 9 \times 9^8 =9^9 \ . $$ Это уже проще: $ 9^9 =(9^3)^3\equiv_{_{132}} 69^3 \equiv_{_{132}} 9\times 69 = 621 \equiv_{_{132}} 93 $. Итак, $ 77685^{98} \equiv 93 \pmod{132} $, $ 919\equiv 127 \pmod{132} $, итого: $$(77685^{98}+919)^{155} \equiv_{_{132}} (93+127)^{155} \equiv_{_{132}} 88^{155} \ . $$

И тут нам улыбается удача : $ 88^{2}=58\times 132+88 $, т.е. остаток от деления квадрата числа на модуль $ M_{} $ совпадает с самим числом! Далее все идет как по маслу: $$ 88^{2}\equiv_{_{132}} 88 \ \Rightarrow \ 88^{3}= 88\times 88^2 \equiv_{_{132}} 88\times 88 \equiv_{_{132}} 88 \ \Rightarrow \dots \Rightarrow \ 88^K\equiv_{_{132}} 88 \ npu \ \forall \, K\in \mathbb N \ .$$

Ответ. $ 88 $.

Вычислить наиболее экономным способом остаток от деления числа $ 8765^{43}-1234^{56} $ на $ 1111 $.

Унифицируем теперь вычисление $ A^B \pmod{M} $, организовав вычисления по схеме, которую поясним сначала на примере.

Пример.

$$ A^{769}=A^{7 \cdot 10^2 +6\cdot 10 + 9 } = A^9\cdot \left( A^6 \right)^{10} \cdot \left(\left( A^7 \right)^{10} \right)^{10} = A^9\cdot \left( A^6 \cdot \left ( A^7 \right)^{10} \right)^{10} \ ; $$ т.е. минимизируем количество умножений. Если нас интересует остаток от деления этого числа на $ M_{} $, то начинаем вычисление с «самой внутренней» скобки. Если мы в состоянии вычислить остаток от деления $ A^7 $ на $ M_{} $: $ A_1=A^7 \pmod{M} $, то эту скобку заменяем на $ A_{1} $. Далее, рассматриваем следующую операцию: $ A_1^{10} $. Если мы способны вычислить остаток от деления $ A_1^{10} $ на $ M_{} $: $ A_2= A_1^{10} \pmod{M} $, то производим подстановку этого остатка. Следующая операция — умножение: $ A^6 \cdot A_2 $. Снова от результата вычисляем остаток, и т.д. На каждом шаге мы имеем дело с числами, не превосходящими $ M^{10} $.

В общем же случае для $$ B=\underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_t {\mathfrak b}_{t+1}} = {\mathfrak b}_1\times 10^t+{\mathfrak b}_2 \times 10^{t-1} + \dots +{\mathfrak b}_t \times 10 + {\mathfrak b}_{t+1} $$ схема вычисления $ A^B_{} \pmod{M} $ организуется по тому же принципу: $$ A^B=A^{{\mathfrak b}_{t+1}}\times \left( A^{{\mathfrak b}_{t}}\times \left( A^{{\mathfrak b}_{t-1}}\times \dots \times \left(A^{{\mathfrak b}_{3}} \times \left( A^{{\mathfrak b}_{2}} \times \left(A^{{\mathfrak b}_{1}} \right)^{10}\right)^{10} \right)^{10} \dots \right)^{10} \right)^{10} \ . $$ и от числа, полученного в каждой скобке, оставляется только лишь его остаток от деления на $ M_{} $. Тогда в ходе вычислений не возникнут числа, бóльшие $ M^{10} $, и, если имеющиеся в нашем распоряжении вычислительные средства позволяют оперировать с такими числами, мы решим поставленную задачу.

Еще более экономная²⁾ схема вычислений получится, если число $ B = \underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_t {\mathfrak b}_{t+1}} $ представлено не в десятичной, а в двоичной системе счисления. В этом случае каждая из цифр $ {\mathfrak b}_j $ равна либо $ 0_{} $, либо $ 1_{} $, а в приведенной выше схеме показатель степени $ 10_{} $ надо заменить на $ 2_{} $.

Алгоритм "квадрирования-умножения" вычисления ³⁾ $ A^B \pmod{M} $

1. Число $ B_{} $ переводится в двоичную систему счисления: $$B={\mathfrak b}_1\times 2^t+{\mathfrak b}_2 \times 2^{t-1} + \dots +{\mathfrak b}_t \times 2 + {\mathfrak b}_{t+1} \ , {\mathfrak b}_1=1 \ ; $$

2. Последовательно вычисляются $ A_1 = A \pmod{M} $, $$ A_j= A_{j-1}^2 \times A^{{\mathfrak b}_j} \pmod{M} = \left\{ \begin{array}{lc} A_{j-1}^2 A \pmod{M} & npu \ {\mathfrak b}_j=1 \\ A_{j-1}^2 \pmod{M} & npu \ {\mathfrak b}_j=0 \end{array} \right. $$ для $ j\in\{2,\dots,t+1\} $.

Тогда $ A_{t+1}=A^B \pmod{M} $.

Очевидно, что числа, получающиеся в ходе вычислений, не превысят $ M^2 $.

Пример. Вычислить $ 56^{237}\pmod{317} $.

Решение. $ 237=2^7+2^6+2^5+2^3+2^2+1 $. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 & 5 &6 &7 & 8 \\ \hline {\mathfrak b}_j & 1 & 1 & 1 & 0 & 1 &1 &0 & 1 \\ \hline A_j &{\scriptstyle 56} & {\scriptstyle 56^2\times 56} & {\scriptstyle 315^2 \times 56} & {\scriptstyle 224^2\times 1} & {\scriptstyle 90^2 \times 56} & {\scriptstyle 290^2 \times 56} & {\scriptstyle 248^2 \times 1} & {\scriptstyle 6^2 \times 56} \\ & {\scriptstyle \equiv_{_{317}} 56} & {\scriptstyle \equiv_{_{317}} 315} & {\scriptstyle \equiv_{_{317}} 224} & {\scriptstyle \equiv_{_{317}} 90} & {\scriptstyle \equiv_{_{317}} 290} & {\scriptstyle \equiv_{_{317}} 248} & {\scriptstyle \equiv_{_{317}} 6} & {\scriptstyle \equiv_{_{317}} 114} \\ \hline \end{array} $$

Ответ. $ 114 $.

Пример. Показать, что число Ферма $ 2^{2^5}+1 $ делится на $ 641 $.

Решение. На основании свойства сравнений $$ A \equiv B \pmod{M} \qquad \Rightarrow \qquad A+k \equiv B+k \pmod{M} npu \quad \forall k \in \mathbb Z $$ (см. ☞ ЗДЕСЬ ) достаточно показать, что $ 2^{2^5} $ при делении на $ 641 $ дает в остатке $ 640 $. $$ \begin{array}{|c|c|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 & 5 &6 \\ \hline {\mathfrak b}_j & 1 & 0 & 0 & 0 &0 & 0 \\ \hline A_j & {\scriptstyle 2 \equiv_{_{641}} 2} & {\scriptstyle 2^2 \equiv_{_{641}} 4} & {\scriptstyle 4^2 \equiv_{_{641}} 16 } & {\scriptstyle 16^2 \equiv_{_{641}} 256} & {\scriptstyle 256^2 \equiv_{_{641}} 154} & {\scriptstyle 154^2 \equiv_{_{641}} 640} \\ \hline \end{array} $$

Применение алгоритма ☞ КРИПТОГРАФИЯ.

Возьмем произвольное число $ A\ne 0 $ и будем возводить его последовательно в степень $ A^0,A,A^2,\dots,A^j,\dots $ и вычислять остатки от деления на $ M_{} $: $$ \{r_j=A^j \pmod{M} \}_{j=0}^{\infty}= r_{0} ,r_{1} , \dots , r_{j}, \dots . $$ Ввиду конечности множества остатков $ \{0,\dots, M-1 \} $, начиная с какого-то места наша последовательность начнет повторяться: $$ \exists \ \{k ,\ell\}\subset \mathbb N, 0\le k <\ell \ :\ r_k = r_{\ell} \ , $$ очевидно, что хотя бы одна такая пара показателей $ \{k ,\ell\} $ будет существовать при $ \ell \le M $ (поскольку $ M+1 $ остатков от деления степеней $ A^{j} $ на $ M_{} $ не могут быть различными). Также очевидно, что последовательность становится циклической: $$ r_{k+1} = r_{\ell+1},\ r_{k+2} = r_{\ell+2},\dots $$

Задача. Найти длину цикла последовательности $ \{A^j \pmod{M} \}_{j=0}^{\infty} $ .

Пример.

$$ \begin{array}{ccl} \left\{ 2^j \pmod{5} \right\}_{j=0}^{\infty}&=& 1,2,4,3,1,2,4,3,1,2,\dots ; \\ \left\{2^j \pmod{6} \right\}_{j=0}^{\infty}&=& 1,2,4,2,4,2,4,2,4,2,\dots ; \\ \left\{2^j \pmod{8} \right\}_{j=0}^{\infty}&=& 1,2,4,0,0,0,0,\dots ; \\ \left\{10^j \pmod{7} \right\}_{j=0}^{\infty}&=& 1,3,2,-1,-3,-2,1,3,2,\dots \end{array} $$

В последнем случае мы отступили от введенного нами же правила вычисления остатков от деления чисел, именно: остаток всегда считается неотрицательным числом. «Честным» решением является $$ \left\{10^j \pmod{7} \right\}_{j=0}^{\infty}= 1,3,2,6,4,5,1,3,2,\dots $$ Заметим, однако, что по абсолютной величине положительные остатки превосходят «остатки отрицательные»: $$ 6 > |-1|,\ 4 > |-3|,\ 5> |-2| \ . $$ Покажем, как это обстоятельство позволяет упростить решение задачи о признаке делимости заданного числа $ A_{} $ на число $ 7_{} $. Разобьем десятичное представление числа $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $ на триплеты, начиная с конца, и составим знакочередующиеся суммы первых, вторых и третьих цифр этих триплетов: $$ \begin{array}{ccl} A_1 &= & {\mathfrak a}_{s+1}-{\mathfrak a}_{s-2}+{\mathfrak a}_{s-5}- \dots , \\ A_2 &= & {\mathfrak a}_{s}-{\mathfrak a}_{s-3}+{\mathfrak a}_{s-6}- \dots , \\ A_3 &= & {\mathfrak a}_{s-1}-{\mathfrak a}_{s-4}+{\mathfrak a}_{s-7}- \dots \end{array} $$ Эти три формулы можно объединить в одну: $$A_k=\displaystyle \sum_{j\ge 0} (-1)^j {\mathfrak a}_{s+(2-k)-3j} \quad npu \quad k\in\{1,2,3\} , $$ и суммирование идет по всем тем $ j_{} $, которые сохраняют положительные значения индексов.

Теорема [Паскаль]. Для того чтобы число $ A_{} $ делилось на $ 7_{} $, необходимо и достаточно, чтобы делилось на $ 7_{} $ число

$$ B=A_1+3\,A_2+2\,A_3 \, .$$

Доказательство. $$ \begin{array}{ccl} A&=&{\mathfrak a}_{s+1}+10\cdot {\mathfrak a}_{s}+10^2 \cdot {\mathfrak a}_{s-1} +10^3 \cdot {\mathfrak a}_{s-2}+10^4 \cdot {\mathfrak a}_{s-3} +10^5 \cdot {\mathfrak a}_{s-4} + \dots \equiv_{_7} \\ &=& {\mathfrak a}_{s+1}+ 3 \cdot {\mathfrak a}_{s}+2 \cdot {\mathfrak a}_{s-1} - 1 \cdot {\mathfrak a}_{s-2}-3 \cdot {\mathfrak a}_{s-3} -2 \cdot {\mathfrak a}_{s-4} + \dots \end{array} $$

Пример. Найти все значения неизвестной цифры $ {\color{Red}{\mathfrak{x}}} $, при которых число

$$ \underline{645763{\color{Red}{\mathfrak{x}}}1789} $$ делится на $ 7_{} $.

Решение. Имеем: $$A_1=9-1+6-4,\ A_2=8- {\color{Red}{\mathfrak{x}}} +7-6=9-{\color{Red}{\mathfrak x }},\ A_3=7-3+5=9 \ . $$ Следовательно, $$B=A_1+3\,A_2+2\,A_3 = 55 -3\,{\color{Red}{\mathfrak{x}}} \equiv 6 -3\, {\color{Red}{\mathfrak{x}}} \pmod{7} $$ и последнее число делится на $ 7_{} $ только при $ {\color{Red}{\mathfrak{x}}}=2 $ и $ {\color{Red}{\mathfrak{x}}}=9 $.

Ответ. $ {\color{Red}{\mathfrak{x}}}\in \{2,9\} $.

Упростить критерии делимости на $ 13 $ и $ 37 $, приведенные ☞ ЗДЕСЬ

Теорема [Ферма (малая)]. Если $ p_{} $ простое и $ A_{} $ не делится на $ p_{} $, то $$ A^{p-1} \equiv 1 \pmod{p} \ . $$

Доказательство. Рассмотрим арифметическую прогрессию $$ A, 2A,\dots, jA,\dots, kA, \dots, (p-1)A $$ и найдем остатки ее членов при делении на $ p_{} $: $$r_1,r_2,\dots,r_j,\dots, r_k, \dots, r_{p-1} \ , $$ Утверждается, что все эти остатки отличны от нуля и все различны. Действительно, если $ jA $ делится на простое $ p_{} $, то по теореме 2 , приведенной ☞ ЗДЕСЬ, либо $ j_{} $ делится на $ p_{} $, либо $ A_{} $ делится на $ p_{} $. Последнее невозможно по условию теоремы, а первое — потому что $ j<p $. Если бы числа $ jA $ и $ kA $ имели одинаковый остаток при делении на $ p_{} $, то их разность $ (k-j)A $ должна была делиться на $ p_{} $. Это невозможно, поскольку ни $ A_{} $, ни $ (k-j) $ не делятся на $ p_{} $.

Тогда $ p-1 $ остатков $ \{r_j\}_{j=1}^{p-1} $ представляют собой перестановку чисел $ 1,2,\dots,p-1 $. Так, например, если $ p=7 $, то

• при $ A=9 $ получим последовательность остатков $ 2,4,6,1,3,5 $,
• при $ A=10 $ — $ 3,6,2,5,1,4 $

и т.д. Перемножив сравнения $$ A\cdot 1 \equiv_{_{p}} r_1,\ A\cdot 2 \equiv_{_{p}} r_2,\dots, A\cdot (p-1)\equiv_{_{p}} r_{p-1} \ , $$ получим: $$(p-1)!\, A^{p-1}\equiv_{_{p}}r_1 r_2\times \dots \times r_{p-1}=(p-1)! \ .$$ Иначе говоря, $ (p-1)!\, \left( A^{p-1}-1 \right) $ делится на простое $ p_{} $. Поскольку $ (p-1)! $ не делится на $ p_{} $, то, по теореме 3 , приведенной ☞ ЗДЕСЬ, число $ A^{p-1}-1 $ должно делиться на $ p_{} $. ♦

При доказательстве теоремы использовался результат формальной логики и комбинаторики, который известен под названиями принцип Дирихле, или «принцип ящиков»⁴⁾. Мне кажется более наглядной его формулировка на языке литературного стиля фэнтези: Семь драконов находятся в семи пещерах, два дракона в одной пещере не уживаются, следовательно, все пещеры заняты.

Оригинал рисунка ☞ ЗДЕСЬ.

Если $ p_{} $ простое, то $$ A^{p} \equiv A \pmod{p} \quad npu \quad \forall A\in \mathbb Z . $$

Доказательство для случая, когда $ A_{} $ не делится на $ p_{} $, следует из теоремы Ферма. Если же $ A_{} $ делится на $ p_{} $, то $ A \equiv_{_p} 0 $, но тогда и $ A^p \equiv_{_p} 0 \equiv_{_p} A $. ♦

Итак, теорема Ферма утверждает, что для простого модуля $ M=p $ и $ \operatorname{HOD}(A,p)=1 $ последовательность $ \{A^j \pmod{p} \}_{j=0}^{\infty} $ будет циклической, начиная с ее первого элемента $ 1_{} $, и длина ее цикла равна $ p-1 $. Примеры показывают, что для некоторых $ A_{} $ эта оценка достигается, а для других может быть уменьшена: $$ \begin{array}{ccl} \left\{4^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 4,\,16,\, 13,\, 1,\,4,\dots ; \\ \left\{8^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 8,\, 13,\, 2,\, 16 , \, 9,\, 4,\, 15,\, 1,\, 8,\dots \end{array} $$ Можно доказать, что длина цикла всегда будет равна делителю числа $ p-1 $ (см. теорему 3 ☞ ЗДЕСЬ ).

Альтернативное доказательство теоремы Ферма, основанное на свойстве биномиальных коэффициентов, ☞ ЗДЕСЬ.

Теперь обратимся к общему случаю — когда модуль $ M_{} $ может быть и составным.

Теорема [Эйлер]. Для любых натуральных взаимно простых $ A_{} $ и $ M_{}>1 $ выполняется: $$ A^{\phi(M)}\equiv 1 \pmod{M} \ , $$ здесь $ \phi $ означает функцию Эйлера.

Доказательство. Пусть известно каноническое разложение числа $ M_{} $: $$ M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ . $$ Тогда из теоремы Эйлера следует, что $$ \phi (M) =\prod_{j=1}^{\mathfrak r} p_j^{{\mathfrak m}_j-1}(p_j-1)\ . $$ Докажем, что $$ A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \ . $$ Действительно, из того, что $ \operatorname{HOD} (A,M)=1 $, следует, что $ A_{} $ не делится на $ p_{j} $, но тогда справедлива теорема Ферма: $$ A^{p_j-1} \equiv 1 \pmod{p_j} \ . $$ Покажем, что из этого сравнения следует: $$ A^{p_j(p_j-1)} \equiv 1 \pmod{p_j^{2}} \ . $$ В самом деле, сравнение $ A^{p_j-1} \equiv 1 \pmod{p_j} $ эквивалентно утверждению, что $ A^{p_j-1} - 1 $ делится на $ p_{j} $, т.е. существует $ q\in \mathbb Z $ такое, что $ A^{p_j-1} - 1=qp_j $. Возведем обе части равенства $ A^{p_j-1} = 1+qp_j $ в степень $ p_{j} $ по формуле бинома Ньютона: $$A^{p_j(p_j-1)}=\left( A^{p_j-1} \right)^{p_j}=(1+qp_j)^{p_j}=$$ $$=1+ C_{p_j}^1\, qp_j+C_{p_j}^2\, q^2p_j^2+\dots+ C_{p_j}^{p_j-1}\, q^{p_j-1}p_j^{p_j-1}+q^{p_j}p_j^{p_j} \ ; $$ все слагаемые, кроме первого, делятся на $ p_j^2 $. Аналогичным приемом пользуемся и для доказательства общей формулы $$ A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \quad npu \quad \forall j\in \{1,\dots, {\mathfrak r}\} .$$ Тогда справедливы (сравнение можно возводить в степень, см. теорему ☞ ЗДЕСЬ ) и сравнения $$ A^{\phi(M)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \quad npu \quad \forall j\in \{1,\dots, {\mathfrak r}\} \, , $$ поскольку $ \phi(M) $ делится нацело на $ p_j^{{\mathfrak m}_j-1}(p_j-1) $. Теорема $ 4 $, приведенная ☞ ЗДЕСЬ, позволяет перемножить модули: $$A^{\phi(M)} \equiv 1 \pmod{\prod_{j=1}^{\mathfrak r} p_j^{{\mathfrak m}_j}} \quad \iff \quad A^{\phi(M)} \equiv 1 \pmod{M} \ .$$ ♦

Докажите, что при $ \operatorname{HOD} (A,M)>1 $ сравнение $ A^k \equiv 1 \pmod{M} $ невозможно ни при каком $ k \in \mathbb N $.

Теоремы Ферма и Эйлера позволяют упростить решение проблемы вычисления $ A^B \pmod{M} $, поставленной в ☞ ПУНКТЕ.

Правило упрощения при вычислении $ A^B \pmod{M} $

$$ A^B \equiv \left(A \pmod{M} \right)^{ B \pmod{ \phi(M)}} \pmod{M} \ \mbox{ при } \ \operatorname{HOD}(A,M)=1 \ . $$

Простыми словами: число $ A_{} $ усекается до остатка от деления на $ M_{} $, а число $ B_{} $ — до остатка от деления на $ \phi(M) $.

Пример. Вычислить: $ 229384527^{8374365933} \pmod{97} $.

Решение. Действуем по правилу упрощения: $$229384527\equiv 91 \pmod{97} \quad \Rightarrow \quad A^B \equiv 91^B \pmod{97} \ .$$ Далее, решето Эратосфена позволяет установить простоту числа $ 97 $, и мы можем уменьшить показатель степени: $$8374365933 \equiv 45 \pmod{96} \quad \Rightarrow \quad A^B \equiv 91^{45} \pmod{97} \ .$$ Теперь получившееся выражение можно вычислить по алгоритму "квадрирования-умножения": $ 91^{45} \equiv 22 \pmod{97} $. ♦

Пример. Вычислить: $ 105080803^{104040003} \pmod{10403} $.

Решение. Первый шаг — такой же, как в предыдущем примере: $$ 105080803 \equiv 100 \pmod{10403} \quad \Rightarrow \quad A^B \equiv 100^B \pmod{10403} \ .$$ Далее, число $ 10403 $ факторизуется применением алгоритма Ферма: $ 10403=101\times 103 $, причем оба сомножителя — простые. На основании формулы Эйлера: $ \phi(10403)=100 \times 102=10200 $. Уменьшаем показатель степени: $$ 104040003 \equiv 3 \pmod{10200} \quad \Rightarrow \quad A^B \equiv 100^3 \pmod{10403} \ .$$ Вычислить последнее не составляет труда.

Ответ. $ 1312 $.

Вычислить а) $ 543^{210}+67^{89} \pmod{47} $; б) $ 83199^{169361} \pmod{301} $ .

Пример. Найти две последние цифры числа а) $ 167711^{9999} $ ; б) $ 9^{9^9} $.

Решение. Хотя задача и выглядит иначе, чем только что решенная, тем не менее это задача именно на сравнения. В самом деле, две последние цифры любого числа (в десятичном представлении) формально получаются как остаток от деления этого числа на $ 100 $. Следовательно, поставленная задача сводится к определению $ A^B \pmod{100} $. Имеем: $ \phi(100)=40 $.

а) $ 167711\equiv 11 \pmod{100} \, ,\ 9999\equiv 39 \pmod{40} $. $$167711^{9999} \equiv_{_{100}} 11^{39} =11\times 121^{19} \equiv_{_{100}} 11\times 21^{19} \equiv_{_{100}} \dots \equiv_{_{100}} 91 .$$

б) Здесь $ B=9^9=9\times \left(9^2 \right)^4 \equiv 9 \pmod{40} $. Таким образом, $$9^{9^9} \equiv_{_{100}} 9^9 \equiv_{_{100}} 29^3 \equiv_{_{100}} 89 \ .$$

Ответ. а) $ 91 $ ; б) $ 89 $.

Найти: а) две последние цифры числа $ 4321^{567^{89}} $; б) три последние цифры числа $ 10101^{10101} $ .

Обобщенной функцией Эйлера называется функция $ L(M) $, определяемая для $ M=1 $ как $ L(1)=1 $, а при всех натуральных $ M>1 $ c каноническим разложением $$ M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} $$ следующим образом: $$ L(M) = \operatorname{HOK} \left(p_1^{{\mathfrak m}_1-1}(p_1-1),\ p_2^{{\mathfrak m}_2-1}(p_2-1),\ \dots,\, p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}-1}(p_{\mathfrak r}-1) \right) \ ; $$ здесь $ \operatorname{HOK} $ — наименьшее общее кратное. Очевидно, что $ L(M)=\phi(M) $ при $ M=p^{{\mathfrak m}} $ и что $ \phi(M) $ делится на $ L(M) $ при любых $ M_{} $.

Пример.

$$ L(105840)=L(2^4\cdot 3^3 \cdot 5 \cdot 7^2)= \operatorname{HOK} \left(2^3 ,\, 2\cdot 3^2,\, 4,\, 7\cdot 6\right)=2^3\cdot 3^2 \cdot 7 = 504 $$ при $ \phi(105840)= 24192 $ ; $$ L(10291)=L(41\cdot 251)=\operatorname{HOK} (40,250)=1000 \quad npu \quad \phi(10291)=10000 ; $$ $$ L(49321)= \quad \quad npu \quad \phi(49321)= \qquad \ . $$

Теорема. Для любых натуральных взаимно простых $ A_{} $ и $ M>1 $ выполняется $$ A^{L(M)}\equiv 1 \pmod{M} \ . $$

Доказательство фактически повторяет доказательство теоремы Эйлера. Вытащим из этого доказательства следующее сравнение $$ A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \quad npu \quad \forall j\in \{1,\dots, {\mathfrak r}\} .$$ Поскольку $ L(M) $ делится на любое из чисел $ p_j^{{\mathfrak m}_j-1}(p_j-1) $, то допустимо возведение в степень последнего сравнения: $$ A^{L(M)} \equiv 1 \pmod{p_j^{{\mathfrak m}_j}} \quad npu \ \forall j \in \{ 1,\dots,{\mathfrak r} \} \ .$$ Теорема 4, приведенная ☞ ЗДЕСЬ, позволяет перемножить модули, что и влечет за собой справедливость доказываемого сравнения. ♦

Дальнейшее упрощение вычисления $ A^B \pmod{M} $ возможно с помощью ☞ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ.

Раздел ☞ ЗДЕСЬ.

Задача. При заданных целых числах $ A,B_{} $ и $ M>0 $ решить линейное сравнение $$ Ax \equiv B \pmod{M} \ , $$ т.е. найти все целые числа $ x_{} $, ему удовлетворяющие.

Эта задача эквивалентна задаче решения уравнения $$ A\,x+M\,y=B $$ в целых числах $ x,y_{} $.

Уравнение вида $ f(x_1,\dots,x_n)=0 $ при $ f_{} $ — полиноме от переменных $ x_1,\dots,x_{n} $ с целыми коэффициентами относится к типу алгебраических; если же интересуют только целочисленные решения такого уравнения, то о нем говорят как о диофантовом уравнении. Примером такого уравнения может служить $ x^n+y^n-z^n=0 $ при $ n\in \mathbb N $; оно имеет решение в случае $ n=2_{} $: $ x=3,y=4,z=5 $.

Теорема [Великая теорема Ферма]. Уравнение $ x^n+y^n-z^n=0 $ не имеет целочисленных решений при $ n>2 $.

В ближайших пунктах мы будем иметь дело с линейными диофантовыми уравениями.

Посмотрим, как решали линейные уравнения в дореволюционных гимназиях.

Пример. [3]. a) Заплатить $ 2761 $ руб. пятирублевыми и десятирублевыми билетами.

б) А должен получить $ 25 $ руб. с Б ; но у Б только трехрублевые, а у А десятирублевые билеты. Как разочтутся А и Б ?

Решение. Условие примера а) записывается в виде уравнения $ 5\,x+10\,y= 2761 $; неизвестные $ x_{} $ и $ y_{} $ ищутся среди целых неотрицательных чисел. Его же можно переписать в виде сравнения $ 5\,x \equiv 2761 \pmod{10} $ или же $ 10\,y \equiv 2761 \pmod{5} $. Очевидно, что в каком бы виде мы не переписывали исходное уравнение, оно не будет иметь решений, поскольку при любом выборе $ \{x,y\} \subset \mathbb Z $ выражение $ 5\,x+10\,y $ будет делиться на $ 5_{} $, в то время как число $ 2761 $ на $ 5_{} $ не делится.

Пример б) порождает уравнение $ 3\,y - 10\, x=25 $; неизвестные $ x_{} $ и $ y_{} $ снова предполагаются неотрицательными⁵⁾. Выделим ту неизвестную, коэффициент при которой меньше, чем у другой по абсолютной величине, и выразим эту неизвестную в виде функции другой: $$ y=\frac{10\,x+25}{3}=3\,x+8 +\frac{x+1}{3} \ . $$ Поскольку $ x_{} $ и $ y_{} $ предполагаются целыми числами, то и последняя дробь должна принимать целые значения, т.е. числитель ее должен иметь вид: $$ x+1=3\,u \quad \iff \quad x=-1+3\,u \quad npu \quad u \in \mathbb Z \ . $$ Подставляя это выражение в формулу для $ y_{} $, получим: $$ y=5+10\,u \quad npu \quad u \in \mathbb Z \ . $$ По условию задачи числа $ x_{} $ и $ y_{} $ должны быть неотрицательными, поэтому имеем ограничение на параметр: $ 3\,u \ge 1 $. Ответом к задаче будет бесконечный набор значений для пар $ (x_{},y) $: $$ (2,15);\ (5,25);\ (8,35);\dots $$

♦

Пример [3]. Решить в целых числах уравнение $ 11\,x+8\,y=73 $.

Решение попробуем осуществить в развитие подхода последнего примера. Выразим $ y_{} $ через $ x_{} $: $$y=\frac{73-11\,x}{8}=9-x+\frac{1-3\,x}8 \ . $$ Чтобы число $ y_{} $ было целым, необходимо, чтобы число $ 1-3\,x $ делилось на $ 8_{} $ нацело. $$ 1-3\,x = 8\, u_1 \quad npu \quad u_1 \in \mathbb Z \ . $$ Итак, исходное уравнение $ 11\,x+8\,y=73 $ мы свели к аналогичному уравнению относительно $ x_{} $ и $ u_1 $: $ 3\,x + 8\, u_1=1 $, коэффициенты которого стали меньшими по абсолютной величине. Продолжим процесс: $$x=\frac{1-8\, u_1}3= -2\, u_1 +\frac{1-2\, u_1}3 \ . $$ Чтобы число $ x_{} $ было целым, необходимо, чтобы число $ 1-2\,u_1 $ делилось на $ 3_{} $ нацело: $$ 1-2\,u_1=3\,u_2 \quad npu \quad u_2 \in \mathbb Z \ . $$ И снова коэффициенты полученного уравнения $ 2\,u_1+3\,u_2=1 $ уменьшились по абсолютной величине по сравнению с предыдущим уравнением. $$ u_1=\frac{1-3\,u_2}{2}=-u_2+\frac{1-u_2}{2} \ . $$ Чтобы число $ u_{1} $ было целым, необходимо, чтобы число $ 1-u_2 $ делилось на $ 2_{} $ нацело, т.е. было бы четным: $$1-u_2=2\,u_3 \quad npu \quad u_3 \in \mathbb Z \ . $$ Отсюда получаем выражение для $ u_{2} $ через произвольный целый параметр $ u_{3} $: $$ u_2=1-2\, u_3 \ . $$ Выражаем $ u_{1} $ через $ u_3 $: $$ u_1=-u_2+\frac{1-u_2}{2}=-1+3\, u_3 \ , $$ а теперь $ x_{} $: $$ x=-2\, u_1 +\frac{1-2\, u_1}3=3-8\,u_3 \ , $$ и, наконец, $ y_{} $: $$y=9-x+\frac{1-3\,x}8=5+11\,u_3 \ . $$ Полагая $ u_{3} $ произвольному целому значению, получаем значения для пары искомых неизвестных.

Ответ. $ \dots, (19,-17);\ (11,-6);\ (3,5);\ (-5,16);\ (-13,27); \dots $

Итак, примеры показывают, что сравнение $ Ax_{} \equiv B \pmod{M} $ может не иметь решений вовсе. С другой стороны, легко видеть, что если этому сравнению удовлетворяет какое-либо целое $ x=x_{1} $, то тому же сравнению будут удовлетворять и все числа, сравнимые с $ x_{1} $ по модулю $ M_{} $: $ x \equiv x_1 \pmod{M} $, в частности, и остаток от деления $ x_{1} $ на $ M_{} $. Поэтому одним из способов решения сравнений по модулю $ M_{} $ является простой перебор чисел $ 0,1,2,\dots,M-1 $.

Для того чтобы понять истоки следующего результата, обратимся к решению последнего примера. Перепишем все образовавшиеся уравнения $$ \begin{array}{rcl} 8\,y+11\,x&=&73, \\ 3\,x + 8\, u_1&=&1, \\ 2\,u_1+3\,u_2&=&1, \\ u_2+2\, u_3&=&1, \end{array} $$ и обратим внимание на правило формирования левых частей этих уравнений. Во втором уравнении коэффициент $ 3_{} $ при неизвестном $ x_{} $ является остатком от деления $ 11 $ на $ 8 $, т.е. коэффициентов первого уравнения. В третьем уравнении коэффициент $ 2_{} $ при $ u_{1} $ — это остаток от деления $ 8_{} $ на $ 3_{} $, т.е. коэффициентов предыдущего уравнения. Наконец в последнем уравнении, $ 1_{} $ при $ u_{2} $ является остатком от деления $ 3_{} $ на $ 2_{} $, т.е. коэффициентов третьего уравнения. Таким образом, левые части уравнений генерируются остатками из алгоритма Евклида вычисления наибольшего общего делителя чисел $ 11_{} $ и $ 8_{} $.

Теорема. Сравнение $ Ax_{} \equiv B \pmod{M} $ не имеет решений, если $ B_{} $ не делится на

$$d = \operatorname{HOD} (A,M) \ .$$ При $ B_{} $, кратном $ d_{} $, сравнение имеет ровно $ d_{} $ решений.

Доказательство. Случай $ B\equiv 0 \pmod{M} $ исчерпывается элементарными рассуждениями. В дальнейшем предполагаем $ B\not\equiv 0 \pmod{M} $.

Если $ d = \operatorname{HOD} (A,M)=1 $, то фактически повторим начало доказательства теоремы Ферма. Каждое из чисел арифметической прогрессии $$ A, 2\,A,\dots, j\,A,\dots, k\,A, \dots, (M-1)A $$ дает при делении на $ M_{} $ ненулевой остаток, и при $ k\ne j $ эти остатки будут различными. Действительно, если $ j\,A $ делится на $ M_{} $, то поскольку $ \operatorname{HOD} (A,M)=1 $ (по теореме 3 , приведенной ☞ ЗДЕСЬ ), $ j_{} $ делится на $ M_{} $. Последнее невозможно, поcкольку $ j<M $. Если бы числа $ j\,A $ и $ k\,A $ имели одинаковый остаток при делении на $ M_{} $, то их разность, равная $ (k-j)A $, должна была бы делиться на $ M_{} $. По теореме 3 , приведенной ☞ ЗДЕСЬ, число $ k-j $ должно тогда делиться на $ M_{} $, что невозможно, поскольку оно меньше $ M_{} $.

Итак, $ M-1 $ чисел должны иметь различные остатки при делении на $ M_{} $: $$r_1,r_2,\dots,r_j,\dots, r_k, \dots, r_{M-1} \ , $$ понятно, что эти остатки — каким-то образом переставленные числа $ 1,2,\dots, M-1 $; среди последних будет и единственное число, сравнимое с $ B_{} $ по модулю $ M_{} $. Следовательно, существует единственное $ x \in \{1,2,\dots,M-1 \} $ такое, что $ xA\equiv B \pmod{M} $.

Пусть теперь $ d=\operatorname{HOD} (A,M)>1 $ и $ B_{} $ не делится на $ d_{} $. Если существует решение $ x=x_0\in \mathbb Z $ сравнения, то разность $ Ax_0-B $ делится на $ M_{} $, а следовательно, и на $ d_{} $. Число $ A_{} $ также делится на $ d_{} $. Но тогда и $ B_{} $ должно делиться на $ d_{} $. Пришли к противоречию.

Пусть $ B_{} $ делится на $ d>1 $: $ B=B_1d $. Поскольку $ d= \operatorname{HOD} (A,M) $, то можно разделить нацело: $ A=A_1d $, $ M=M_1d $; очевидно, $ \operatorname{HOD} (A_1,M_1)=1 $. Тогда сравнение $ Ax_{} \equiv B \pmod{M} $ равносильно $ A_1x \equiv B_1 \pmod{M_1} $. Случай $ B_1\equiv 0 \pmod{M_1} $ тривиален. Если же $ B_1\not\equiv 0 \pmod{M_1} $, то, по доказанному выше, такое сравнение имеет единственное решение по модулю $ M_1 $: существует $ x_1\in \{1,2,\dots,M_1-1 \} $ такое, что $ A_1x_1 \equiv B_1 \pmod{M_1} $. Тогда $ d_{} $ чисел $$x_1,x_1+M_1,x_1+2M_1,\dots, x_1+(d-1)M_1 $$ будут решениями сравнения $ Ax_{} \equiv B \pmod{M} $. Действительно, $ x_1+kM_1<M $ при $ k\in \{0,1,\dots,d-1 \} $ и $$A(x_1+kM_1)-B=A_1d(x_1+kM_1)-B_1d=(A_1x_1-B_1)d+A_1kM \equiv 0 \pmod{M} \ .$$ Других решений у сравнения $ Ax_{} \equiv B \pmod{M} $ быть не может. Действительно, если $ Ax_2 \equiv B \pmod{M} $, то $ A(x_2-x_1) \equiv 0 \pmod{M} $, тогда $ A_1(x_2-x_1) $ должно делиться на $ M_{1} $, следовательно, ввиду того, что $ \operatorname{HOD} (A_1,M_1)=1 $, разность $ x_2-x_1 $ делится на $ M_{1} $. ♦

Доказать, что при любых ненулевых числах $ \{A_1,A_2\} \subset \mathbb Z $ уравнение

$$ A_1x+A_2y=A_1\cdot A_2 $$ разрешимо в целых числах.

Теорема [Паоли] [4]. Число неотрицательных целочисленных решений уравнения

$$ A_1x+A_2y=B , \mbox{ где } \ \{A_1,A_2,B\} \subset \mathbb N, \operatorname{HOD}(A_1,A_2)=1 \, ,$$ равно $$ \left\lfloor \frac{B}{A_1A_2} \right\rfloor \qquad \mbox{ или } \qquad \left\lfloor \frac{B}{A_1A_2} \right\rfloor +1 \ . $$

Итак, алгоритм решения сравнения $ Ax_{} \equiv B \pmod{M} $ включает в себя вычисление $ d= \operatorname{HOD}(A,M) $. Основным конструктивным способом вычисления последнего является алгоритм Евклида. Вспомним, однако, что вычислительная схема алгоритма может быть использована и для решения другой задачи — нахождения линейного представления наибольшего общего делителя, т.е. чисел $ u_{} $ и $ v_{} $, удовлетворяющих равенству $$ uA+vM=d \ ;$$ при этом число $ u_{} $ можно выбрать из множества $ \{0,1,\dots,M-1 \} $. Заметим, что последнее равенство может быть переписано на языке сравнений: $$ Au \equiv d \pmod{M} \ ; $$ таким образом, в частном случае $ B=d $ сравнение имеет решение $ x=u $. Более того, в случае, когда $ B_{} $ делится на $ d_{} $, решение сравнения получится по формуле $ x=uB/d $. Теорема существования из предыдущего пункта утверждает, что во множестве $ \{0,1,\dots,M-1 \} $ будет существовать $ d_{} $ решений. Все эти решения получаются «сдвигом» уже полученного на величину, кратную $ M/d $: множество $$ \left\{ u \frac{B}{d} +k \frac{M}{d} \pmod{M} \, \big| \, k\in \{0,1,\dots,d-1 \} \right\} $$ содержит в себе решения сравнения $ Ax_{} \equiv B \pmod{M} $, и все эти решения различны. ♦

Пример. Решить сравнение $ 356\,x \equiv 122 \pmod{82} $.

Решение. Прежде всего упрощаем сравнение, заменяя числа в обеих его частях на их остатки от деления на модуль: $$28\, x \equiv 40 \pmod{82} \ .$$ Далее вычисляем $ d=\operatorname{HOD}(28,82)=2 $ по алгоритму Евклида: в схеме этого алгоритма имеем $ k=2 $ и $ q_1=2,\, q_2=1 $. Поскольку $ 40 $ делится на $ d=2 $, то, по теореме существования, сравнение имеет два решения. Для их нахождения вычисляем $ u_{} $ с помощью континуанты: $ u=1+q_1q_2=3 $.

Ответ. $ \{60 \pmod{82} \, ; 19=101 \pmod{82}\} $.

Пример. Решить сравнение $ 356\,x \equiv 122 \pmod{84} $.

Решение. Сравнение эквивалентно $ 20\, x \equiv 38 \pmod{84} $ и оно не имеет решений, поскольку число $ 38 $ не делится нацело на $ \operatorname{HOD}(20,84)=4 $. ♦

Пример. Решить сравнение $ 2340\, x \equiv 72 \pmod{9903} $.

Решение. В схеме алгоритма Евклида нахождения $ \operatorname{HOD}(2340,9903) $ имеем: $$k=5,\ q_1=4,\ q_2=4,\ q_3=3,\ q_4=4,\ q_5=3,\ d=3 \ .$$ Вычисляем континуанту: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline j & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline q_j & - & 4 & 4 & 3 & 4 & 3\\ \hline K_j(q_1,q_2,\dots,q_j) & 1 & 4 & 17 & 55 & 237 & 766 \\ \hline \end{array} $$ По ☞ формуле получаем: $ u=u_5=(-1)^{5}K_5(q_1,q_2,\dots,q_5) =-766 $. Множество решений сравнения имеет вид $$ \begin{array}{llll} \bigg\{-766 \cdot \displaystyle \frac{72}{3} \equiv &1422 \pmod{9903} \, ;\ & & \\ &1422 + \displaystyle \frac{9903}{3} \equiv & 4723 \pmod{9903} \, ;\ & \\ & & 4723 + \displaystyle \frac{9903}{3} \equiv 8024 \pmod{9903} \bigg\} & \ . \end{array} $$ ♦

Нас теперь будет интересовать один частный случай, при котором решение сравнения будет единственным во множестве $ \{0,1,2,\dots,M-1\} $.

Единственное решение сравнения $$ Ax \equiv 1 \pmod{M} \quad npu \quad \ \operatorname{HOD}(A,M)=1 $$ называется обратным числу $ A_{} $ относительно умножения (или мультипликативным обратным) по модулю $ M_{} $. Его обозначают $ A^{-1} \pmod{M} $.

Формально мультипликативное обратное может быть получено с помощью теоремы Эйлера: $$x = A^{\phi (M)-1} \pmod{M} \ .$$ Однако вычисление по этой формуле требует знания канонического разложения числа $ M_{} $, нахождение которого для больших $ M_{} $ является трудоемкой задачей. С вычислительной точки зрения более конструктивна предложенная выше схема, которую мы выпишем отдельно:

Алгоритм нахождения числа, обратного $ A_{} $ относительно умножения по модулю $ M_{} $

1. строится последовательность частных $ q_1,q_2,\dots,q_k $ из алгоритма Евклида нахождения $ \operatorname{HOD} (A,M) $;

2. по ☞ формуле вычисляется величина $ \tilde u=u_k =(-1)^{k}K_k(q_1,q_2,\dots,q_k) $ ;

3. при необходимости к числу $ \tilde u $ прибавляется целое кратное числа $ M_{} $ так, чтобы число $ \tilde {\tilde u}=\tilde u+tM $ попало в интервал $ 0<\tilde {\tilde u}<M $.

Число $ \tilde {\tilde u} $ и будет обратным числу $ A_{} $ относительно умножения по модулю $ M_{} $: $$ \tilde {\tilde u} = A^{-1} \pmod{M} \qquad . $$

Пример. Найти число, обратное числу $ 45 $ относительно умножения по модулю $ 391 $.

Решение. В схеме алгоритма Евклида поиска $ \operatorname{HOD}(45,391) $ будет $ k=5 $ и $ q_1=8, q_2=1, q_3=2, q_4=4, q_5=1 $. Тогда $ \tilde u=(-1)^{5}K(q_1,q_2,\dots,q_5)=-139 $. Прибавляем $ M_{} $, чтобы получить положительное число: $ \tilde {\tilde u}=\tilde u+M=252 $.

Ответ. $ 252 $. Проверка. $ 252\times 45=29 \times 391+1 $.

Результаты предыдущих пунктов позволили полностью исследовать задачу решения линейного уравнения вида $ A_1x+A_2y=B $ относительно двух неизвестных $ x_{} $ и $ y_{} $. Рассмотрим теперь линейное уравнение относительно $ n>2 $ неизвестных $ x_1,x_2,\dots,x_n $: $$ A_1x_1+A_2x_2+\dots+A_nx_n=B \quad npu \quad \{A_1,A_2,\dots,A_n,B\} \subset \mathbb Z \ . $$ Предположим, что хотя бы один коэффициент $ A_{j} $ отличен от нуля.

Теорема. Пусть $ d=\operatorname{HOD} (A_1,A_2,\dots,A_n) $. Уравнение имеет решение тогда и только тогда, когда $ B_{} $ делится $ d_{} $.

Доказательство. Необходимость. Все числа $ A_1,A_2,\dots,A_n $ делятся на $ d_{} $, следовательно и сумма $ A_1x_1+A_2x_2+\dots+A_nx_n $ делится на $ d_{} $. Значит и число $ B_{} $ должно делиться на $ d_{} $. ♦

Пример [3]. Решить уравнение $ 10\,x+9\,y+7\,z=58 $.

Решение. Выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте: $$ z=\frac{58-10\,x-9\,y}{7}=8-x-y+\frac{2-3\,x-2\,y}{7} \ . $$ Поскольку, по предположению, все неизвестные должны быть числами целыми, то положим $$\frac{2-3\,x-2\,y}{7}=u_1 \quad \mbox{ или } \quad 2-3\,x-2\,y=7\, u_1 \ . $$ Теперь выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте: $$ y = \frac{2-3\,x-7\, u_1}{2}= 1- x-3\, u_1- \frac{x+u_1}{2} \ . $$ Положим $$ \frac{x+u_1}{2}=u_2 \quad \mbox{ или } \quad x=2\,u_2-u_1 \ . $$ Подставим найденное выражение в предыдущее выражение для $ y_{} $: $$ y=1-x-3\,u_1-u_2=1-(2\,u_2-u_1)-3\,u_1-u_2=1-2\,u_1-3\,u_2 \ ; $$ и, окончательно, в выражение для $ z_{} $: $$ z=8-(2\,u_2-u_1)-(1-2\,u_1-3\,u_2)+u_1=7+4\,u_1+u_2 \ . $$ Таким образом, значения неизвестных $ x,y,z $ полностью определяются формулами $$ x=-u_1+2\,u_2,\ y=1-2\,u_1-3\,u_2,\ z=7+4\,u_1+u_2 \quad npu \quad \{u_1,u_2\} \subset \mathbb Z \ . $$ Если поставить дополнительное требование положительности решений, то получаем условия на параметры $ u_1,u_2 $ в виде неравенств $$ -u_1+2\,u_2>0 ,\ 1-2\,u_1-3\,u_2 > 0,\ 7+4\,u_1+u_2 > 0 \ . $$ Разрешим каждое из этих неравенств относительно $ u_{1} $: $$ u_1<2\,u_2, \ u_1 < \frac{1-3\,u_2}{2},\ u_1>\frac{-7-u_2}{4} \ . $$ Объединяя первое неравенство с третьим и второе неравенство с третьим, получаем ограничения на $ u_{2} $: $$ \frac{-7-u_2}{4}< 2\,u_2, \ \frac{-7-u_2}{4}< \frac{1-3\,u_2}{2} , $$ откуда: $$ -7/9 < u_2 < 9/5 \ . $$ Поскольку, по предположению, $ u_{2} $ — целое, то $ u_2\in \{0,1\} $. Подставляем $ u_2=0 $ в систему неравенств относительно $ u_{1} $: $$ u_1<0,\ u_1<\frac{1}{2},\ u_1>-\frac{7}{4} \qquad \Rightarrow \qquad u_1=-1 \ . $$ Подставляем $ u_2=1 $ в систему неравенств относительно $ u_{1} $: $$u_1<2,\ u_1< -1,\ u_1>-2 \ . $$ Эта система неравенств не имеет целых решений. Таким образом, положительные решения исходного сравнения получаются только при значениях параметров $ u_1=-1,u_2=0 $: $$ x=1,\ y=3, \ z=3 \ . $$ ♦

Решение системы линейных уравнений в целых числах ☞ ЗДЕСЬ.

Более общей является задача решения системы сравнений $$ A_1x \equiv B_1 \pmod{M_1},\ \dots,\ A_kx \equiv B_k \pmod{M_k} \ . $$ Если число $ x=x_1\in \mathbb Z $ удовлетворяет этой системе, то ей, очевидно, удовлетворяет и любое число вида $ x_1+t\cdot \operatorname{HOK}(M_1,\dots,M_k) $ при $ t \in \mathbb Z $, иными словами, любое число, сравнимое с $ x_{1} $ по модулю $ \operatorname{HOK}(M_1,\dots,M_k) $: $$ x\equiv x_1 \pmod{\operatorname{HOK}(M_1,\dots,M_k)} \, . $$ По аналогии с задачей предыдущего пункта будем говорить о числе решений системы сравнений, имея в виду только решения из множества $ \{ 0,1,\dots, \operatorname{HOK}(M_1,\dots,M_k) -1 \} $.

Предположим, что $ \operatorname{HOD}(A_j,M_j)=1 $ для каждого $ j\in \{1,\dots,k\} $. На основании теоремы существования, сравнение $ A_jx \equiv B_j \pmod{M_j} $ имеет единственное решение среди чисел $ \{0,1,\dots,M_j-1 \} $. Обозначим это решение через $ B_j^{\prime} $. Тогда система может быть заменена на эквивалентную (т.е. имеющую то же множество решений) ей систему более простого вида $$ x \equiv B_1^{\prime} \pmod{M_1},\ \dots,\ x \equiv B_k^{\prime} \pmod{M_k} \ . $$ Для упрощения обозначений будем считать, что исходная система уже приведена к такому виду, т.е. в ней $ A_1=1, \dots, A_k=1 $ и числа $ B_{1},\dots,B_{k} $ неотрицательны. Решение такой системы можно интерпретировать как нахождение натурального числа, дающего при делении на $ M_{1} $ остаток $ B_{1} $, при делении на $ M_{2} $ остаток $ B_{2} $, и т.д., а при делении на $ M_{k} $ остаток $ B_{k} $.

Теорема [Китайская теорема об остатках]. Пусть числа $ 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} \quad npu \quad 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}, \quad npu \quad 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} $$

Доказательство теоремы, ее развитие и применения ☞ ЗДЕСЬ.

В настоящем пункте нас будут интересовать решения сравнения $$ f(x) \equiv 0 \pmod{M} \ , $$ где $ f(x)= a_0x^n+a_1x^{n-1}+\dots +a_{n-1}x +a_n $ — полином по переменной $ x_{} $ с целыми коэффициентами $ a_{0},\dots,a_n $. Будем считать $ a_{0} \ne 0 $ и $ n=\deg f > 1 $.

Если модуль $ M_{} $ раскладывается в произведение $$M= M_1 \times \dots \times M_k$$ попарно взаимно простых сомножителей $ M_1, \dots, M_k $, то решение сравнения $ f(x) \equiv 0 \pmod{M} $ эквивалентно решению системы сравнений $$ f(x) \equiv 0 \pmod{M_1},\ \dots ,\ f(x) \equiv 0 \pmod{M_k} \ . $$ В самом деле, согласно теореме $ 4 $, приведенной ☞ ЗДЕСЬ , число $ x_0\in \mathbb Z $ будет решением сравнения $ f(x) \equiv 0 \pmod{M} $ тогда и только тогда, когда оно удовлетворяет каждому сравнению $ f(x) \equiv 0 \pmod{M_j} $. С другой стороны, если известны все решения каждого из сравнений $ f(x) \equiv 0 \pmod{M_j} $, то с помощью китайской теоремы об остатках (КТО) из них можно сконструировать все решения сравнения $ f(x) \equiv 0 \pmod{M} $. Действительно, если обозначить через $ x_{j} $ произвольное решение сравнения $ f(x) \equiv 0 \pmod{M_j} $, то КТО утверждает, что существует единственное число $ x=x_0\in\{0,1,\dots,M-1\} $, удовлетворяющее одновременно сравнениям $$x \equiv x_1 \pmod{M_1},\ \dots , x \equiv x_k \pmod{M_k} $$ и дает конструктивные способы его нахождения. Это число удовлетворяет всем сравнениям $ f(x) \equiv 0 \pmod{M_j} $, а, следовательно, и сравнению $ f(x) \equiv 0 \pmod{M} $. Из двух способов представления решения, изложенных в теореме, для нашей задачи более предпочтителен вариант 1 .

Пример. Решить сравнение $ x^3+11\,x-12 \equiv 0 \pmod{56} $, если известно, что

решениями сравнения $ x^3+11\,x-12 \equiv 0 \pmod{7} $ являются числа $ \{1,5\} $, а

решениями сравнения $ x^3+11\,x-12 \equiv 0 \pmod{8} $ являются числа $ \{1,3,4,5,7\} $.

Решение. В обозначениях КТО имеем $$8\cdot y_1 \equiv 1 \pmod{7} \ \Rightarrow \ y_1=1 \ , \ 7\cdot y_2 \equiv 1 \pmod{8} \ \Rightarrow \ y_2=7 \ .$$ Таким образом, все решения сравнения $ x^3+11\,x-12 \equiv 0 \pmod{56} $ получаются в форме всевозможных комбинаций вида $$ 1\times 8 \times \left\{ \begin{array}{c} 1 \\ 5 \end{array} \right\} + 7\times 7 \times \left\{ \begin{array}{c} 1 \\ 3 \\ 4 \\ 5 \\ 7 \end{array} \right\} \pmod{56} \ . $$

Ответ. $ x\in \{1,\,5,\, 12,\, 15,\, 19,\, 29,\, 33,\, 36,\, 43,\, 47\} $.

Мы ограничимся рассмотрением случая, когда все числа $ M_1,\dots,M_k $ — различные простые. Тогда решение сравнения $ f(x) \equiv 0 \pmod{M} $ сводится к решению $$ f(x) \equiv 0 \pmod{p} $$ при простом $ p_{} $. Сделаем некоторые предположения относительно коэффициентов $ f_{}(x) $. На основании правил действий со сравнениями любой из этих коэффициентов можно заменить его остатком при делении на $ p_{} $, это позволит рассматривать сравнения при ограниченных коэффициентах, например: $$\{ a_1,\dots , a_n \} \subset \{-(p-1),\dots,-2,-1,0,1,2, \dots, p-1 \} \ . $$ В дальнейшем будем предполагать такое приведение произведенным, и по-прежнему считать, что $ a_0\ne 0 $. Домножая $ f(x) \equiv 0 \pmod{p} $ на обратное числу $ a_{0} $ относительно умножения по модулю $ p_{} $, делаем старший коэффициент равным $ 1_{} $.

Теорема 1. Если $ \deg f(x)=n $, то сравнение $ f(x) \equiv 0 \pmod{p} $ не может иметь более $ n_{} $ различных решений.

Доказательство проведем индукцией по $ n_{} $. Для $ n_{}=1 $ утверждение теоремы справедливо: сравнение $ x+a_1 \equiv 0 \pmod{p} $ имеет единственное решение. Пусть утверждение теоремы справедливо для любого полинома степени $ n_{}-1 $. Если теперь предположить, что $ \deg f(x)=n $ и что $ x=\lambda_1 $ является решением сравнения $ f(x) \equiv 0 \pmod{p} $: $ f(\lambda_1)\equiv 0 \pmod{p} $, то из теоремы Безу следует $$f(x)\equiv (x-\lambda_1)\, f_1(x) \pmod{p} \ ,$$ где $ f_{1}(x) $ — полином с целыми коэффициентами степени $ n_{}-1 $. Если $ x=\lambda_j\ne \lambda_1 $ — какое-то другое решение сравнения $ f(x) \equiv 0 \pmod{p} $, то оно должно удовлетворять сравнению $ f_1(x) \equiv 0 \pmod{p} $, которое по индуктивному предположению не может иметь более $ n_{}-1 $ решений. Следовательно, число решений сравнения $ f(x) \equiv 0 \pmod{p} $ не превышает $ n_{} $. ♦

Теорема 2. Если сравнение $ f(x) \equiv 0 \pmod{p} $ имеет $ n_{} $ различных решений $ \left\{\lambda_1,\dots, \lambda_n \right\}\subset \{0,1,\dots,p-1\} $, то имеет место представление

$$f(x)\equiv (x-\lambda_1)\times \dots \times (x-\lambda_n) + p\,F(x) \ , $$ где $ F_{}(x) $ — полином с целыми коэффициентами.

Доказательство. Рассмотрим полином $$g(x) = f(x)- (x-\lambda_1)\times \dots \times (x-\lambda_n) \ . $$ Очевидно, что $$m = \deg g(x) \le n-1 \ \mbox{ и что }\ g(\lambda_1) \equiv 0 \pmod{p}, \dots , g(\lambda_n) \equiv 0 \pmod{p} \ . $$ Покажем, что все коэффициенты полинома $$g(x)=b_0x^m+b_1x^{m-1}+ \dots + b_m $$ делятся на $ p_{} $. Действительно, если $ b_0\not \equiv 0 \pmod{p} $, то сравнение $ g(x)\equiv 0 \pmod{p} $ не может иметь более $ m<n_{} $ решений, а оно уже имеет $ n_{} $ решений $ \lambda_j $. Следовательно, $ b_0 \equiv 0 \pmod{p} $ и к сравнению $$ b_1x^{m-1}+ \dots + b_m \equiv 0 \pmod{p} $$ применяем те же самые рассуждения. Окончательно получаем, что все коэффициенты $ g_{}(x) $ делятся на $ p_{} $, и полином $ F(x)= g(x)/p $ будет иметь целые коэффициенты. ♦

Теорема 3. Если сравнение $ f(x) \equiv 0 \pmod{p} $ имеет $ n_{} $ различных решений и полином $ f_{}(x) $ допускает представление в виде произведения

$$f(x)\equiv f_1(x)\times \dots \times f_k(x) $$ полиномов с целыми коэффициентами, то сравнение $ f_j(x) \equiv 0 \pmod{p} $ имеет ровно $ \deg f_j(x) $ решений.

Доказательство. Обозначим $ n_j = \deg f_j(x) $. Тогда $ n_1+\dots+ n_k =n $. Любое из $ n_{} $ решений $ x=\lambda $ сравнения $ f(x) \equiv 0 \pmod{p} $ должно удовлетворять хотя бы одному из сравнений $ f_j(x)\equiv 0 \pmod{p} $: $$f(\lambda) \equiv 0 \pmod{p} \quad \Rightarrow \quad f_1(\lambda)\times \dots \times f_k(\lambda) \equiv 0 \pmod{p} \ . $$ Если сравнение $ f_j(x)\equiv 0 \pmod{p} $ имеет меньше чем $ n_{j} $ решений, то, поскольку суммарное количество решений всех сравнений должно оставаться равным $ n_{} $, какое-то другое сравнение $ f_{\ell}(x)\equiv 0 \pmod{p} $ должно иметь больше чем $ n_{\ell} $ решений. Последнее противоречит теореме 1. ♦

Сложность материала — повышенная. Для понимания потребуется знакомство с разделом ☞ ИНДЕКС (ДИСКРЕТНЫЙ ЛОГРАРИФМ).

Рассмотрим теперь двучленное сравнение $$ x^n \equiv B \pmod{p} \ . $$ В случае существования решения этого сравнения, его можно назвать корнем $ n_{} $-й степени из числа $ B_{} $ по модулю $ p_{} $. Для установления структуры множества этих корней привлечем аппарат индексов по основанию произвольного первообразного корня $ \Lambda_{} $ по модулю $ p_{} $. Требуемое сравнение выполняется тогда и только тогда, когда выполняется линейное сравнение $$ n\cdot \operatorname{ind}_{_{\Lambda}} x \equiv \operatorname{ind}_{_\Lambda} B \pmod{p-1} \ . $$ (см. следствие к теореме ☞ ЗДЕСЬ ). Рассматривая последнее сравнение относительно неизвестного числа $ z = \operatorname{ind}_{_\Lambda} x $, мы можем воспользоваться теоремой о существовании решений линейного сравнения, из которой следует, что решение существует тогда и только тогда, когда $ \operatorname{ind}_{_\Lambda} B $ делится на $ d = \operatorname{HOD}(n,\,p-1) $; в этом случае существует ровно $ d_{} $ чисел множества $ \{0,1,\dots,p-2 \} $, ему удовлетворяющих. Если имеются в наличии таблицы для вычисления индексов, то можно и установить эти решения.

Пример. Решить сравнение $ x^{12} \equiv 16 \pmod{17} $.

Решение. Число $ \Lambda=3 $ является первообразным корнем по модулю $ 17 $. Воспользовавшись таблицей индексов по модулю $ 17 $ и основанию $ 3_{} $: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline \operatorname{ind}_{3} A&0&14&1&12&5&15&11&10&2&3&7&13&4&9&6&8 \\ \hline \end{array} $$ получим линейное сравнение $ n\cdot \operatorname{ind}_{_{\Lambda}} x \equiv \operatorname{ind}_{_\Lambda} B \pmod{p-1} $ в виде $$12 \cdot \operatorname{ind}_{_3} x \equiv 8 \pmod{16} \ .$$ Поскольку $ 8_{} $ делится на $ d=\operatorname{HOD}(16,12)=4 $, то это сравнение имеет ровно $ 4_{} $ решения, которые легко находятся с помощью ☞ АЛГОРИТМА: $ \operatorname{ind}_{_3} x \in \{2,\, 6,\, 10,\, 14 \} $. Для определения значений $ x_{} $ по величинам $ \operatorname{ind}_{_3} x $ снова обращаемся к таблице.

Ответ. $ x\in \{9,\, 15,\, 8,\, 2 \} $.

Хотя использование аппарата индексов и позволяет решить нелинейное сравнение, однако — из соображений здравого смысла — как условие разрешимости, так и количество возможных решений не должно зависеть от выбора основания $ \Lambda_{} $. Иначе говоря, должен существовать критерий разрешимости $ x^n \equiv B \pmod{p} $, не использующий понятия индекса.

Теорема [Эйлер]. Пусть $ d=\operatorname{HOD}(n,p-1) $. Сравнение $ x^n \equiv B \pmod{p} $ имеет решение тогда и только тогда, когда выполняется сравнение

$$ B^{(p-1)/d} \equiv 1 \pmod{p} \ ; $$ в случае его выполнения сравнение $ x^n \equiv B \pmod{p} $ имеет ровно $ d_{} $ решений.

Доказательство. Необходимость. Пусть существует решение $ x=\lambda \in \{0,1,\dots, p-1 \} $ сравнения $ x^n \equiv B \pmod{p} $: $ B \equiv \lambda^n \pmod{p} $. Возведем это сравнение в степень $ (p-1)/d $ (это целое число, по определению $ d_{} $): $$B^{(p-1)/d} \equiv_{_p} \left( \lambda^n \right)^{(p-1)/d} = \left( \lambda^{n/d} \right)^{p-1} \ \equiv_{_p} \ 1 \pmod{p} $$ на основании теоремы Ферма.

Достаточность. Пусть условие $ B^{(p-1)/d} \equiv 1 \pmod{p} $ выполняется. Докажем, что линейное сравнение $ n\cdot \operatorname{ind}_{_{\Lambda}} x \equiv \operatorname{ind}_{_\Lambda} B \pmod{p-1} $ имеет решение при некотором первообразном корне $ \Lambda_{} $, т.е. что $ \operatorname{ind}_{_\Lambda} B $ делится на $ d=\operatorname{HOD}(n,\, p-1) $. Возведем сравнение $$ \Lambda^{\operatorname{ind}_{_\Lambda}B} \equiv B \pmod{p} $$ в степень $ (p-1)/d $: $$ \Lambda^{(\operatorname{ind}_{_\Lambda}B)(p-1)/d} \equiv_{_p} \ B^{(p-1)/d} \equiv_{_p} \ 1 \pmod{p} \ . $$ Последнее сравнение, ввиду теоремы 3, приведенной ☞ ЗДЕСЬ, гарантирует, что число $ (\operatorname{ind}_{_\Lambda}B)(p-1)/d $ делится на $ \operatorname{ord} (\Lambda)=p-1 $ (поскольку $ \Lambda $ является первообразным корнем по модулю $ p_{} $). Но тогда $ \operatorname{ind}_{_\Lambda} B $ делится на $ d_{} $. ♦

При выполнении условия теоремы множество решений сравнения $ x^n \equiv B \pmod{p} $ совпадает со множеством решений сравнения

$$x^{d} \equiv B^{z} \pmod{p} \quad , $$ где $ z_{} $ означает решение линейного сравнения $$\frac{n}{d} \cdot z \equiv 1 \left(\mod \, \frac{p-1}{d} \right) \ .$$

Мы не будем доказывать этот результат в его общем виде, а рассмотрим только случай единственности решения сравнения $ x^n \equiv B \pmod{p} $, который, очевидно, получается, когда числа $ n_{} $ и $ p-1 $ взаимно просты. Предположив, что $ B_{} $ не делится на $ p_{} $, мы — на основании теоремы Ферма — получаем единственное решение $ x\in \{0,1,\dots,p-1\} $. Та же теорема Ферма позволит найти и представление этого решения.

Алгоритм решения сравнения $ x^n \equiv B \pmod{p} $

1. С помощью алгоритма решения линейного сравнения решаем сравнение $$ n\cdot z \equiv 1 \pmod{p-1} $$ относительно $ z\in \{0,1,\dots,p-2\} $.

2. С помощью алгоритма "квадрирования-умножения" вычисляем $$ x=B^z \pmod{p} \ . $$ Это и есть решение.

В самом деле, поскольку $ \operatorname{HOD}(n,p-1)=1 $, то, на основании теоремы о существовании решения линейного сравнения, сравнение $ n\cdot z \equiv 1 \pmod{p-1} $ однозначно разрешимо относительно $ z_{} $. Имеем $$ n\cdot z = 1+t(p-1) \ npu \ t\in \mathbb Z \ , $$ и $$\left( B^z \right)^n = B^{1+t(p-1)} =B\cdot \left(B^{p-1} \right)^t \equiv B \pmod{p}$$ на основании теоремы Ферма. Таким образом, число $ x=B^z \pmod{p} $ является решением сравнения $ x^n \equiv B \pmod{p} $; по теореме, это решение единственно.

Пример. Решить сравнение $ x^7 \equiv B \pmod{11} $.

Решение. Поскольку $ \operatorname{HOD}(7,11-1)=1 $, то решение сравнения единственно при любых $ B\in \{0,1,\dots, 10\} $. Решаем сравнение $$7\, z \equiv 1 \pmod{10} \ \Rightarrow \ z=3 \ .$$ Таким образом, $ x=B^3 \pmod{11} $ будет решением сравнения для всех $ B_{} $. ♦

Применение двучленных сравнений см. в разделе ☞ КРИПТОГРАФИЯ.

Множество целых чисел можно естественным образом рассортировать на подмножества, поместив в каждое из них все числа, имеющие один и тот же остаток $ r_{} $ от деления на фиксированный модуль $ M_{} $.

Классом по модулю $ M_{} $ называется множество всех целых чисел, попарно сравнимых между собой. Каждое из чисел класса называется вычетом по модулю $ M_{} $ по отношению ко всем остальным числам класса; поэтому класс по модулю $ M_{} $ называют еще классом вычетов по модулю $ M_{} $. Если число $ a_{} $ — какой-то из вычетов по модулю $ M_{} $, то класс вычетов, которому $ a_{} $ принадлежит, обозначают $ \overline a $. Взяв из каждого класса по одному вычету, получим полную систему вычетов по модулю $ M_{} $. Чаще всего в качестве полной системы вычетов употребляют $ 0,1,\dots,M-1 $; соответствующие классы обозначают тогда $ \overline 0, \overline 1, \dots, \overline {M-1} $: $$\overline r = \left\{r+Mt \ \big| \ t\in \mathbb Z \right\} \ .$$ (Очевидно, что $ \overline 0 $ — это множество чисел, делящихся нацело на $ M_{} $). Множество классов вычетов по модулю $ M_{} $ обозначают $ \mathbb Z_M $. Например: $$ \mathbb Z_{_7}=\{\overline 0, \overline 1, \overline 2, \overline 3, \overline 4, \overline 5, \overline 6\}=\{\overline {-3}, \overline {-2},\overline {-1}, \overline 0, \overline 1, \overline 2, \overline 3 \} \ . $$

Теорема. Любые $ M_{} $ чисел, попарно несравнимые по модулю $ M_{} $,образуют полную систему вычетов по этому модулю.

Суммой (произведением) двух классов вычетов по модулю $ M_{} $ называется класс по модулю $ M_{} $, которому принадлежит сумма (произведение) каких-либо чисел из складываемых (перемножаемых) классов.

Возникает естественный вопрос о корректности этого определения: зависят ли результаты указанных операций от выбора конкретных представителей классов?

Теорема. Сумма и произведение классов определяются единственным образом и не зависят от выбора отдельных представителей классов.

Доказательство. Действительно, если $ a_1 \in \overline a,\ b_1 \in \overline b $, то $ a_1 \equiv a \pmod{M} $, $ b_1 \equiv b \pmod{M} $ и на основании теоремы о сложении сравнений: $$a_1 +b_1 \equiv a +b \pmod{M}\ , \quad a_1 b_1 \equiv a b \pmod{M} \ .$$ Следовательно, $$\overline{a_1 +b_1} = \overline{a +b} , \quad \overline{a_1 b_1} = \overline{a b} \ .$$ Видим, что сумма (произведение) классов содержит сумму (произведение) любых чисел, взятых из этих классов. ♦

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

Пример. Для классов $ \mathbb Z_6=\{\overline 0, \overline 1, \overline 2, \overline 3, \overline 4, \overline 5\} $ имеем

$$ \overline 4 + \overline 5 = \overline 9 = \overline 3 \ , \quad \overline 4 \cdot \overline 5 = \overline{20}=\overline{2} \ . $$

Эти результаты могут быть собраны в таблицы.

Таблицы действий над классами из $ \mathbb Z_6 $: $$ \begin{array}{c} M=6 \\ \hline \\ \begin{array}{c|cccccc} \mathbb{+} & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 \\ \hline \\ \overline 0 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 \\ \overline 1 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 0 \\ \overline 2 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 0 & \overline 1 \\ \overline 3 & \overline 3 & \overline 4 & \overline 5 & \overline 0 & \overline 1 & \overline 2 \\ \overline 4 & \overline 4 & \overline 5 & \overline 0 & \overline 1 & \overline 2 & \overline 3 \\ \overline 5 & \overline 5 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 \end{array} \end{array} \qquad \begin{array}{c} M=6 \\ \hline \\ \begin{array}{c|cccccc} \mathbb{\times} & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 \\ \hline \\ \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 \\ \overline 1 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 \\ \overline 2 & \overline 0 & \overline 2 & \overline 4 & \overline 0 & \overline 2 & \overline 4 \\ \overline 3 & \overline 0 & \overline 3 & \overline 0 & \overline 3 & \overline 0 & \overline 3 \\ \overline 4 & \overline 0 & \overline 4 & \overline 2 & \overline 0 & \overline 4 & \overline 2 \\ \overline 5 & \overline 0 & \overline 5 & \overline 4 & \overline 3 & \overline 2 & \overline 1 \end{array} \end{array} $$

Таблицы действий над классами из $ \mathbb Z_7 $ $$ \begin{array}{c} M=7 \\ \hline \\ \begin{array}{c|ccccccc} \mathbb{+} & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 \\ \hline \\ \overline 0 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 \\ \overline 1 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 & \overline 0 \\ \overline 2 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 & \overline 0 & \overline 1 \\ \overline 3 & \overline 3 & \overline 4 & \overline 5 & \overline 6 & \overline 0 & \overline 1 & \overline 2 \\ \overline 4 & \overline 4 & \overline 5 & \overline 6 & \overline 0 & \overline 1 & \overline 2 & \overline 3 \\ \overline 5 & \overline 5 & \overline 6 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 \\ \overline 6 & \overline 6 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 \end{array} \end{array} \ \ \begin{array}{c} M=7 \\ \hline \\ \begin{array}{c|ccccccc} \mathbb{\times} & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 \\ \hline \\ \overline 0^{} & \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 & \overline 0 \\ \overline 1 & \overline 0 & \overline 1 & \overline 2 & \overline 3 & \overline 4 & \overline 5 & \overline 6 \\ \overline 2 & \overline 0 & \overline 2 & \overline 4 & \overline 6 & \overline 1 & \overline 3 & \overline 5 \\ \overline 3 & \overline 0 & \overline 3 & \overline 6 & \overline 2 & \overline 5 & \overline 1 & \overline 4 \\ \overline 4 & \overline 0 & \overline 4 & \overline 1 & \overline 5 & \overline 2 & \overline 6 & \overline 3 \\ \overline 5 & \overline 0 & \overline 5 & \overline 3 & \overline 1 & \overline 6 & \overline 4 & \overline 2 \\ \overline 6 & \overline 0 & \overline 6 & \overline 5 & \overline 4 & \overline 3 & \overline 2 & \overline 1 \end{array} \end{array} $$

Отметим некоторые очевидные свойства действий над классами из $ \mathbb Z_M $.

1. $ \overline a+\overline b=\overline b+\overline a $ (коммутативность сложения);

2. $ (\overline a+\overline b)+\overline c=\overline a+(\overline b+\overline c) $ (ассоциативность сложения);

3. класс $ \overline 0 $ играет роль нуля при сложении классов, именно: $ \overline a+\overline 0 =\overline a $ при $ \forall \overline a $;

4. класс $ \overline{M-a} $ играет роль класса, противоположного классу $ \overline a $, именно: $ \overline a+ \overline{M-a}=\overline 0 $;

5. $ \overline{a}(\overline{b}+\overline{c})=\overline{a}\overline{b}+ \overline{a}\overline{c} $ и $ (\overline{b}+\overline{c})\overline a= \overline b\overline a+ \overline c\overline a $ (дистрибутивность);

6. $ (\overline a\overline b)\overline c=\overline a(\overline b \overline c) $ (ассоциативность умножения);

7. $ \overline a\overline b=\overline b\overline a $ (коммутативность умножения);

8. класс $ \overline 1 $ играет роль единицы при умножении классов, именно: $ \overline a \cdot \overline{1}=\overline a $ при $ \forall \overline a $.

Возможность выполнения элементарных алгебраических операций над классами из $ \mathbb Z_M $ провоцирует желание определить более сложные операции, например, деления классов. Таблица умножения классов из $ \mathbb Z_6 $, приведенная выше, показывает, что не для всех классов это возможно: так, не существует класса $ \overline x $ такого, что $ \overline 2 \cdot \overline x = \overline 1 $. В отношении к поставленной задаче, таблица умножения классов из $ \mathbb Z_7 $ более перспективна: для любого класса $ \overline a \ne \overline 0 $ и при любом классе $ \overline b $ существует решение уравнения $ \overline a \cdot \overline x = \overline b $. При переводе последнего равенства на язык сравнений задача становится более понятной: речь идет о существовании обратного к числу $ a_{} $ относительно умножения по модулю $ M_{} $. В самом деле, если $ a\cdot y \equiv 1 \pmod M $, то класс $ \overline x=\overline{yb} $ будет решением уравнения $ \overline a \cdot \overline x = \overline b $, т.е. частным от деления класса $ \overline b $ на класс $ \overline a $. Эти рассуждения позволяют понять, почему в отношении делимости $ \mathbb Z_7 $ имел преимущество перед $ \mathbb Z_6 $: число $ 7_{} $ является простым, а по отношению к простому модулю все числа, ему не кратные, имеют обратные.

Теорема. Если $ \operatorname{HOD} (A,M)=1 $ и $ x_{} $ пробегает полную систему вычетов по модулю $ M_{} $, то $ Ax+B $, где $ B_{} $ — произвольное фиксированное целое число, тоже пробегает полную систему вычетов по модулю $ M_{} $.

Теорема. Если $ M=M_1\times \dots \times M_k $ при попарно взаимно простых числах $ M_1,\dots,M_k $, а $ B_{} $ — произвольное фиксированное целое число, то при $ x_{j} $, пробегающем полную систему вычетов по модулю $ M_{j} $ для всех $ j \in \{1,\dots, k \} $, число

$$ \frac{M}{M_1}x_1+\dots+\frac{M}{M_k}x_k + B $$ пробегает полную систему вычетов по модулю $ M_{} $.

При $ B=0 $ эта теорема представляет переформулировку китайской теоремы об остатках.

☞ ЗДЕСЬ.

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

[2]. Uspensky J.V., Heaslet M.A. Elementary Number Theory. New York. McGraw-Hill. 1941

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

[4]. Полиа Г., Сеге Г. Задачи и теоремы из анализа. Т.1. М.Наука. 1978. С.26.

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