Как найти остаток от деления по модулю

Содержание

В

☞

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

• 

    Quotient (q) and

    remainder (r) as functions of dividend (a), using truncated division

  Many implementations use truncated division, for which the quotient is defined by

  

  where [] is the integral part function (rounding toward zero), i.e. the truncation to zero significant digits.
  Thus according to equation (1), the remainder has the same sign as the dividend:

  

• 

  Quotient and remainder using floored division

  Donald Knuth^[3] promotes floored division, for which the quotient is defined by

  

  where ⌊⌋ is the floor function (rounding down).
  Thus according to equation (1), the remainder has the same sign as the divisor:

  

• 

  Quotient and remainder using Euclidean division

  Raymond T. Boute^[4] promotes Euclidean division, for which the quotient is defined by

  

  where sgn is the sign function, ⌊⌋ is the floor function (rounding down), and ⌈⌉ is the ceiling function (rounding up).
  Thus according to equation (1), the remainder is non negative:

  

• 

  Quotient and remainder using rounded division

  Common Lisp and IEEE 754 use rounded division, for which the quotient is defined by

  

  where round is the round function (rounding half to even).
  Thus according to equation (1), the remainder falls between and , and its sign depends on which side of zero it falls to be within these boundaries:

  

• 

  Quotient and remainder using ceiling division

  Common Lisp also uses ceiling division, for which the quotient is defined by

  

  where ⌈⌉ is the ceiling function (rounding up).
  Thus according to equation (1), the remainder has the opposite sign of that of the divisor:

  

bool is_odd(int n) {
    return n % 2 == 1;
}

bool is_odd(int n) {
    return n % 2 != 0;
}

bool is_odd(int n) {
    return n % 2 == 1 || n % 2 == -1;
}

bool is_odd(int n) {
    return n % 2;
}

/* Euclidean and Floored divmod, in the style of C's ldiv() */
typedef struct {
  /* This structure is part of the C stdlib.h, but is reproduced here for clarity */
  long int quot;
  long int rem;
} ldiv_t;

/* Euclidean division */
inline ldiv_t ldivE(long numer, long denom) {
  /* The C99 and C++11 languages define both of these as truncating. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0) {
      q = q - 1;
      r = r + denom;
    } else {
      q = q + 1;
      r = r - denom;
    }
  }
  return (ldiv_t){.quot = q, .rem = r};
}

/* Floored division */
inline ldiv_t ldivF(long numer, long denom) {
  long q = numer / denom;
  long r = numer % denom;
  if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) {
    q = q - 1;
    r = r + denom;
  }
  return (ldiv_t){.quot = q, .rem = r};
}

1. ^ Mathematically, these two choices are but two of the infinite number of choices available for the inequality satisfied by a remainder.
2. ^ ^{a b} Argument order reverses, i.e., α|ω computes , the remainder when dividing ω by α.
3. ^ C99 and C++11 define the behavior of % to be truncated.^[9] The standards before then leave the behavior implementation-defined.^[10]
4. ^ As implemented in ACUCOBOL, Micro Focus COBOL, and possible others.
5. ^ Divisor must be positive, otherwise undefined.
6. ^ As discussed by Boute, ISO Pascal’s definitions of div and mod do not obey the Division Identity of D = d · (D / d) + D % d, and are thus fundamentally broken.
7. ^ Perl usually uses arithmetic modulo operator that is machine-independent. For examples and exceptions, see the Perl documentation on multiplicative operators.^[38]

1. ^ Weisstein, Eric W. «Congruence». mathworld.wolfram.com. Retrieved 2020-08-27.
2. ^ Caldwell, Chris. «residue». Prime Glossary. Retrieved August 27, 2020.
3. ^ Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley.
4. ^ Boute, Raymond T. (April 1992). «The Euclidean definition of the functions div and mod». ACM Transactions on Programming Languages and Systems. ACM Press (New York, NY, USA). 14 (2): 127–144. doi:10.1145/128861.128862. hdl:1854/LU-314490. S2CID 8321674.
5. ^ ^{a b} Leijen, Daan (December 3, 2001). «Division and Modulus for Computer Scientists» (PDF). Retrieved 2014-12-25.
6. ^ Peterson, Doctor (5 July 2001). «Mod Function and Negative Numbers». Math Forum — Ask Dr. Math. Archived from the original on 2019-10-22. Retrieved 22 October 2019.
7. ^ Horvath, Adam (July 5, 2012). «Faster division and modulo operation — the power of two».
8. ^ ^{a b} «ISO/IEC 8652:2012 — Information technology — Programming languages — Ada». ISO, IEC. 2012. sec. 4.5.5 Multiplying Operators.
9. ^ «C99 specification (ISO/IEC 9899:TC2)» (PDF). 2005-05-06. sec. 6.5.5 Multiplicative operators. Retrieved 16 August 2018.
10. ^ «ISO/IEC 14882:2003: Programming languages – C++». International Organization for Standardization (ISO), International Electrotechnical Commission (IEC). 2003. sec. 5.6.4. the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined
11. ^ «ISO/IEC 9899:1990: Programming languages – C». ISO, IEC. 1990. sec. 7.5.6.4. The fmod function returns the value x — i * y, for some integer i such that, if y is nonzero, the result has the same sign as x and magnitude less than the magnitude of y.
12. ^ ^{a b} dotnet-bot. «Math.IEEERemainder(Double, Double) Method (System)». learn.microsoft.com. Retrieved 2022-10-04.
13. ^ «clojure.core — Clojure v1.10.3 API documentation». clojure.github.io. Retrieved 2022-03-16.
14. ^ «clojure.core — Clojure v1.10.3 API documentation». clojure.github.io. Retrieved 2022-03-16.
15. ^ CoffeeScript operators
16. ^ «Expressions — D Programming Language». dlang.org. Retrieved 2021-06-01.
17. ^ «operator % method — num class — dart:core library — Dart API». api.dart.dev. Retrieved 2021-06-01.
18. ^ «remainder method — num class — dart:core library — Dart API». api.dart.dev. Retrieved 2021-06-01.
19. ^ «Kernel — Elixir v1.11.3». hexdocs.pm. Retrieved 2021-01-28.
20. ^ «Integer — Elixir v1.11.3». hexdocs.pm. Retrieved 2021-01-28.
21. ^ «Basics — core 1.0.5». package.elm-lang.org. Retrieved 2022-03-16.
22. ^ «Basics — core 1.0.5». package.elm-lang.org. Retrieved 2022-03-16.
23. ^ «Erlang — math». erlang.org. Retrieved 2021-06-01.
24. ^ «GLSL Language Specification, Version 4.50.7» (PDF). section 5.9 Expressions. If both operands are non-negative, then the remainder is non-negative. Results are undefined if one or both operands are negative.
25. ^ «GLSL Language Specification, Version 4.50.7» (PDF). section 8.3 Common Functions.
26. ^ «The Go Programming Language Specification — The Go Programming Language». go.dev. Retrieved 2022-02-28.
27. ^ «math package — math — pkg.go.dev». pkg.go.dev. Retrieved 2022-02-28.
28. ^ «big package — math/big — pkg.go.dev». pkg.go.dev. Retrieved 2022-02-28.
29. ^ ^{a b} «6 Predefined Types and Classes». www.haskell.org. Retrieved 2022-05-22.
30. ^ «Operators». Microsoft. Retrieved 2021-07-19. The % operator is defined only in cases where either both sides are positive or both sides are negative. Unlike C, it also operates on floating-point data types, as well as integers.
31. ^ «Mathematics · The Julia Language». docs.julialang.org. Retrieved 2021-11-20.
32. ^ «Mathematics · The Julia Language». docs.julialang.org. Retrieved 2021-11-20.
33. ^ «rem — Kotlin Programming Language». Kotlin. Retrieved 2021-05-05.
34. ^ «mod — Kotlin Programming Language». Kotlin. Retrieved 2021-05-05.
35. ^ «Chapter 3: The NASM Language». NASM — The Netwide Assembler version 2.15.05.
36. ^ «OCaml library : Stdlib». ocaml.org. Retrieved 2022-02-19.
37. ^ «OCaml library : Stdlib». ocaml.org. Retrieved 2022-02-19.
38. ^ Perl documentation
39. ^ «PHP: Arithmetic Operators — Manual». www.php.net. Retrieved 2021-11-20.
40. ^ «PHP: fmod — Manual». www.php.net. Retrieved 2021-11-20.
41. ^ «EuclideanRing».
42. ^ QuantumWriter. «Expressions». docs.microsoft.com. Retrieved 2018-07-11.
43. ^ «R: Arithmetic Operators». search.r-project.org. Retrieved 2022-12-24.
44. ^ «F32 — Rust».
45. ^ ^{a b} r6rs.org
46. ^ «Shell Command Language». pubs.opengroup.org. Retrieved 2021-02-05.
47. ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
48. ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
49. ^ «Apple Developer Documentation». developer.apple.com. Retrieved 2021-11-20.
50. ^ «Numerics — WebAssembly 1.1 (Draft 2022-03-02)». webassembly.github.io. Retrieved 2022-03-16.
51. ^ «Numerics — WebAssembly 1.1 (Draft 2022-03-02)». webassembly.github.io. Retrieved 2022-03-16.
52. ^ «Zig Documentation». Zig Programming Language. Retrieved 2022-12-18.
53. ^ ^{a b} «Mod». Wolfram Language & System Documentation Center. Wolfram Research. 2020. Retrieved April 8, 2020.

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

Говоря о теории чисел, мы будем работать с остатками.

Определение:
Остаток от деления $a$ на $b$ —это такое число $0 le c < b$, что $a = bq + c$ для некоторого $q$.

Выражение $a equiv b pmod m$ означает, что остатки от деления $a$ на $m$ и $b$ на $m$ равны. Это выражение читается как «$a$ сравнимо $b$ по модулю $m$».

Еще это можно опрделить так: $a$ сравнимо c $b$ по модулю $m$, если $(a — b)$ делится на $m$.

Все целые числа можно разделить на классы эквивалентности — два числа лежат в одном классе, если они сравнимы по модулю $m$. Говорят, что мы работаем в «кольце остатков по модулю $m$», и в нем ровно $m$ элементов: $0, 1, 2, cdots, m-1$.

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

Некоторые свойства:

1. $a equiv b$, $c equiv d Rightarrow a pm c equiv b pm d mod m$
2. $a equiv b$, $c equiv d Rightarrow ac equiv bd mod m$
3. $aequiv b mod m Rightarrow a^n equiv b^n mod m$

Деление по модулю

Поделить одно число $a$ на другое число $b$ в кольце вычетов по модулю $m$ — значит найти такое число $c$, что $cb equiv a mod m$. Эта задача уже сложнее, чем сложение и умножение по модулю. Она сводится у нахождению так называемого обратного по модулю к числу $b$.

Обратным к числу $a$ по модулю $m$ называют такое число $a^{-1}$, что $acdot a^{-1} equiv 1 mod m$.

В том случае, если модуль простой (является простым числом), найти обратный всегда можно, только если исходное число не делится на модуль $m$. Если же модуль — составное число, то обратный элемент к $a$ существует только тогда, когда $(a, m) = 1$, то есть когда $a$ и $m$ взаимнопросты.

Если мы нашла обратное к $b$ число, то $ab^{-1} equiv bcb^{-1} equiv c mod m$. То есть умножив $a$ на обратное к $b$ число, мы выполнили деление и нашли искомое $c$.

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

Код на C++

const int mod = 1e9 + 7; // Поменяйте на тот, который в вашей задаче

template<typename T>
T add(T x) {
    return x;
}

template<typename T, typename... Ts>
T add(T x, Ts... y) {
    T res = x + add(y...);
    if (res >= mod)
        res -= mod;
    return res;
}
// Конструкция выше позволяет писать add(x, y, z, t, ...) с любым количеством аргументов 

template<typename T, typename... Ts>
T sub(T x, Ts... y) {
    return add(x, mod - add(y...));
}

// udd это add, записывающий результат сложения в первый аргумент. 
// Старое значение первого аргумента в сумме участвует
template<typename T, typename... Ts>
void udd(T &x, Ts... y) {
    x = add(x, y...);
}


template<typename T>
T mul(T x) {
    return x;
}

template<typename T, typename... Ts>
T mul(T x, Ts... y) {
    return (x * 1ll * mul(y...)) % mod;
}

template<typename T, typename... Ts>
void uul(T &x, Ts... y) {
    x = mul(x, y...);
}

int bin(int a, ll deg) {
    int r = 1;
    while (deg) {
        if (deg & 1)
            uul(r, a);
        deg >>= 1;
        uul(a, a);
    }
    return r;
}

// обратный по __простому__ модулю
int inv(int x) {
    assert(x);
    return bin(x, mod - 2);
}

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko

Автор конспекта: Саша Гришутин

По всем вопросам пишите в telegram @rationalex