Сравнения

16

Разделится или нет? Этот вопрос часто возникает в арифметике целых чисел. И это не случайно — ведь деление является наиболее сложным из арифметических действия.

Обозначим делимое и делитель буквами $a$ и $m$ (мы ограничимся случаем $m > 0$), а частное и остаток — буквами $q$ и $r$ соответственно. Тогда (см. рисунок) $a = mq + r$, $0 \leq r < m$ (определение деления с остатком).

Если $r = 0$, то $a = mq$, и мы говорим, что «а делимся на $m$» или «а кратно $m$». Обозначается это с помощью троеочия: $a : m$; символ : означает «делимся на…»

Ответить на вопрос, делится или нет, в ряде случаев помогают признаки делимости. Но в школьном курсе рассматривают лишь простейшие из них: на 2, 3, 5 и 9. Признаки делимости, например, на 7, 11 лежат за пределами школьного курса. Знаний, получаемых на уроках арифметики, недостаточно, чтобы найти остаток от деления $2^{25} + 1$ на 641, 1971$^{1972}$ на 7, $22^{11} + 11^{22}$ на 3. На эти и многое другие вопросы дает ответ теория сравнения, об элементах которого и рассказывается в данной статье.

1. Остаток от деления

Нередко остаток $r$ представляется больший интерес, чем частное $q$. Например, чтобы определить НОД

$$mq \cdot a \cdot m(q+1)$$

Рис. 1.

(*) Подробно об этом расскаZAно в статье В. Н. Вагутена «Алгоритм Евклида и основная теорема арифметики», «Квант» № 6, 1972.

18

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

$$a \equiv b, c \equiv d \pmod{m} \Rightarrow a \pm c \equiv b \pm d, ac \equiv bd \pmod{m}.$$ (C)

Отсюда получается также следствия:
к части Dannого сравнения можно прибавлять одно и то же число, их можно умножать на одно и то же число, а также возводить в одну и ту же натуральную степень, то есть

$$a \equiv b \pmod{m} \Rightarrow a + c \equiv b + c, ac \equiv bc, a^k \equiv b^k \pmod{m}.$$

Упражнения

1. Докажите критерий (К) и свойства сравнения (С).

2. Докажите, что части сравнения можно сокращать на число, взаимно простое с моделем (если, конечно, обе части сравнения делятся на это число).

3. Покажите, что сравнение 3x ≡ 4(mod5) верно при любом x, сравнимом с 3 по данному modulo.

4. Проверьте, что не существует целых чисел x, удовлетворяющих 3x ≡ 2(mod 6).

5. Сравнения по modulo и разбиения на классы

Свойства сравнения, данные в пункте 2, позволяют сравнительно просто решать многое задачи теории делимости, нередко встречалось среди олимпиадных, конкурсных и т.п. Рассмотрим неокоторые из них, но предварительно заметим, что при решении этих задач можно решать себе разбитым на классы чисел, сравнимых по данному modulo (при этом модель выбирается в зависимости от обстоятельств или определяется самим условием задачи).

При каждом a сравнению x ≡ a(mod m) удовлетворяет классы чисел x, которые при делении на m дают остаток r(a, m). Для каждой x выполняется одно из сравнений

$$x \equiv 0, x \equiv 1, x \equiv 2, \dots, x \equiv m - 2, x \equiv m - 1 \pmod{m}$$

или, что то же самое, одно из равенств

$$x = mt, x = 1 + mt, x = 2 + mt, \dots, x = m - 2 + mt, x = m - 1 + mt,$$

где t — соответствующее целое число. Итак, каждое целое принадлежит одному из m классов; не сравнимые по данному modulo числа принадлежат различным классам.

Упражнение

5. Проверьте, что отношение сравнимости является отношением эквивалентности и разбиает все числа на классы сравнимых, а именно, докажите, что

a) x ≡ x(mod m);
b) x ≡ y(mod m) ⇒ y ≡ x(mod m);
b) x ≡ y, y ≡ z(mod m) ⇒ x ≡ z(mod m).

Подробно о разбиении на классы рассケано в статье М. М. Глухова «Отношение эквивалентности и разбиения множества», «Кваант» № 2, 1972.

4. Некоторые задачи

Чтобы свободнее пользоваться «языком сравнения» при решении задач, рассмотрим следующие вопросы: какие классы, например, по modulo 6, содержат простые числа? Какому из этих классов принадлежит простое число 37? Какие классы по modulo 6 содержат целевые степени чисел?

Легко видеть, что класс x ≡ 0(mod 6) не содержит простых чисел: он состоит из чисел, кратных 6. Не входят простые числа в класс x ≡ 4(mod 6), так как он состоит из четырех чисел 4+6t = 2(2+3t) (и не содержит числа 2). классы x ≡ 2 и x ≡ 3(mod 6) содержат по одному простому числу: соответственно 2 и 3. классы x ≡ 1, x ≡ 5(mod 6) содержат все остальные простые числа; например, в первый из них входят 7 и 13, а во второй 11 и 17.