Сегодня поговорим о простом и понятном, не очень полезном, но остроумном и, насколько это возможно, симпатичном способе проверить, делится ли число на семь.
Звучит он так:
Число делится на 7, если разница между частным и удвоенным остатком от целочисленного деления числа 10 делится на 7.
Например, сегодня за мной приехало такси с номером 273. По давней привычке, начал проверять не делится ли это число на 3, 7, 13 и т.д. пока не надоест. Для проверки делимости на 7 делим число на 10: 273 = 27×10 + 9 и вычисляем разницу между частным и удвоенным остатком: 27 − 2×3 = 21. О, делится! Это повод написать заметку. Прямо в такси.
Принцип работы
Как же работает этот метод, и каковы его ограничения? Давайте разберёмся.
Итак, мы делим число N на две части — Q и R:
N = 10Q + R.
Как можно упростить это выражение, действуя в модулярной арифметике с модулем 7? Делителей нуля в этой арифметике нет, так что лучшее, что мы модем сделать — превратить число 10 в 1. Для этого нужно найти число, обратное 10. Таким является число 5, поскольку 50 = 49 + 1 = 1 mod 7. Значит, умножив всë выражение на 5, мы упростим его:
5N = Q + 5R mod 7.
Наконец, замечаем, что 5 + 2 = 7 = 0 mod 7, а это значит, что 5 и 2 противоположны друг другу, то есть 5 = −2 mod 7 и можно записать, что
5N = Q − 2R mod 7.
Если число 5N делится на 7, то и N делится на 7. Отсюда мы и получаем наш признак.
Перечислим достоинства и недостатки этого метода.
Плюсы
+ Он оперирует только цифрами числа и для больших чисел даёт ответ за число шагов, пропорциональное десятичному логарифму числа, то есть количеству цифр.
+ На этапе удвоения последней цифры можно использовать сравнения по модулю 7. Например
259: 25 − 2×9 = 4 − 2×2 = 0 mod 7, потому что 25 = 4 mod 7 и 9 = 2 mod 7.
+ С предыдущим пунктом связано то, что если цифры младших разрядов образуют число кратное семи, то их можно отбросить. Это же относится и к самым старшим разрядам.
Примеры:
- 1425942 делится на 7, потому что 259 делится 7, а 14 и 42 можно отбросить.
- 70353142 на 7 не делится, потому что отбрасывая справа и слева цифры, образующие числа, кратные семи, получаем:
70353142 = 353142 = 3142 = 31 = 3 mod 7
Минусы:
− Этот метод непросто запомнить, придумать или вывести.
− Поскольку каждая итерация метода умножает число на 5, он не даёт остатка от деления на 7, а только отвечает на вопрос равен ли остаток нулю или нет.
Метод дающий верный остаток от деления на 7 приводится в другой моей заметке:
И что дальше?
Понять что-то, значит уметь сконструировать аналог с нужными свойствами. Давайте адаптируем этот метод к делимости на другие числа.
Разобъëм число на части
N = 10Q + R,
и подумаем, можно ли «уничтожить» число 10 в различных модулярных арифметиках.
- В ℤ/2ℤ и в ℤ/5ℤ число 10 = 0. Значит
N = R mod 2, 5
То есть, всю информацию о числе несëт последняя цифра.
- В ℤ/3ℤ и в ℤ/9ℤ число 10 = 1, значит
N = Q + R mod 3, 9
и информацию о делимости содержит сумма цифр (цифровой корень), которая получается многократным применением этого алгоритма к числу.
- В ℤ/4ℤ, ℤ/6ℤ и в ℤ/8ℤ число, сравнимое с 10 никаким умножением превратить в единицу не выйдет (оно не обратимое), так что обсуждаемый метод применить не получится, но для них есть другие отличные методы.
- В ℤ/11ℤ число 10 = –1, значит, умножив N на –1 можно получить из 10 единицу. Так мы приходим к хорошо знакомому алгоритму:
–N = Q – R mod 11,
который при многократном применении приводит к сумме знакопеременного ряда цифр.
Пример: 8129:
8–(1– (2 – 9)) = 8 – 1 + 2 – 9 = 0
- В кольце ℤ/13ℤ, число, обратное 10 это 4:
4×10 = 40 = 39 + 1 = 1 mod 13
Значит,
4N = Q + 4R mod 13,
и мы получаем признак делимости:
Число делится на 13, если сумма частного и учетверëнного остатка от целочисленного деления числа на 10 делится на 13.
Применим его к номеру сегодняшнего моего такси 273.
27 + 3*4 = 39 = 0 mod 13.
Значит, таксистский номер делится и на 7 и на 13.
Интересно, что для модулярной арифметики ℤ/3mℤ, обсуждаемый признак делимости будет совпадать с признаком для m. Например, поскольку 21 = 3×7, то выяснить делится ли число на 21 можно точно тем же способом, какой мы использовали для 7. Действительно:
10×19 = 1 mod 21, и 19 = –2 mod 21, а значит метод выглядит как
19N = Q – 2R.