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


§

Для понимания материалов этого раздела неплохо было бы просмотреть материалы раздела НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ.


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

В ПУНКТЕ обсуждается вопрос делимости нацело данного числа 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 или \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) — произвольный полином с целыми коэффициентами.

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

?

Можно ли сравнение сокращать на общий множитель:

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}, т.е. результат операции неверен.

§

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

123811566370524395\ \colon \ 689603=179540353474

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

Еще одна историческая задача — о вечном календаре — имеет отношение к модулю 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]. День недели по дате устанавливается следующей формулой Целлера1)

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

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

1 2 3 4 5 6 0
пн. вт. ср. чт. пт. сб. вс.
  • Д - число (дата);
  • В - первые две цифры года (полное число столетий);
  • Г - последние две цифры года;
  • M ^{ * } - номер месяца в соответствии со следующим правилом
    • январь считается 11-м месяцем предыдущего года (т.е. для января 1987_{} года следует положить Г = 86_{}, M ^{*}=11_{}),
    • февраль считается 12-м месяцем предыдущего года,
    • март считается 1-м месяцем настоящего года: M ^{*}=1_{}, и далее последовательно:
март апрель май июнь июль август сентябрь октябрь ноябрь декабрь
M ^{ * } 1 2 3 4 5 6 7 8 9 10
П

Пример. Установить день недели для 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} на 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} \ .

И тут нам улыбается удача :-P : 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}, и, если имеющиеся в нашем распоряжении вычислительные средства позволяют оперировать с такими числами, мы решим поставленную задачу.

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


Алгоритм "квадрирования-умножения" вычисления 3) 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}

\{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}
П

Пример. Найти все значения неизвестной цифры \mathfrak{x}, при которых число \underline{645763\mathfrak{x}1789} делится на 7_{}.

Решение. Имеем:

A_1=9-1+6-4,\ A_2=8-\mathfrak{x} +7-6=9-\mathfrak{x},\ A_3=7-3+5=9 \ .

Следовательно,

B=A_1+3\,A_2+2\,A_3 = 55 -3\,\mathfrak{x} \equiv 6 -3\, \mathfrak{x} \pmod{7}

и последнее число делится на 7_{} только при \mathfrak{x}=2 и \mathfrak{x}=9.

Ответ. \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_{}, то по теореме либо 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=103,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_{}.

§

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

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

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







=>

Если 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} \ npu \ \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_{} снова предполагаются неотрицательными5). Выделим ту неизвестную, коэффициент при которой меньше, чем у другой по абсолютной величине и выразим эту неизвестную в виде функции другой:

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.

!

В дальнейшем, говоря о числе решений сравнения Ax_{} \equiv B \pmod{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, где \{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 или \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}

?

Решить сравнение

(M-1)x \equiv \frac{M-1}{2} \pmod{M}

при нечетном M>2.

Нас теперь будет интересовать один частный случай, при котором решение сравнения будет единственно во множестве \{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.

§

В частном случае простого модуля M=p имеем: при любом числе A_{} из множества \{1,\, 2,\, \dots,\, p-1\} решение сравнения A\, x \equiv 1 \pmod{p} всегда существует, и оно единственно среди чисел того же ряда. Этот результат позволяет вывести критерий простоты числа, известный как критерий Вильсона.

Общий случай линейного уравнения

Результаты предыдущих пунктов позволили полностью исследовать задачу решения линейного уравнения вида 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 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 или \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 или \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 \ .

?

Найти двузначные натуральные числа, удовлетворяющие уравнению 17\, x+ 20\, y+45\, z =4111 .

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

Более общей является задача решения системы сравнений

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 и что \ 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}
§

Начинающему изучать классы вычетов трудно преодолеть психологический барьер, заключающийся в применении обычных алгебраических операций над числами к бесконечным множествам. Для привыкания удобно первое время «переводить» результаты действий над классами по модулю M_{} в привычный язык остатков от деления на M_{}. Так, например, результат действия \overline 3 \cdot \overline 5 = \overline 1 над классами из \mathbb Z_7 вовсе не означает, что 1_{} можно представить в виде произведения двух чисел, дающих при делении на 7_{} остатки 3_{} и 5_{}. Этот результат должен интерпретироваться так: «если произвольное число, дающее 3 в остатке при делении на 7, умножить на произвольное число, дающее 5 в остатке при делении на 7, то результатом умножения будет некоторое число, которое при делении на 7 дает 1 в остатке».

Отметим некоторые очевидные свойства действий над классами из \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.

1) В литературе ее почтительно называют формулой преподобного Целлера (Rev. Zeller); вероятно, священнослужитель…
2) В смысле размеров промежуточных результатов!
3) Square-and-multiply algorithm
4) Pigeonhole principle (англ.) — принцип голубиных ящиков.
5) Знак минус в левой части итерпретируется как сдача, которую А должен отдать Б .

2017/01/19 11:30