Сравнения по модулю и арифметика остатков

27

1. ДЕЛЕНИЕ С ОСТАТКОМ

Вы собрались ехать на метро. Стоимость проезда — 5 копеек; контроль при входе автоматический: в ответствие автомата нужно бросить пятак, а если у вас его нет, то обменять в разменной кассе ваши деньги на пятко-пеечные монеты.

Предположим, что у вас есть монета в 20 копеек. Сколько пятаков вы можете получить в кассе? Всякий скажет, что 4.

Ну, а если у вас есть 19 копеек без пятаков? Ясно, что вы можете получить всего 3 пятака и еще 4 копейки сдачи. Запишем так: $19 = 3 \cdot 5 + 4$. Это — запись деления числа 19 на 5 с остатком.

Воображим теперь, что существует монеты любого достоинства, то есть 1 копейка, 2 копейки, 3 копейки, 4 копейки и т. д., и вам нужно разменять $a$-копеечную монету так, чтобы получить наиболее число $b$-копеечных. Спрашиваем, как это сделать?

Ясно, что если вам научут отчитывать $b$-копеечные монеты:

$b, 2b, 3b$ и т. д.,

то в конце концов hastanet момент, когда, получив несколько $b$-копеечных монет, вы уже не сможете получить следующее; вам даут какое-то

28

число $b$-копеечных монет и еще какой-то остаток, скажем $r$ копеек. При этом $r$ будет непреемно меньше, чем $b$ (не исключано, конечно, что $r = 0$).

Результат такого размена можно записать следующим образом:

$$a = kb + r, \quad r < b.$$

В этой формуле числа $a, b$ натуральные, то есть целые положительные, а $k$ и $r$ — целые неотрицательные.

О пределене деления с остатком. Разделить целое число $a$ на натуральное число $b$ — значит представить $a$ в виде

$$a = kb + r,$$

где $k, r$ — целые числа, $b > r \geq 0$.

При этом число $k$ называется частным, а $r$ — остатком от деления $a$ на $b$.

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

$$\frac{175}{14} = \frac{14}{12};$$

$$\frac{28}{7}$$

здесь сразу же находится остаток и частное: $175 = 12 \cdot 14 + 7$.

Заметим, что в данном определении мы не требуем, чтобы $a$ было меньше $b$, и даже не требуем, чтобы $a$ было положительным. Можно, например, разделить

a) 5 на 7: $5 = 0 \cdot 7 + 5 \quad (k = 0, r = 5)$,

b) -13 на 7: $-13 = (-2) \cdot 7 + 1 \quad (k = -2, r = 1)$,

b) -224 на 7: $-224 = (-32) \cdot 7 \quad (k = -32, r = 0)$.

В том случае, если остаток равен нулю, то есть $a = kb$, говоря, что $a$ делится на $b$.

Ясно, что если числа $a$ и $b$ делятся на число $c$, то и $a+b$ и $a-b$, а также $ka, kb$ (к— натуральное) делятся на $c$.

2. СРАВНЕНИЕ ЦЕЛЫХ ЧИСЕЛ ПО МОДУЛЮ

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

Пример первый. Псезид идет из города $A$ в город $B$ 78 часов. Он выходит из $A$ в 10 часов утра. В котором часу поедет в $B$?

Вспомним, что в сутках 24 часа, поделим число 78 на 24:

$$78 = 3 \cdot 24 + 6$$

Значит, поедет из $A$ в $B$ трое суток и 6 часов. Следовательно, он прибудет в $B$ в 16 часов.

Обратите внимание на то, что точно такой же результат получился бы, если бы поедет из $A$ в $B$ не 78, а 54, 30 или 126, 102 и вообще $24 \cdot k + 6$ часов при любом целом $k$.

Пример второй. Учитель математики проводит в классе контрольные работы по следующей системе, обеспечивающей, по его мнению, необходимости взаимной помощи учеников. Он разделяет им подряд листочки с условиями задачи («варинты»), переменеров их по числу учеников класса, и сообщает, что все варианты — различные. И действительно, ученики, сидящие недалеко друг от друга, решают различные задачи.

На самом деле учитель заготовляет всего 7 различных вариантов: варинты 8 совпадает с варинтом 1, 9 — с 2, …, 14 — с 7, 15 — с 1 и т. д.

30

Введем теперь следующие определение:

Определене. Если целые числа $a$ и $b$ можно, что их разность делится на натуральное число $m$, то говоря, что $a$ и $b$ сравним по модулю $m^*$).

Сравним чисел $a$ и $b$ по модулю $m$ записывается так:

$$a \equiv b \pmod{m}.$$

Понятно, что два числа сравним по модулю $m$ тогда и только тогда, когда они дают при делении на $m$ одинаковые остатки, то есть принадлежат одному и тому же классу.

Например,

$$27 \equiv 7 \pmod{10}, \quad 78 \equiv 6 \pmod{24}, \quad 6 \equiv 0 \pmod{3}, \quad 25 \equiv -1 \pmod{13}.$$

Понятные сравнимости чисел оказывается полезным при решении многих задач.

Задача 1. Для каких натуральных чисел $n$ число $n^2+2$ делится на 3, то есть $n^2+2 \equiv 0 \pmod{3}$?

Решение.

Если $n \equiv 0 \pmod{3}$, то $n^2+2 \equiv 2 \pmod{3}$,

» $n \equiv 1 \pmod{3}$, » $n^2+2 \equiv 0 \pmod{3}$,

» $n \equiv 2 \pmod{3}$, » $n^2+2 \equiv 0 \pmod{3}$.

Итак, $n^2+2 \equiv 0 \pmod{3}$ тогда и только тогда, когда $n$ не делится на 3.

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

если $a \equiv b \pmod{m}$, и $c \equiv d \pmod{m}$, то

$$a + c \equiv b + d \pmod{m}, \quad a - c \equiv b - d \pmod{m}, \quad ac \equiv bd \pmod{m}.$$

Докажем, например, что сравнение можно перемножать. Так как $a \equiv b \pmod{m}$ и $c \equiv d \pmod{m}$, то $a-b$ и $c-d$ делятся на $m$. Из равенств

$$ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)$$

видно, что $ac-bd$ также делится на $m$, то есть

$$ac \equiv bd \pmod{m}.$$

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

Пусть $a \equiv b \pmod{m}$. Из указанных выше свойств сравнения следует, что $a^k \equiv b^k \pmod{m}$ для любого натурального $k$ (то есть что обе части сравнения можно возводить в степень) и, кроме того, что $ac \equiv bc \pmod{m}$, где $c$ — любое целое число (то есть что обе части сравнения можно умножить на любое целое число).

Задача 2. Какой остаток при делении на 3 дает число $(2^2+1)(3^2+1)(4^2+1) \dots (1000^2+1)$?

Решение. Этот остаток не изменится, если каждое из чисел 2, 3, . . . , 1000 в данной выражении заменить его остатком при делении на 3. Таким образом, интерсующее число по модулю 3 равно $(2^2+1)^{333} (3^2+1)^{333} (1^2+1)^{333} \equiv 5^{333} \cdot 10^{333} \cdot 2^{333} \equiv 2^{333} \cdot 1^{333} \cdot 2^{333} \equiv 2^{2 \cdot 333} \equiv 4^{333} \equiv 1^{333} \equiv 1$, т. е. искомый остаток равен 1.

*) Слово «модуль» (от латинского «modulus»—мера) применяется в различных областях математики и ее приложений; оно присваивается числу, имеющему особо важное значение; например, по отношению к нему ведется счет или измерение.

31

Задание 3. Доказать, что всякое натуральное число $n$ сравним по modulo 9 со своей суммой цифр.

Решение. Пусть

$$\overline{a = a_n a_{n-1} \dots a_0},$$

где $a_0, a_1, \dots, a_n$ — цифры числа $a$. Имеем

$$a = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \dots + a_0.$$

Запишем теперь следующие оценные сравнения:

$$1 \equiv 1 \pmod{9}, \quad 10 \equiv 1 \pmod{9}, \quad \dots, \quad 10^n \equiv 1 \pmod{9}.$$

Умножая эти сравнения соответственно на $a_0, a_1, \dots, a_n$ и складывая, получаем

$$a_0 + 10 \cdot a_1 + \dots + 10^n a_n = a \equiv (a_0 + a_1 + \dots + a_n) \pmod{9}.$$

Отсюда, кстати, сразу получается известный признак делимости чисел на 9 (и на 3).

3. АРИФМЕТИКА ОСТАТКОВ ПО ДАННОМУ MODУЛЮ

Пусть задано натуральное число $m$ (modulo). Расматривая всевозможные целые числа, мы будем интересовать только остатками их от деления их на $m$. Таким образом, мы не будем отличать друг от друга чисел, сравнимых по modulo $m$. При таком условии у нас остаткой $m$ «разных» объектов — остатков от деления на $m$:

$$0, 1, 2, 3, \dots, m-1,$$

и для них мы можем определить новые правила «сложения» и «умножения»: именно, если $r_1$ и $r_2$ — два остатка, то «суммой» $r_1 + r_2$ мы будем называть остаток, который дает число $r_1 + r_2$ при его делении на $m$, а «произведением» $r_1 \cdot r_2$ — остаток при делении $r_1 \cdot r_2$ на $m$. Например, для $m = 10$ остатком от деления на число 10 является последняя цифра его десятичной записи. Поэтому в.ariphметике остатков по modulo 10 будут верны, например, также равенства

$$7 + 3 = 0, \quad 1 + 2 = 3, \quad 7 + 5 = 2, \quad 7 \cdot 5 = 5, \quad 7 \cdot 6 = 2, \quad 2 \cdot 5 = 0.$$

В.ariphметике остатков по modulo 2 всего два остатка: 0 и 1, так что эта.ariphметика совсем простая:

$$0 + 0 = 0, \quad 1 + 0 = 1, \quad 1 + 1 = 0,$$

$$0 \cdot 0 = 0, \quad 1 \cdot 0 = 0, \quad 1 \cdot 1 = 1.$$

Для $m = 6$ получаем

$$5 + 3 = 2, \quad 4 + 2 = 0, \quad 3 + 3 = 0, \quad 3 \cdot 2 = 0, \quad 3 \cdot 4 = 0$$ и т.п.

Таким образом, какдому modulo $m$ соответствует свой.ariphметик. Для сокращения мы будем называть ее $m$-арiphметикой*).

32

В качестве примера приведем таблицы умножения и сложения в 7-арифметике.

Таблица умножения

| × | 1 | 2 | 3 | 4 | 5 | 6 |
| :— | :— | :— | :— | :— | :— | :— |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |

Таблица сложения

| + | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| :— | :— | :— | :— | :— | :— | :— | :— |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 0 | 1 | 2 | 3 | 4 | 5 |

Таблицы эти устройства так: на пересечении строк и столбцов строят произведение (соответствие — суммы) остатков, стоящих в начале этих строк и столбцов.

Из свойств сравнения и обычных правил действия над числами видно, что в $m$-арифметике выполняются приведенные правила обычной.arифметики, то есть для любых остатков $a, b, c$ будет

$$a+b = b+a \text{ — коммутиативность (переместительность) сложения},$$
$$(a+b)+c = a+(b+c) \text{ — ассоциативность (сочетательность) сложения},$$
$$ab = ba \text{ — коммутиативность умножения},$$
$$(ab)c = a(bc) \text{ — сочетательность умножения},$$
$$a(b+c) = ab+ac \text{ — дистрибутивность (распределительность) умножения относительно сложения}.$$

Таким образом, в наших.arифметиках будут верны, например, такие формулы:

$$(a+b)^2 = a^2 + 2ab + b^2,$$
$$(a+b)(c+d) = ac + ad + bc + bd.$$

Рассмотрим несколько задач на использование $m$-арифметики.

Задание 4. Найти остаток от деления $2^{1000}$ на 7.

Решение. Мы должны выяснить, чем равно $2^{1000}$ в 7-арифметике. Легко видеть, что $2^{1000} = (2^3)^{333} \cdot 2 = 1^{333} \cdot 2 = 2$.

Задание 5. Найти последнюю цифру числа $7^{7^{1000}}$.

Решение. Мы должны выяснить, чем равно это число в 10-арифметике. Для этого рассмотрим последовательные степени числа 7 в 10-арифметике:

$$7^1 = 7, 7^2 = 9, 7^3 = 3, 7^4 = 1, 7^5 = 7 \text{ и т. д.}$$

Ясно, что

$$7^{4n} = 1, 7^{4n+1} = 7, 7^{4n+2} = 9, 7^{4n+3} = 3.$$

Итак, мы должны узнать остаток от деления числа $7^{1000}$ на 4. Рассмотрим для этого $7^{1000}$ в 4-арифметике. Поскольку $7^{1000} = 3^{1000}$, мы теперь рассмотрим последовательность остатков в 4-арифметике:

$$3^1 = 3, 3^2 = 1, 3^3 = 3, 3^4 = 1, 3^5 = 3, \dots,$$

33

$$3^{2n+1} = 3, \quad 3^{2n} = 1.$$

Но 1000 — четное число; значит, $7^{1000} = 1$, то есть $7^{1000} = 4n+1$. Следовательно, в 10-аррифметике $7^{71000} = 7^{4n+1} = 7^{4n} \cdot 7 = 7$.

Ответ: число $7^{71000}$ оканчивается на 7.

Задача 6. Доказать, что если $a^2+b^2$ делится на 3, то как $a$, так и $b$ делится на 3.

Решение. Переход к остаткам от деления на 3, получаем 3-аррифметическое равенство $a^2+b^2 = 0$. В 3-аррифметике три остатка: 0, 1, 2.

Имеем: $1^2 = 1, 2^2 = 1$. Легко видеть, что при $a \neq 0$ $a^2+b^2 \neq 0$, то есть из равенства $a^2+b^2 = 0$ следует $a = 0$ и $b = 0$. А это изначит, что $a$ и $b$ одновременно делятся на 3.

ЗАДАЧИ *)

1. Деление с остатком
   1.0. Разделите с остатком —297 на 31, —1005 на 98.

2. Докажите, что число делителей любого натурального числа $N$ не превыходит $2\sqrt{N}$.

3. Найдите остатки от деления чисел ($n$ — натуральное): а) $n$ на $(n-1)$ и на $(n-2)$; б) $(n^2+n+1)$ на $(n+1)$ и на $(n+2)$; в) $(n^4+1)$ на $(n+3)$ (при $n \geqslant 80$).

4. Найдите все целые числа $n$, для которых число $\frac{n^2+1}{n-1}$ тоже целое.

5. Докажите, что произведение трех любых последовательных целых чисел делится на 6.

6. Докажите, что если $a+b+c$ делится на 6, то $a^3+b^3+c^3$ тоже делится на 6 ($a, b, c$ — целые).
   7*. 15 простых чисел составляют.arрифметическую прогрессию. Докажите, что ее разность больше 30 000.

7. Сравнение целых чисел по модулю
   8.0. Найдите все натуральные числа $n$, для которых число $n^3+n+1$ делится на 3.
   9.0. Решите сравнение $6n+5 \equiv 0$ (mod 7).

8. Докажите следующее признак делимости на 11:
   $$a = \overline{a_n a_{n-1} \dots a_0} \equiv 0 \pmod{11}$$

тогда и только тогда, когда
$(-1)^n a_n + (-1)^{n-1} a_{n-1} + \dots + a_n \equiv 0 \pmod{11}$.
11. Пользовать тем, что $1000 \equiv -1$ (mod 7), а также $1000 \equiv 1$ (mod 37), получите признаки делимости на 7 и на 37.
12. Докажите, что если числа $A$ и 5$A$ имеют одинаковую сумму цифр, то $A$ делится на 9.
13. Докажите, что уравнение $15x^2-7y^2=9$ не имеет решения в целых числах.
14. Докажите, что ни при каком целом $n$ число $n^2+3n+5$ не делится на 11.
15. Докажите, что числа вида $3n+2, 5n \pm 2, 7n+3, 7n-1, 7n-2$ ни при каком натуральном $n$ не является точным квадратами.
3. Арифметика остатков по данному modулю
16.0. Постройте таблицы сложения и умножения в 4-, 6-, 8-, 11- и 13-аррифметиках.
17. Постройте таблицы квадратов и кубов в 9-аррифметиках.
18. Пользовать таблицу кубов, полученной в задаче 17, докажите, что числа вида $9n+5$ и $9n+4$ нельзя представить в виде суммы кубов трех чисел.
19. Докажать, что в $p$-аррифметике, где $p$ — простое число, из равенства $ab=0$ при $a \neq 0$ следует, что $b=0$.
20. Докажите, что в $m$-аррифметике для любого остатка $a$ существует единственный остаток — $a$ такой, что $a+(-a)=0$. Выведите отсюда, что уравнение $a+x=b$ имеет решение в любой $m$-аррифметике при любых $a$ и $b$.
21. Докажите, что при составном $m$ в $m$-аррифметике существует остатки $a \neq 0$ и $b \neq 0$ также, что $ab=0$.
22. Пользовать 31-аррифметикой, докажите, что $1^{255}+2^{255}+\dots+30^{255}$ делится на 31.

*) Нуликом отмещены легкие задачи, звездочкой — наиболее сложные.