Как найти остаток умножения

Содержание

В

☞

ПУНКТЕ обсуждается вопрос делимости нацело данного числа
$ 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_{} $?

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

В каждом разделе математики имеется исторически сложившаяся система названий
и обозначений, при этом иногда одни и те же слова или символы в разных разделах
обозначают совершенно не связанные по смыслу объекты. В частности, это
относится к слову «модуль»: если в курсе анализа или в разделе КОМПЛЕКСНЫЕ ЧИСЛА оно означает абсолютную величину числа, то в теории чисел оно закреплено за другим понятием и будет использоваться в настоящем разделе исключительно в смысле только что приведенного определения.

П

Пример.

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

Т

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

1.

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

♦

=>

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

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

=>

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

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

?

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

В дальнейшем запись
$$x= A pmod{M} $$
будем понимать в смысле, что переменной $ x_{} $ присваивается значение остатка от деления числа $ A_{} $ на $ M_{} $; таким образом, $ xin {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} .
$$

П

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

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

Решение. а) $ 1+2+3+4+7=17, 1+7=8 Rightarrow 12347 equiv 8
pmod 9 $. Аналогично устанавливается, что
$$ 54323equiv 8 pmod{9} , 670726081 equiv 1 pmod{9} .$$
Поскольку $ 8times 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 — (3times 1 +2 ) = — 4 equiv_{_7} 3 . $$

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

Т

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

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

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

• Д — число (дата);

• В — первые две цифры года (полное число столетий);

• Г — последние две цифры года;

• M $ ^{ * } $ — номер месяца в соответствии со следующим правилом

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

  • февраль считается 12-м месяцем предыдущего года,

  • март считается 1-м месяцем настоящего года: M $ ^{*}=1_{} $, и далее последовательно:

П

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

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

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

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

§

Определение даты Пасхи по году

☞

ЗДЕСЬ.

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

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

?

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

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

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

П

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

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

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

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

Ответ. $ 88 $.

?

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

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

П

Пример.

$$ A^{769}=A^{7 cdot 10^2 +6cdot 10 + 9 } = A^9cdot left( A^6 right)^{10} cdot
left(left( A^7 right)^{10} right)^{10} = A^9cdot 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}_1times 10^t+{mathfrak b}_2 times 10^{t-1} + dots +{mathfrak b}_t times
10 + {mathfrak b}_{t+1}
$$
схема вычисления $ A^B_{} pmod{M} $ организуется по тому же принципу:
$$
A^B=A^{{mathfrak b}_{t+1}}times left( A^{{mathfrak b}_{t}}times left(
A^{{mathfrak b}_{t-1}}times dots times left(A^{{mathfrak b}_{3}}
times left( A^{{mathfrak b}_{2}} times
left(A^{{mathfrak b}_{1}} right)^{10}right)^{10} right)^{10} dots right)^{10} right)^{10}
.
$$
и от числа, полученного в каждой скобке, оставляется только лишь его остаток от деления на $ M_{} $.
Тогда в ходе вычислений не возникнут числа, бóльшие $ M^{10} $, и, если
имеющиеся в нашем распоряжении вычислительные средства позволяют
оперировать с такими числами, мы решим поставленную задачу.

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

Алгоритм «квадрирования-умножения» вычисления

³⁾
$ A^B pmod{M} $

1.

Число $ B_{} $ переводится в двоичную систему счисления:
$$B={mathfrak b}_1times 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.
$$
для $ jin{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^2times 56} &
{scriptstyle 315^2 times 56} & {scriptstyle 224^2times 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}
$$

§

Применение алгоритма

☞

КРИПТОГРАФИЯ.

Возьмем произвольное число $ Ane 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, 0le 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_{jge 0} (-1)^j {mathfrak a}_{s+(2-k)-3j}
quad npu quad kin{1,2,3} , $$
и суммирование идет по всем тем $ j_{} $, которые сохраняют положительные значения
индексов.

Т

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

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

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

П

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

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

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

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

?

Упростить критерии делимости на $ 13 $ и $ 37 $, приведенные

☞

ЗДЕСЬ

Т

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

Доказательство. Рассмотрим арифметическую прогрессию
$$
A, 2A,dots, jA,dots, kA, dots, (p-1)A
$$
и найдем остатки ее членов при делении на $ p_{} $:
$$r_1,r_2,dots,r_j,dots, r_k, dots, r_{p-1} , $$
Утверждается, что все эти остатки отличны от нуля и все различны.
Действительно, если $ jA $
делится на простое $ p_{} $, то по теореме

2

, приведенной

☞

ЗДЕСЬ, либо $ j_{} $ делится
на $ p_{} $, либо $ A_{} $ делится на $ p_{} $. Последнее невозможно по условию теоремы,
а первое — потому что $ j<p $. Если бы числа $ jA $ и $ kA $ имели одинаковый
остаток при делении на $ p_{} $, то их разность $ (k-j)A $ должна была делиться на $ p_{} $.
Это невозможно, поскольку ни $ A_{} $, ни $ (k-j) $ не делятся на $ p_{} $.

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

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

• при $ A=10 $ — $ 3,6,2,5,1,4 $

и т.д. Перемножив сравнения
$$ Acdot 1 equiv_{_{p}} r_1, Acdot 2 equiv_{_{p}} r_2,dots, Acdot (p-1)equiv_{_{p}} r_{p-1} , $$
получим:
$$(p-1)!, A^{p-1}equiv_{_{p}}r_1 r_2times dots times r_{p-1}=(p-1)! .$$
Иначе говоря, $ (p-1)!, left( A^{p-1}-1 right) $ делится на простое $ p_{} $.
Поскольку $ (p-1)! $ не делится на $ p_{} $, то, по теореме

3

, приведенной

☞

ЗДЕСЬ,
число $ A^{p-1}-1 $ должно делиться на $ p_{} $.

♦

=>

Если $ p_{} $ простое, то
$$
A^{p} equiv A pmod{p} quad npu quad forall Ain 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} $, т.е. существует $ qin 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
jin {1,dots, {mathfrak r}} .$$
Тогда справедливы (сравнение можно возводить в степень, см. теорему

☞

ЗДЕСЬ ) и сравнения
$$
A^{phi(M)} equiv 1 pmod{p_j^{{mathfrak m}_j}} quad npu quad forall
jin {1,dots, {mathfrak r}} , ,
$$
поскольку $ phi(M) $ делится нацело на $ p_j^{{mathfrak m}_j-1}(p_j-1) $.
Теорема $ 4 $, приведенная

☞

ЗДЕСЬ, позволяет перемножить модули:
$$A^{phi(M)} equiv 1 pmod{prod_{j=1}^{mathfrak r} p_j^{{mathfrak m}_j}}
quad iff quad A^{phi(M)} equiv 1 pmod{M} .$$

♦

?

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

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

☞

ПУНКТЕ.

Правило упрощения при вычислении

$ A^B pmod{M} $

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

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

П

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

Решение. Действуем по правилу упрощения:
$$229384527equiv 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=101times 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 $.

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

б) Здесь $ B=9^9=9times 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^4cdot 3^3 cdot 5 cdot 7^2)= operatorname{HOK} left(2^3 ,,
2cdot 3^2,, 4,, 7cdot 6right)=2^3cdot 3^2 cdot 7 = 504 $$
при $ phi(105840)= 24192 $ ;
$$
L(10291)=L(41cdot 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
jin {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 $ при $ nin mathbb N $; оно имеет решение в случае $ n=2_{} $: $ x=3,y=4,z=5 $.

Т

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

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

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

П

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

б)

А

должен получить $ 25 $ руб. с

Б

; но у

Б

только трехрублевые, а у

А

десятирублевые билеты. Как разочтутся

А

и

Б

?

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

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

♦

П

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

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

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

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

В дальнейшем, говоря о числе решений сравнения $ 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_{} $ решений.

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

Если $ d = operatorname{HOD} (A,M)=1 $, то фактически повторим начало доказательства теоремы Ферма. Каждое из чисел арифметической прогрессии
$$
A, 2,A,dots, j,A,dots, k,A, dots, (M-1)A
$$
дает при делении на $ M_{} $ ненулевой остаток, и
при $ kne 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 } $ такое, что $ xAequiv B pmod{M} $.

Пусть теперь $ d=operatorname{HOD} (A,M)>1 $ и $ B_{} $ не делится на $ d_{} $. Если существует решение $ x=x_0in 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_1equiv 0 pmod{M_1} $ тривиален.
Если же $ B_1notequiv 0 pmod{M_1} $, то, по доказанному выше, такое
сравнение имеет
единственное решение по модулю $ M_1 $: существует $ x_1in {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 $
при $ kin {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_1cdot A_2 $$
разрешимо в целых числах.

Т

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

$$ A_1x+A_2y=B , mbox{ где } {A_1,A_2,B} subset mathbb N, operatorname{HOD}(A_1,A_2)=1 , ,$$
равно
$$ leftlfloor frac{B}{A_1A_2} rightrfloor qquad mbox{ или } qquad leftlfloor frac{B}{A_1A_2} rightrfloor +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| , kin {0,1,dots,d-1 } right}
$$
содержит в себе решения сравнения $ Ax_{} equiv B pmod{M} $, и все эти решения различны.

♦

П

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

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

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

П

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

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

♦

П

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

Решение. В схеме алгоритма Евклида нахождения $ operatorname{HOD}(2340,9903) $
имеем:
$$k=5, q_1=4, q_2=4, q_3=3, q_4=4, q_5=3, d=3 .$$
Вычисляем континуанту:
$$
begin{array}{|c|c|c|c|c|c|c|}
hline
j & 0 & 1 & 2 & 3 & 4 & 5 \
hline
q_j & — & 4 & 4 & 3 & 4 & 3\
hline
K_j(q_1,q_2,dots,q_j) & 1 & 4 & 17 & 55 & 237 & 766 \
hline
end{array}
$$
По

☞

формуле получаем: $ u=u_5=(-1)^{5}K_5(q_1,q_2,dots,q_5) =-766 $.
Множество решений сравнения имеет вид
$$
begin{array}{llll}
bigg{-766 cdot displaystyle frac{72}{3} equiv &1422 pmod{9903} , ; & & \
&1422 + displaystyle frac{9903}{3} equiv & 4723 pmod{9903} , ; & \
& & 4723 + displaystyle frac{9903}{3} equiv 8024 pmod{9903} bigg} & .
end{array}
$$

♦

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

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

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

Алгоритм нахождения числа, обратного

$ A_{} $

относительно умножения по модулю

$ M_{} $

1.

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

2.

по

☞

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

3.

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

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

П

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

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

Ответ. $ 252 $. Проверка. $ 252times 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 mathbb Z . $$
Предположим, что хотя бы один коэффициент $ A_{j} $ отличен от нуля.

Т

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

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

♦

П

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

Решение. Выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте:
$$ z=frac{58-10,x-9,y}{7}=8-x-y+frac{2-3,x-2,y}{7} . $$
Поскольку, по предположению, все неизвестные должны быть числами целыми, то положим
$$frac{2-3,x-2,y}{7}=u_1 quad mbox{ или } quad 2-3,x-2,y=7, u_1 . $$
Теперь выразим из этого уравнения неизвестную при минимальном (по абсолютной величине) коэффициенте:
$$ y = frac{2-3,x-7, u_1}{2}= 1- x-3, u_1- frac{x+u_1}{2} . $$
Положим
$$ frac{x+u_1}{2}=u_2 quad mbox{ или } quad x=2,u_2-u_1 . $$
Подставим найденное выражение в предыдущее выражение для $ y_{} $:
$$ y=1-x-3,u_1-u_2=1-(2,u_2-u_1)-3,u_1-u_2=1-2,u_1-3,u_2 ; $$
и, окончательно, в выражение для $ z_{} $:
$$ z=8-(2,u_2-u_1)-(1-2,u_1-3,u_2)+u_1=7+4,u_1+u_2 . $$
Таким образом, значения неизвестных $ x,y,z $ полностью определяются формулами
$$ x=-u_1+2,u_2, y=1-2,u_1-3,u_2, z=7+4,u_1+u_2 quad npu quad {u_1,u_2} subset mathbb Z . $$
Если поставить дополнительное требование положительности решений, то получаем условия на параметры $ u_1,u_2 $ в виде неравенств
$$ -u_1+2,u_2>0 , 1-2,u_1-3,u_2 > 0, 7+4,u_1+u_2 > 0 . $$
Разрешим каждое из этих неравенств относительно $ u_{1} $:
$$ u_1<2,u_2, u_1 < frac{1-3,u_2}{2}, u_1>frac{-7-u_2}{4} . $$
Объединяя первое неравенство с третьим и второе неравенство с третьим, получаем ограничения на $ u_{2} $:
$$ frac{-7-u_2}{4}< 2,u_2, frac{-7-u_2}{4}< frac{1-3,u_2}{2} , $$
откуда:
$$ -7/9 < u_2 < 9/5 . $$
Поскольку, по предположению, $ u_{2} $ — целое, то $ u_2in {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_1leftarrow1, 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_1in mathbb Z $ удовлетворяет этой системе, то
ей, очевидно, удовлетворяет и любое число вида $ x_1+tcdot
operatorname{HOK}(M_1,dots,M_k) $ при $ t in mathbb Z $, иными словами,
любое число, сравнимое с $ x_{1} $ по модулю $ operatorname{HOK}(M_1,dots,M_k) $:
$$ xequiv 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 $ для каждого $ jin {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 $, обозначающем число, обратное числу $ Mbig/ 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_2times 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_2times 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_0in 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_0in{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} $.

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

Ответ. $ xin {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_0ne 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_jne lambda_1 $ — какое-то другое решение сравнения $ f(x) equiv 0 pmod{p} $, то оно должно удовлетворять сравнению
$ f_1(x) equiv 0 pmod{p} $, которое по индуктивному предположению
не может иметь более $ n_{}-1 $ решений. Следовательно, число решений
сравнения $ f(x) equiv 0 pmod{p} $ не превышает $ n_{} $.

♦

Т

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

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

Доказательство. Рассмотрим полином
$$g(x) = f(x)- (x-lambda_1)times dots times (x-lambda_n) . $$
Очевидно, что
$$m = deg g(x) le n-1 mbox{ и что } g(lambda_1) equiv 0 pmod{p},
dots , g(lambda_n) equiv 0 pmod{p} .
$$
Покажем, что все коэффициенты полинома
$$g(x)=b_0x^m+b_1x^{m-1}+ dots + b_m $$
делятся на $ p_{} $. Действительно, если $ b_0not 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_{} $. Требуемое сравнение выполняется тогда и только тогда, когда выполняется линейное сравнение
$$
ncdot 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}
$$
получим линейное сравнение $ ncdot 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 $
снова обращаемся к таблице.

Ответ. $ xin {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} $ выполняется. Докажем, что линейное
сравнение
$ ncdot 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_{} $,
мы — на основании теоремы Ферма — получаем единственное
решение $ xin {0,1,dots,p-1} $. Та же теорема Ферма позволит найти и
представление этого решения.

Алгоритм решения сравнения

$ x^n equiv B pmod{p} $

1.

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

2.

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

В самом деле, поскольку $ operatorname{HOD}(n,p-1)=1 $,
то, на основании теоремы о существовании решения линейного сравнения, сравнение
$ ncdot z equiv 1 pmod{p-1} $
однозначно разрешимо относительно $ z_{} $. Имеем
$$ ncdot z = 1+t(p-1)
npu tin mathbb Z , $$
и
$$left( B^z right)^n = B^{1+t(p-1)} =Bcdot 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 $, то решение сравнения
единственно при любых $ Bin {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| tin 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 boverline a+ overline coverline a $ (дистрибутивность);

6.

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

7.

$ overline aoverline b=overline boverline 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_{} $. В самом деле, если $ acdot 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_1times 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.

Время на прочтение
6 мин

Количество просмотров 67K

Математика • 7 класс

11

• Пусть число 𝑎1 при делении на 𝑏 даёт остаток 𝑟1, а число 𝑎2 при делении на 𝑏 даёт остаток 𝑟2: 𝑎1=𝑏ост 𝑟1, 𝑎2=𝑏ост 𝑟2.

  Тогда число 𝑎1·𝑎2 при делении на 𝑏 даёт остаток 𝑟1·𝑟2.

  В случае если 𝑟1⋅𝑟2>𝑏, необходимо найти остаток от деления 𝑟1⋅𝑟2 на 𝑏.

• Например, 100 = 7 (ост 2), 90 = 7 (ост 6).

  Тогда 9000 = 7 (ост 12), но так как остаток должен быть всегда меньше делителя, разделим 12 на 7, получаем 9000 = 7 (ост 5).

Было полезно?