Все мы помним правила, помогающие определить делится ли заданное целое число на 2, 5 или 10. Достаточно взглянуть на последнюю цифру числа, чтобы разобраться. Кто-то со школы помнит признаки делимости на 3 или 9 — сумма цифр числа должна делиться на 3 или 9, соответственно. Любители повыпендриваться могут блеснуть знанием признаков делимости на 7 или 11, они уже не столь просты, особенно для больших чисел.
А откуда взялись эти признаки? Почему они такие разные? Можно ли получить универсальный признак делимости на заданное число? Имеется в виду такой признак, который был бы, по возможности, проще прямого деления, и основывался лишь на цифрах числа. Давайте разберёмся с этими вопросами и получим от этого удовольствие!
Поскольку речь идёт о делимости чисел, то нам понадобится модулярная арифметика, в которой числа заменяются на остатки от деления их на некоторое целое число. Например, остатком от деления 5 на 2 будет 1. Мы будем записывать это так, как это принято в математике: 5 ≡ 1 mod 2. Такую операцию называют ещё сравнением чисел по модулю и говорят, что 5 сравнимо с 1 по модулю 2. Отличие сравнения от вычисления остатка от деления состоит в том, что делим мы большее число на меньшее, а сравнивать можно любые числа. Например, 5 ≡ 14 mod 3, поскольку и 5 и 14 дают при делении на 3 остаток 2.
Самое главное свойство сравнения чисел по остаткам состоит в том, что это настоящее отношение эквивалентности! То есть всё, что мы привыкли делать с равенствами (складывать правые и левые части двух равенств, умножать обе части равенства на ненулевое число и т.д.) можно проделывать и со сравнениями по остаткам. В частности, верно, что если
a ≡ a' mod m, и b ≡ b' mod m, то
a + b ≡ a' + b' mod m,
a×b ≡ a'×b' mod m.
Что же нам дают эти абстрактные соображения? Давайте рассмотрим некоторое четырёхзначное число с цифрами abcd:
n = 1000a + 100b + 10c + d.
и зададимся вопросом: "Когда это число будет сравнимо с нулём по модулю 3"?
n = 1000a + 100b + 10c + d ≡ 0 mod 3
Оказавшись в модулярной арифметике, мы можем заменить 10, 100 и 1000 остатками от деления их на 3. Раз 10 ≡ 1 mod 3, то и все степени десяти сравнимы с 1 по модулю 3. Это позволяет нам переписать равенство таким образом:
n = a + b + c + d ≡ 0 mod 3.
Это означает, что число n делится на 3 тогда, когда сумма его цифр тоже делится на 3. Здорово! Вспомним, что 10 ≡ 1 mod 9, а значит признак делимости на 9 будет точно таким же. Других чисел m, для которых 10 ≡ 1 mod m нет, так что этот признак работает лишь для 3 и 9. О том, как можно оптимизировать этот признак делимости я писал тут:
Давайте рассмотрим модуль два. 10 ≡ 0 mod 2, это значит, что все степени 10 больше нулевой, тоже равны нулю. Отсюда имеем отношение:
n = 1000a + 100b + 10c + d ≡ d mod 2
Следовательно, число делится на 2, если последняя цифра делится на 2. Знакомый результат!
А что с признаком делимости, скажем, на 11? Давайте посмотрим: 10 ≡ 10 mod 11, это не интересно. Но в модулярной арифметике могут быть и отрицательные числа! Если двигаться по циферблату в обратную сторону, мы снова получим значения, указанные на циферблате:
11 ≡ 0 mod 11,
11 – 1 ≡ 0 – 1 mod 11,
10 ≡ –1 mod 11.
Отсюда имеем:
10 ≡ –1 mod 11,
100 = 10×10 = (–1)×(–1) ≡ 1 mod 11,
1000 = 100×10 ≡ –1 mod 11,
10000 = 1000×10 ≡ 1 mod 11.
Это значит, что для четырёхзначного числа верно, что
n = 1000a + 100b + 10c + d = (–a) + b + (–c) + d ≡ 0 mod 11
Получили признак делимости: число делится на 11, если сумма знакопеременного ряда его цифр делится на 11. Он работает для любого числа цифр.
Можно построить таблицу с остатками деления степеней десяти на различные числа.
Из неё следуют знакомые признаки делимости на 2 и 5, 3 и 9, а также достаточно удобные признаки для 4 и 8, о которых я писал ранее.
Для 7, 11 и 13 признаки делимости уже нелегко запоминаются, но легко выводятся, если уяснить себе принцип их построения с помощью модулярной арифметики.
Кроме того, можно пересчитать эту таблицу для степеней другого основания, отличного от 10. Так можно получить признаки делимости для произвольной системы счисления. Например, в троичной системе признаком чётности числа будет чётность суммы его цифр, как для делимости на 3 в десятичной системе.
Ура! Теперь все признаки делимости у вас в кармане!