§ 2. Не производя деления

Вопрос о том, делится ли данное число n нацело на другое число m, часто возникает в самых разных практических задачах. Один из способов выяснить это состоит в непосредственном делении числа n на число m, однако такой способ далеко не самый легкий. Желание иметь какие-либо критерии, позволяющие устанавливать факт делимости, не прибегая к операции деления, приводит нас к задаче о нахождении наиболее простых признаков делимости.

Некоторые признаки делимости (на 2, на 3, на 5, на 9) хорошо известны. Целью настоящего параграфа является создание более или менее целостной картины, выработка единого взгляда на систему методов, дающих различные признаки делимости. Разумеется, свойства чисел настолько богаты и разнообразны, что их вряд ли можно уложить в одну простую схему, дающую все признаки делимости. Мы постарались отобрать лишь такие свойства, из которых получаются наиболее эффективные, на наш взгляд, результаты.

Для решения приведенных ниже задач могут понадобиться некоторые сведения о целых числах. Напомним, что деление числа n на число m с остатком означает нахождение частного q и остатка r, для которых выполнены условия

n = qm + r, 0≤r<m. Если r = 0, то говорят, что число n делится на m или кратно m. Мы будем разрешать деление не только положительных чисел, но и любых целых чисел вообще - при этом число q, возможно, будет отрицательным или нулем. Будем допускать также и деление с недостатком -r, т. е. представление числа в виде

n = qm - r, 0≤r<m. Полезно знать следующие несложные факты (если они вам не известны, то попробуйте доказать их самостоятельно):

а) если два числа отличаются друг от друга на число, кратное m, то остатки от деления этих чисел на m совпадают, и наоборот;

б) сумма двух чисел имеет тот же остаток от деления на m, что и сумма остатков от деления этих чисел на m;

в) произведение двух чисел имеет тот же остаток от деления на m, что и произведение остатков от деления этих чисел на m;

г) если произведение двух чисел, одно из которых взаимно просто с числом m, делится на m, то второе из этих чисел делится на m, и наоборот;

д) если число делится на каждое из двух взаимно простых чисел, то оно делится и на их произведение.

Число, десятичная запись которого состоит из k цифр n₁, n₂, ..., n_k-1, n_k, идущих справа налево, будем обозначать так: n_kn_k-1...n₂n₁. При этом иногда под k-значным числом будем понимать также числа, имеющие на самом деле менее k цифр, не исключая возможности, что некоторые первые цифры числа являются нулями.

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

2.1. Делимость на 5 Сформулируйте и докажите признак делимости на 5. Как найти остаток от деления числа на 5?

2.2. Делимость на 25 Докажите, что данное число делится на 25 в том и только в том случае, если на 25 делится число, полученное из данного отбрасыванием всех его цифр, кроме двух последних. Укажите, какие в этом случае могут быть две последние цифры числа.

2.3. Степени пятерки Сформулируйте и докажите признак делимости на 5^k при k = 1, 2, 3, ...

2.4. Степени двойки Сформулируйте и докажите признак делимости на 2 и вообще на 2^k при k = 1, 2, 3, ...

2.5. Упрощение для 4 Согласно общему признаку делимости на 2^k, чтобы узнать, делится ли данное число на 4, достаточно проверить, делится ли на 4 число, полученное из данного отбрасыванием всех его цифр, кроме двух последних.

Как можно упростить проверку делимости двузначного числа на 4?

2.6. Упрощение для 8 Согласно общему признаку делимости на 2к, чтобы узнать, делится ли данное число на 8, достаточно проверить, делится ли на 8 число, полученное из данного отбрасыванием всех его цифр, кроме трех последних.

Как можно упростить проверку делимости трехзначного числа на 8?

2.7. По сумме цифр Докажите, что любое число при делении как на 3, так и на 9 дает тот же остаток, что и сумма его цифр.

2.8. Упрощение для 3 Согласно утверждению задачи 2.7, данное число делится на 3 в том и только в том случае, если на 3 делится сумма его цифр.

Как можно упростить проверку делимости суммы цифр числа на 3, не находя самой этой суммы?

2.9. Упрощение для 9 Согласно утверждению задачи 2.7, данное число делится на 9 в том и только в том случае, если на 9 делится сумма его цифр.

Как можно упростить проверку делимости суммы цифр числа на 9, не находя самой этой суммы?

2.10. Только 3 и 9 Докажите, что если признак делимости на число m (большее 1) не зависит от порядка цифр делимого, то само число m может быть равно только 3 или 9.

2.11. Проверка сложения Вы сложили несколько чисел и хотите проверить правильность своих вычислений. Для этого можно поступить следующим образом: найти остаток от деления на 9 суммы цифр полученного ответа, затем найти остаток от деления на 9 общей суммы цифр всех слагаемых. Если указанные два остатка не совпадут, то в вычислениях имеется ошибка. Дайте объяснение предложенному способу проверки сложения.

Придумайте аналогичный способ проверки вычисления алгебраической суммы, т. е. суммы нескольких целых чисел разных знаков.

2.12. Проверка умножения Вы перемножили несколько чисел и хотите проверить правильность своих вычислений. Для этого можно поступить следующим образом: найти остаток от деления на 9 суммы цифр полученного ответа, затем перемножить остатки от деления на 9 суммы цифр каждого из сомножителей и найти остаток от деления на 9 этого произведения, Если указанные два остатка не совпадут, то в вычислениях имеется ошибка.

Дайте объяснение предложенному способу проверки умножения. Придумайте аналогичный способ проверки деления (возможно, с остатком).

2.13. Надежна ли проверка? В задачах 2.11 и 2.12 приведены способы проверки вычислений, которые позволяют усомниться в правильности произведенных выкладок в случае несовпадения некоторых остатков от деления на 9.

Можно ли утверждать, что если указанные остатки совпали, то вычисления не содержат ошибок?

Можно ли это утверждать при условии, что вы ручаетесь за правильность всех цифр полученного в ответе числа, кроме, быть может, одной цифры?

2.14. В магазине Вы пришли в магазин и хотите купить 8 одинаковых авторучек, несколько карандашей по 4 копейки, линейку за 9 копеек, 2 общие тетради по 18 копеек и 12 тонких тетрадей. Продавец подсчитал общую стоимость товаров и попросил вас уплатить в кассу 5 рублей 27 копеек.

Как, по-вашему, не ошибся ли продавец?

2.15. Разложив на множители Сформулируйте признаки делимости на 6, 12, 15, 18, 24, 36, 45. Достаточно ли для проверки делимости числа на 24 установить его одновременную делимость на 4 и на 6?

2.16. Признак Паскаля Для получения признака делимости на m найдем заранее остатки m₁, m₂, m₃,... от деления на m чисел 10¹, 10², 10³,..., соответственно. Для любого числа определим число

f_m(n)= n₀+m₁n₁+m₂n₂+. ..+m_kn_k.

Докажите, что числа n и f_m (n) дают одинаковые остатки при делении на m и могут делиться на m только одновременно. Проверьте, что нахождение остатка m_k+1 при k = 1, 2, 3,... можно осуществить проще, если заметить, что он равен остатку от деления на m числа 10m_k, (вместо числа 10^k+1).

2.17. Частные случаи Проверьте, что сформулированные выше признаки делимости на 2, 3, 5 и 9 (см. задачи 2.4, 2.8, 2.1 и 2.9) представляют собой частные случаи признака Паскаля.

2.18. Что лучше? Получите из признака Паскаля признаки делимости на 4 и на 8. Сравните их с предложенными ранее в задачах 2.5 и 2.6.

2.19. Модификация признака Паскаля Для практического применения признака делимости на m, сформулированного в задаче 2.16, бывает удобнее некоторые из остатков m₁, m₂, m₃,... от деления на m чисел 10¹, 10², 10³,..., Заменить соответствующими недостатками (особенный аффект от такой замены достигается в тех случаях когда недостатки близки к нулю).

Проверьте, что в результата указанной замены признак Паскаля сохранит силу.

2.20. Остаток от деления на 11 С помощью модификации признака Паскаля (см. задачу 2.19) придумайте способ, как найти остаток от деления данного числа на 11, не производя самого деления.

Докажите, что данное число делится на 11 в том и только в том случае, если сумма его цифр, стоящих на четных местах, совпадает с суммой его цифр, стоящих на нечетных местах, или отличается от нее на число, кратное 11.

2.21. Еще одна проверка вычислений По аналогии со способами, предложенными в задачах 2.11 и 2.12, придумайте способы проверки сложения и умножения, основанные на признаке делимости на 11 (см. задачу 2.20).

Докажите, что если возможная ошибка затрагивает только одну цифру полученного в ответе числа, то наличие ошибки можно установить с помощью одного лишь признака делимости на 11.

2.22. Делимость на 7 Пользуясь модификацией признака Паскаля (см. задачу 2.19), сформулируйте признак делимости на 7.

2.23. Разбиение цифр на группы Когда степени десятки дают при делении на m большие остатки и недостатки, эффективность признака Паскаля (см. задачи 2.16 и 2.19) оказывается невелика, поскольку подсчет значения f_m (n) в этом случае столь же трудоемок, что и непосредственное деление числа n на m. В такой ситуации существенную роль может сыграть обнаружение степени десятки, дающей маленький по модулю остаток или недостаток при делении на m, что позволяет разбить все цифры делимого на группы и тем самым действительно облегчить проверку делимости многозначных чисел.

Пользуясь тем, что число 10³ дает при делении на 37 остаток 1, получите следующий признак делимости на 37: если разбить все цифры числа n на тройки, начиная справа (в последней "тройке" может оказаться менее трех цифр, но тогда ее недостающие цифры будем считать нулями), и сложить эти тройки как трехзначные числа, то полученная сумма будет иметь тот же остаток от деления на 37, что и число n.