Универсальные признаки делимости чисел: теория и доказательства

Признак делимости на всё
Основная часть
Как правило, обсуждая признаки делимости, разбирают модули, не превосходящие 11
(ладно, ещё 2^n и 5^n). Про другие составные числа говорят, что те раскладываются на
меньшие взаимно простые множители, признаки делимости на которые нам, наверно,
известны. Но мы же понимаем, что целые числа не ограничиваются этими условиями
(взять, например, простые числа или их степени). Как тогда поступить с ними?
Вернемся к семерке и напомним признаки делимости на нее.
Натуральное число делится на 7 тогда и только тогда, когда:
•
разность числа его десятков и удвоенной последней цифры делится на 7;
•
сумма числа его десятков и последней цифры, умноженной на 5, делится на 7;
•
сумма утроенного числа десятков и последней цифры делится на 7.
Почему эти признаки так отличаются от признаков для других чисел? Те кажутся более
приятными, а эти звучат искусственно — их и запомнить тяжелее. Красота признаков
делимости на первые 11 чисел, кроме 7, объясняется тем, что эти числа связаны с
десяткой (делят либо ее, либо ее степень, либо рядом стоящие числа). Нет гарантий, что
для произвольного натурального числа удастся найти приятный признак делимости —
для больших чисел (и тем более простых), как правило, деление эффективнее (если оно
доступно). Одно ясно: все признаки делимости связаны с записью числа, поэтому
уточню, что будем работать в десятичной системе счисления.
Разберем доказательство признаков делимости на 7.
Проверим делимость числа A = 10B + C на 7, где C — его последняя цифра, а остальные
цифры образуют число B. Числа A и D = 10B + (1-7p)C, где p целое, дают один и тот же
остаток. Будем работать с D. Если бы его второе слагаемое делилось на 10, то D и D/10
делились бы на 7 совместно (хотя остатки могли бы быть разными). Остается подобрать
p, чтобы D/10 было целым. Подходят, например, 3 и -7, т. е. D/10 = B - 2C или B + 5C.
Таким образом, получаем первые два признака делимости на 7. Третий признак
доказывается проще, оставляю читателю.
Аналогично можно сформулировать и доказать признаки делимости для любых чисел,
взаимнопростых с 10 (потому что в доказательстве происходит деление на 10):
Эти признаки сводятся к нахождению p или q. Лично мне больше интересен I признак,
хотя II признак звучит проще, сохраняет остатки и справедлив для всех m, а не только
для взаимнопростых с 10. Однако находить p легче, чем q: нужно лишь подобрать
такое k, что 1-mk оканчивается нулем/нулями. Всё.
Как видно, условию на k удовлетворяет бесконечно много чисел, поэтому и признаков
делимости для каждого m можно придумать сколько угодно. Конечно, проще работать с
наименьшими по модулю значениями k (как в признаках для 7), ведь тогда и p будет
меньше.
Отмечу, что иногда эффективнее брать n > 1. Например, взяв n = 2, можно получить
очень симпатичный признак для m = 99 (при этом I и II признаки совпадут), а значит, и
для m = 11 и 33.
Подумайте над следующей простой задачкой:
Какие условия накладываются на пару чисел k_1, k_2 (или p_1, p_2), подходящих для
данных m и n?
Благодаря ней, зная хотя бы один признак, можно легко найти и остальные (в классе I
признаков) или проверить себя.
Заключение
К сожалению, никакой литературы по обобщению признаков делимости я не нашел.
Популярен признак Паскаля, на котором основаны признаки для 2^n, 3, 5^n, 9, 11.
В интернете можно встретить размышления математиков-любителей по поводу разных
обобщений, некоторые предлагают свои (наверно) формулы, использование которых
бывает затратным по времени даже для небольших примеров.
Нужно понимать, что почти у каждого признака делимости есть свой «радиус
действия». Например, как-то для проверки I признака попросил я у отца какое-нибудь
число попроще. Он не промахнулся — дал 113. Легко проверить, что в соответствующем
признаке нужно умножать последнюю цифру на 34.
Проблема: всегда ли целесообразно возиться с этим умножением, а потом еще и
сложением к оставшемуся числу? Всегда ли результат меньше? — Это ведь цель
большинства признаков.
Представленные универсальные признаки легко переносятся на другие системы
счисления, правда для одних и тех же чисел они могут отличаться. Делимость в
произвольных системах счисления интересна сама по себе. Попробуйте найти такие
системы счисления, в которых:
а) признак делимости на 3 аналогичен признаку делимости на 2 в десятичной системе;
б) признак делимости на 2 аналогичен признаку делимости на 3 в десятичной системе.
На сегодня всё!