Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом
((:numtheory НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ)).
==Модулярная арифметика==
В
☞
((:numtheory#признаки_делимости ПУНКТЕ)) обсуждается вопрос делимости нацело данного числа
$ 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 $
(см. определение
☞
((:numtheory#делимость_с_остатком ЗДЕСЬ)) ). Таким образом, множество $ \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_{} $".
В каждом разделе математики имеется исторически сложившаяся система названий
и обозначений, при этом иногда одни и те же слова или символы в разных разделах
обозначают совершенно не связанные по смыслу объекты. В частности, это
относится к слову "модуль": если в курсе анализа или в разделе ((:complex_num#тригонометрическая_форма_комплексного_числа КОМПЛЕКСНЫЕ ЧИСЛА)) оно означает абсолютную величину числа, то в теории чисел оно закреплено за другим понятием и будет использоваться в настоящем разделе исключительно в смысле только что приведенного определения.
!!П!! **Пример.**
$$ 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) $ --- произвольный ((:polynomial полином)) с целыми коэффициентами.
Последние результаты объясняют, почему для записи сравнений выбран знак $ {\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} $, т.е. результат операции неверен.
♦
Подчеркнем, что теорема дает лишь __необходимое__ условие правильности
проведенной операции: так, например, хотя результат операции
$$ 123811566370524395\ \colon \ 689603=179540353474 $$
и выдерживает проверку правильности "отбрасыванием девяток", тем не менее, он неверен.
Еще одна историческая задача --- о **вечном календаре** --- имеет отношение к модулю $ M=7 $:
**Задача.** Определить день недели по дате.
Задача может быть решена буквально "на пальцах", если мы обладаем календарем хотя бы за какой-то год.
{{ kalendar.gif|}}
!!П!! **Пример.** Установить день недели для 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])). //День недели по дате устанавливается следующей// **формулой Целлера**[[В литературе ее почтительно называют //формулой преподобного Целлера// (Rev. Zeller); вероятно, священнослужитель...]]
Д + $ \lfloor 2.6_{} \times $ M $ ^{*} - 0.2_{} \rfloor + $ Г $ + \lfloor $ Г/4 $ \rfloor +
\lfloor $ В/4 $ \rfloor - 2_{}\times $ В $ \pmod 7_{} $
//Здесь// $ \lfloor_{} \mbox{ } \rfloor_{} $ //означает ((algebra2:notations#целая_часть_числа целую часть числа)), а полученный результат следует интерпретировать//: \\
| 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 \ . $$
**Ответ.** Среда.
!!§!! ''Определение даты Пасхи по году''
☞
((:modular:easter ЗДЕСЬ)).
=== Вычисление остатков степенных выражений ==
Перейдем теперь от задач, представляющих, скорее, исторический интерес, к задачам, порожденным эпохой компьютеров.
**Задача.** Вычислить $ 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}
\ .
$$
И тут нам улыбается удача :-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 $((:modular:vspom1 .))
Унифицируем теперь вычисление $ 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_{} $.
----
Алгоритм "квадрирования-умножения" вычисления
[[Square-and-multiply algorithm]]
$ 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}
$$
!!§!! Применение алгоритма
☞
((:crypto#алгоритм_rsa КРИПТОГРАФИЯ)).
=== Теоремы Ферма и Эйлера ==
Возьмем произвольное число $ 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}
$$
В последнем случае мы отступили от введенного нами же ((:numtheory#делимость_с_остатком правила вычисления остатков)) от деления чисел, именно: остаток всегда считается неотрицательным числом. "Честным" решением является
$$
\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 $, приведенные
☞
((:numtheory#признаки_делимости ЗДЕСЬ))
====Теорема Ферма==
!!Т!! **Теорема [Ферма (малая)].** //Если// $ 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
, приведенной
☞
((:numtheory#каноническое_разложение_числа ЗДЕСЬ)), либо $ j_{} $ делится
на $ p_{} $, либо $ A_{} $ делится на $ p_{} $. Последнее невозможно по условию теоремы,
а первое --- потому что $ j
3