§ 5.4. Критерий делимости

Большинство людей помнят из начальной школы, что число делится на 3, если сумма цифр в его десятичной записи делится на 3. Но почему это верно? Мы легко можем это доказать, используя сравнения по модулю 3. Напомним, что число делится на 3 тогда и только тогда, когда оно сравнимо с 0 по модулю 3. Значит, на языке арифметики остатков критерий делимости на 3 утверждает, что число сравнимо с 0 по модулю 3. если и только если то же самое справедливо для суммы его цифр. Последнее утверждение мы сейчас и докажем.

Пусть а — целое число и его цифры в десятичной записи. Иначе говоря,

где для В предыдущем параграфе мы показали, что умножение не зависит от выбора представителей классов по модулю Поскольку , независимость от выбора говорит нам, что сравнимо с по модулю 3 для любого положительного целого к. Другими словами, любая степень 10 имеет вычет 1 по модулю 3. Значит,

Отсюда немедленно следует, что тогда и только тогда, когда . А это как раз то, что нужно было доказать.

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

Применим похожие аргументы к другому числу, например, к 11. Снова будем предполагать, что

где цифры записи числа а. Поскольку то

будет либо 1 (если к четно), либо —1 (если к нечетно). Поэтому

Говоря человеческим языком, число делится на 11 тогда и только тогда, когда на 11 делится альтернированная сумма его

цифр. Например, 3443 делится на 11, потому что делится на 11.

Критерии делимости на 2 и 5 слишком очевидны, чтобы приводить их доказательства. Таким образом мы нашли простые критерии делимости на все простые числа от 2 до 11, исключая 7. Разберемся, что произойдет в случае применения того же подхода к 7.

Мы уже знаем из предыдущего примера, что та часть рассуждений, которая зависит от модуля, состоит в вычислении степеней 10. На этот раз , а степени 3 не так легко вычисляются, как степени 1 или —1. Попытаемся найти эти степени при малых показателях. Все сравнения, приведенные ниже, сделаны по модулю 7.

Заметим, что последний вычет равен Это означает, что вычеты будут циклически, с периодом повторяться. Эти вычисления показывают, что критерий делимости на 7 несколько более сложен для запоминания, чем на 3 и 11. Поскольку мы уже довольно? далеко продвинулись в работе над этим критерием, точно сформулируем его в простом случай. Предположим, что где Используя вычеты степеней 10, вычисленные только что, мы имеем

Таким образом, а делится на 7 тогда и только тогда, когда на 7 делится выражение Например, 231 делится на 7 ввиду делимости на 7.