Сравнения и классы вычетов

4

Н. Виленкин

Сравнения и классы вычетов

Многим любитляем математики известна следующая задача:

Обезьяна и орехи

Пять путешествников остановились на почlee. Они взели с собой мешок орехов и обезьяну. Ноую один из них проснулся, подошел к мешку и разделил орехи на 5 равных частей, причем один орех остался линим. Он отдал обезьяне линим орех, съел свою долю и снова лезла спать. Помом проснулся второй путешествник и, не зная о поступке первого, продолжало то же самое. Помом это же сделали по очереди остальные три путешествника. Когда утром оставился орехи разделил на 5 равных частей, снова остался орех для обезьяны. Сколько было орехов?

Вся трудность этой задачи в лишних орехах, без них ответом послужило бы любое число, которое можно шесть раз делить без остатка на 5, то есть любое число, кратное $5^6 = 15625$. А из-за того, что каждый раз деление произходило с остатком, задачу решить куда труднее. Замечательное решение придумал в сту-

денческие годы знакомый английский физик Дирак. Он решил найти число орехов, которое бы … не менялось при описанной операции (делении на пять частей с выделением ореха обезьяне и подадении одной части). Читатель, несомненно, сказал, что такого числа орехов быть не может — ясно, что после этой операции оно должно уменьшиться. Но все дело в том, что Дирак не ограничивал себя натуральными числами. А тогда ему осталось решить уравнение $\frac{4}{5}(x-1)=x$. Корнем этого уравнения является число —4. Поэтому число —4 могло бы быть решением нашей задачи, но по ее смыслу, конечно, не годится. Зато теперь ясно, как получить положительный ответ: надо к числу —4, найденному Дираком, прибавить $5^6$. Проверьте, что ответ 15 621 удовлетворяет условию задачи. Впрочем, ему удовлетворяет и каждое число вида —4 + $5^6 \cdot k$, где $k$ — любое натуральное число.

Что такое сравнимые числа

Если ответься от требования положительных решения, то любое число вида —4 + $5^6 \cdot k$, где $k$ — целое, является решением задачи про орехи и обезьяну. Эти числа образуют «двустороннюю арифметическую прогрессию» с разностью $5^6$, пространiosoся в обе стороны. У них есть одно общее свойство — при делении на $5^6$ все они дают один и тот же остаток 15 621.

5

Про также числа в математике говорят, что они сравнимы друг с другой по modulo*) 15 625.

В общем виде понятие сравнимости по некоторому modulo $m \in \mathbb{N}$ можно определить двумя равносильными способами:

О пределене 1. Цельные числа $a$ и $b$ называются сравнимыми по modulo $m$, если их разность делится без остатка на $m$.

О пределене 1’. Цельные числа $a$ и $b$ называются сравнимыми по modulo $m$, если их остатки при делении на $m$ oddnakovы*).

Если числа $a$ и $b$ сравнимы друг с другом по modulo $m$, то пишут так:
$$a \equiv b \pmod{m}.$$
Например, $16 \equiv 30 \pmod{7}$, так как разность $16 - 30 = -14$ делится на 7, а $72 \neq 45 \pmod{8}$, так как $72 - 45 = 27$ не делится на 8.

Арифметика остатков

Все числа, сравнимые с числом 2 по modulo 5, одинаково ведут себя при делении на 5 — они дают остаток 2. Объединим эти числа в одно множество и назовем его классом выцелов по modulo 5. Обозначим этот класс той же цифрой 2, только, чтобы отличить его от числа 2, будем писать ее так: $\bar{2}$. Значит, $\bar{2}$—не число, а бесконечная совокупность чисел:
$$\bar{2} = \{... -8, -3, 2, 7, 12, ...\}$$
Так же определяется класс выцелов по любому modulo $m$. При делении на $m$ могут получиться $m$ различных остатков: 0, 1, 2, …, $m - 1$. Каждому из них соответствует свой класс выцелов. Остатку $r$ соответствует класс выцелов $\bar{r}$, состоящий из чисел вида $r + km$, где $k$—целое число:
$$\bar{r} = \{r + km \mid k \in \mathbb{Z}\}.$$
Все множество $\mathbb{Z}$ целых чисел распадается на $m$ классов выцелов по модulo $m$. Множество всех этих классов обозначают через $F_m : F_m = \{0, 1, ..., m - 1\}$. При изучении вопросов, касающихся делимости на $m$, лучше иметь дело с конечным множеством $F_m$, чем с бесконечным множеством $Z$.

Чтобы решать задачи про делимость, надо уметь выполнять над классами выцелов аргументические операции. Начнем со сложения. Она определяется очень просто — в каждом из слагаемых (напомним, что класс выцелов есть бесконечное множество целых чисел) берет по представителю и складывает их, а потом смотрит, в какой класс выцелов попала сумма. Его и называют суммой данных классов. Например, сложим классы выцелов $\bar{4}$ и $\bar{5}$ по modulo 6. Для этого выберем в них по представителю. Чтобы долго не думать, возьмем сами остатки $\bar{4}$ и $\bar{5}$, давшие название классам. Их сумма равна 9. Но $9 \equiv 3 \pmod{6}$ и потому $\bar{4} + \bar{5} = \bar{3}$. Если же классы выцелов не в $F_6$, а в $F_8$, то сумма получится иная: $\bar{4} + \bar{5} = \bar{1}$. А в $F_9$ $\bar{4} + \bar{5} = \bar{0}$.

Чтобы покончить с вопросом о сложении классов выцелов, надо еще доказать, что при выборе иных представителей сумма не изменится. Это следует из такой теоремы:

Теорема 1. Если $a \equiv a_1 \pmod{m}$ и $b \equiv b_1 \pmod{m}$, то $a + b \equiv a_1 + b_1 \pmod{m}$.

Доказательство. Так как $a \equiv a_1 \pmod{m}$, $a = a_1 + km$, где $k \in \mathbb{Z}$, а так как $b \equiv b_1 \pmod{m}$, $b = b_1 + lm$, где $l \in \mathbb{Z}$. Поэтому $a + b = a_1 + b_1 + (k + l)m$, где $k + l \in \mathbb{Z}$, и $a + b \equiv a_1 + b_1 \pmod{m}$.

Мы свели сложение классов выцелов к сложению чисел. Поэтому классов выцелов компутативно и ассоциально, то есть $a + b = \bar{b} + \bar{a}$ и $(\bar{a} + \bar{b}) + \bar{c} = \bar{a} + (\bar{b} + \bar{c})$, прибавление класса $\bar{0}$ не меняет класса выцелов, то есть $\bar{a} + \bar{0} = \bar{a}$, и т. д.

Вычитание и умножение классов выцелов определяются точно так же — в классе выцелают по представителю и выполяют операции над ними. И здесь результаты не зависят от выбо-

6

ра представитель (доказите это сами). Более того, справедливо следующие условия:

Если $P(x)$ — многочлен с целыми коэффициентами $u$ $a \equiv a_1$ (mod $m$), то $P(a) \equiv P(a_1)$ (mod $m$). Постраайтесь доказать это самостояльно.

Свойства операций вычитания и умножения классов вычитов тоже очень похожи на свойства этих операций для целых чисел (за одним исключением; о нем — ниже).

Задание на делимость

Поскольку классы вычитов по модулю $m$ текно связаны с остатками от деления на $m$, почти все задачи, в которых решить о делимости чисел, удобно решать с помощью сравнения.

Пример 1. Найдем остаток от деления $212^{1978}$ на 7.

Так как при делении 212 на 7 получается остаток 2, $212 \equiv 2$ (mod 7). Отсюда следует, что $212^{1978} \equiv 2^{1978}$ (mod 7). Заметим теперь, что $2^3 = 8 \equiv 1$ (mod 7). Но 1978 = $659 \times 3 + 1$. Значит, из $2^3 \equiv 1$ (mod 7) следует, что $2^{1978} = (2^3)^{659} \cdot 2 \equiv 1^{659} \cdot 2 = 2$ (mod 7). Поэтому при делении $212^{1978}$ на 7 получится остаток 2.

Пример 2. Выведем признак делимости на 9.

Так как $10 \equiv 1$ (mod 9), для любого $k$ имеем $10^k \equiv 1$ (mod 9). Но тогда

$$a_0 \cdot 10^n + a_1 \cdot 10^{n-1} + \dots + a_n \equiv a_0 + a_1 + \dots + a_n \pmod{9}.$$

Это значит, что числа $N = a_0 \cdot 10^n + \dots + a_n$ и $M = a_0 + \dots + a_n$ имеют одинаковые остатки при делении на 9. В частности, $N$ делится на 9 в том и только в том случае, когда на 9 делится число $M$ (сумма цифр числа $N$).

Пример 3. Доказем, что квадрат любого натурального числа либо делится на 9, либо даем при делении на 3 остаток 1.

В самом деле, если $x \equiv 0$ (mod 3), то $x^2$ делится на 9. Если же $x \equiv 1$ (mod 3) или $x \equiv 2$ (mod 3), то $x^2 \equiv 1$ (mod 3), так как $1^2 = 1$ и $2^2 = 4 \equiv 1$ (mod 3).

Пример 4. Найдем последнюю цифру числа $7^{71}$

Нам надо найти остаток от деления числа $7^{77}$ на 10. Но $7^2 = 49 \equiv -1$ (mod 10), и потому $7^4 \equiv (-1)^2 \equiv 1$ (mod 10). Найдем остаток от деления показателя $7^7$ на 4. Так как $7 \equiv -1$ (mod 4), $7^7 \equiv (-1)^7 \equiv -1 \equiv 3$ (mod 4), и потому $7^7 = 4m + 3$. Следовательно, $7^{77} = (7^4)^m \cdot 7^3 \equiv (-3)^3 \equiv -27 \equiv 3$ (mod 10). Это значит, что у чисел $7^{77}$ и 3 одинакова последняя цифра, то есть $7^{77}$ кончается на 3.

Деление классов вычитов

Разделить класс вычитов $\bar{b}$ на класс вычитов $\bar{a}$ — значит найти такой класс вычитов $\bar{x}$, что $\bar{ax} = \bar{b}$. Для целых чисел задача деления разрешима не всегда, но уже она решается, то единственный образом. Это связано с тем, что произведение двух целых чисел равно нулю лишь в случае, когда хотя один из множителей равен нулю. Но в $F_m$ делится не так. Взглянув на таблицу умножения для $F_6$, заменаем, что нули строят в ней не только в первой строке и первой столбце (там, где один из множителей равен нулю).

Нулю равны и произведение $\bar{2} \cdot \bar{3}$, $\bar{3} \cdot \bar{4}$, хотя множители отличны от нуля. Как говорят, в $F_6$ есть делители нуля (класс вычитов $\bar{a}$ называется делителем нуля, если он отличен от 0, но существует такой класс $\bar{b} \neq \bar{0}$, что $\bar{a} \cdot \bar{b} = \bar{0}$). В $F_6$ делители нуля оказывается взаимно простыми с моделем 6. Это называет на мысль о справедливости следующей теоремы:

| | $\bar{0}$ | $\bar{1}$ | $\bar{2}$ | $\bar{3}$ | $\bar{4}$ | $\bar{5}$ |
| :— | :— | :— | :— | :— | :— | :— |
| $\bar{0}$ | $\bar{0}$ | $\bar{0}$ | $\bar{0}$ | $\bar{0}$ | $\bar{0}$ | $\bar{0}$ |
| $\bar{1}$ | $\bar{1}$ | $\bar{2}$ | $\bar{3}$ | $\bar{4}$ | $\bar{5}$ | $\bar{5}$ |
| $\bar{2}$ | $\bar{0}$ | $\bar{2}$ | $\bar{4}$ | $\bar{0}$ | $\bar{2}$ | $\bar{4}$ |
| $\bar{3}$ | $\bar{0}$ | $\bar{3}$ | $\bar{0}$ | $\bar{3}$ | $\bar{0}$ | $\bar{3}$ |
| $\bar{4}$ | $\bar{0}$ | $\bar{4}$ | $\bar{2}$ | $\bar{0}$ | $\bar{4}$ | $\bar{2}$ |
| $\bar{5}$ | $\bar{0}$ | $\bar{5}$ | $\bar{4}$ | $\bar{3}$ | $\bar{2}$ | $\bar{1}$ |

7

Теорема 2. Класс вычетов $a$ в $F_m$ не является делительом нуля в том и только в том случае, когда $a$ и $m$ взаимно просты.

Доказательство. Пусть $a$ и $m$ взаимно просты. Если $a \cdot b = 0$, то число $ab$ делится на $m$. Но, в силу взаимной простоты $a$ и $m$, это может быть лишь в случае, когда $b$ делится на $m$, то есть $b = 0$. Это и значит, что $ab = 0$ лишь при $b = 0$, то есть что $a$ не является делительом нуля.

Предположим теперь, что наиболее общий делитель чисел $a$ и $m$ отличается от 1, $a = a_1d$, $m = m_1d$, $d > 1$. тогда число $m_1 < m$ — целое, причем отлично от $m$, и потому $m_1 \neq 0$. Но $am_1 = a_1dm_1 = a_1m$, то есть $am_1 = 0$. Значит, $a$ — делитель нуля.

Если число $a$ взаимно просто с моделем $m$, то все числа из класса вычетов $a$ взаимно просты с $m$. В этом случае говорят, что класс $a$ взаимно прост с $m$.

Из теоремы 2 вытекает важное Следствие 1. Если класс вычетов $a$ взаимно прост с $m$, то в $F_m$ можно однозначно делить на $a$, то есть для любого $b \in F_m$ уравнение $ax = b$ имеет одно и только одно решение.

Сначала доказаем, что это уравнение не может иметь различных решений. Если $ax_1 = b$ и $ax_2 = b$, то $a(x_1 - x_2) = 0$, а так как $a$ не делитель нуля, то $x_1 - x_2 = 0$, то есть $x_1 = x_2$. Значит, решение может быть лишь одно.

Осталось показать, что решение существует.

Мы только что доказали, что средние классов вычетов $a \cdot 0, a \cdot 1, \ldots, a(m-1)$ нет одинаковых. Значит, это же классы $0, 1, \ldots, m-1$, только, возможно, взятые в ином порядке. А тогда для любого класса $b$ найдется такой класс $x$, что $a \cdot x = b$.

Подтверждением доказанного следствия может служить таблица умножения по моделю $6$ — из нее видно, что только в строках для классов $1$ и $5$ встречаются все классы вычетов. В других строках есть лишь часть классов: в строках для $2$ и $4$ классы $0, 2, 4$, а в строке для $3$ — классы $0$ и $3$. Легко понять, как обстоит дело в общем случае:

Следствие 2. Если $(a, m) = d^*$, то уравнение $ax = b$ имеет решение лишь при условии, что $b$ делится на $d$. В этом случае число решения равно $d$.

Представляем читателю доказать это утверждение.

В случае, когда модель уравнения простым числом, можно делить на любой ненулевой класс вычетов — в этом случае все такие классы взаимно просты с моделем. Поэтому, например, в таблице умножения по моделю 5 одна строка состоит из нулей, а остальные содержат по одному разу все классы вычетов.

Теоремы Ферма и Эйлера

В теории чисел очень часто применяется так называемая Малая теорема Ферма:

Теорема 3. Если $p$ — простое число и $a$ не делится на $p$, то остаток от деления числа $a^{p-1}$ на $p$ равен 1.

По-другому ее можно сформулировать следующим образом:

Теорема 3’. Если $a$ — ненулевой класс вычетов по простому моделю $p$, то $a^{p-1} = 1$.

Доказательство. Так как $0 < a < p$, а модель $p$ — простое число, то $a$ и $m$ взаимно просты. Поэтому классы вычетов $a \cdot 1, a \cdot 2, \ldots, a(p-1)$ являются теми же самыми, что и $1, 2, \ldots, p-1$, только

$*)$ $(a, m)$ — наиболее общий делитель чисел $a$ и $m$.