2.21. Еще одна проверка вычислений По аналогии со способами, предложенными в задачах 2.11 и 2.12, придумайте способы проверки сложения и умножения, основанные на признаке делимости на 11 (см. задачу 2.20).
Докажите, что если возможная ошибка затрагивает только одну цифру полученного в ответе числа, то наличие ошибки можно установить с помощью одного лишь признака делимости на 11.
2.22. Делимость на 7 Пользуясь модификацией признака Паскаля (см. задачу 2.19), сформулируйте признак делимости на 7.
2.23. Разбиение цифр на группы Когда степени десятки дают при делении на m большие остатки и недостатки, эффективность признака Паскаля (см. задачи 2.16 и 2.19) оказывается невелика, поскольку подсчет значения fm (n) в этом случае столь же трудоемок, что и непосредственное деление числа n на m. В такой ситуации существенную роль может сыграть обнаружение степени десятки, дающей маленький по модулю остаток или недостаток при делении на m, что позволяет разбить все цифры делимого на группы и тем самым действительно облегчить проверку делимости многозначных чисел.
Пользуясь тем, что число 103 дает при делении на 37 остаток 1, получите следующий признак делимости на 37: если разбить все цифры числа n на тройки, начиная справа (в последней "тройке" может оказаться менее трех цифр, но тогда ее недостающие цифры будем считать нулями), и сложить эти тройки как трехзначные числа, то полученная сумма будет иметь тот же остаток от деления на 37, что и число n.
Придумайте способ, как упростить проверку делимости трехзначного числа на 37.
2.24. Общий признак для 7, 11, 13 Пользуясь описанной в задаче 2.23 идеей разбиения цифр на группы, предложите признаки делимости на 7, 11, 13, сводящиеся к проверке делимости некоторого трехзначного числа на 7, 11, 13 соответственно.
2.25. Делимость на 19 Докажите, что число 10n + n0 делится на 10m - 1 только одновременно с числом n + n0m. С помощью этого утверждения получите признак делимости на 19.
2.26. Делимость на 31 Докажите, что число 10n + n0 делится на 10m + 1 только одновременно с числом n - n0m. С помощью этого утверждения получите признак делимости на 31.
2.27. Еще о делимости на 13 Докажите, что число 10n + n0 делится на 10m + 3 только одновременно с числом n + n0(3m + 1). с помощью этого утверждения получите признак делимости на 13.
2.28. Делимость на 17 Докажите, что число 10n + n0 делится на 10m - 3 только одновременно с числом n - n0(3m - 1). С помощью этого утверждения получите признак делимости на 17.
Решения
2.1. Число делится на 5 в том и только в том случае, если его последняя цифра равна 0 или 5. Действительно, если последняя цифра числа n равна n0, то само число n имеет вид 10n1 + n0. Так как число 10n1 делится на 5, то остаток от деления числа n на 5 совпадает с остатком от деления на 5 цифры n0. Поэтому остаток от деления числа на 5 равен нулю в том и только в том случае, если его последняя цифра делится на 5, т. е. равна 0 или 5.
2.2. Запишем данное число n в виде 100n1 + n0, где n0 - двузначное число, образованное двумя последними цифрами числа n. Так как число 100n1 делится на 25, то остаток от деления числа n на 25 равен остатку от деления на 25 числа n0. Следовательно, число n делится на 25 в том и только в том случае, если остаток от деления числа n0 на 25 равен 0, т. е. если две последние цифры числа n образуют одну из четырех комбинаций 00, 25, 50 или 75.
2.3. Число n делится на 5k в том и только в том случае, если на 5k делится число n0, полученное из числа n отбрасыванием всех его цифр, кроме k последних. Действительно, запишем число n в виде 10kn1 + n0. Тогда число 10kn1 делится на 5k, а значит, остатки от деления чисел n и n0 на 5k совпадают и, стало быть, могут равняться 0 только временно.
2.4. Число n делится на 2k в том и только в том случае, если на 2k делится число n0, полученное из числа n отбрасыванием всех его цифр, кроме к последних. Данное утверждение следует из представления числа n в виде 10kn1 + n0 и того факта, что число 10kn1 делится на 2k.
2.5. Проще всего в данном двузначном числе выделить наибольшее возможное четное число десятков (ведь любое число, кратное 20, кратно и 4), в результате чего останется число, меньшее 20, для которого проверка делимости на 4 уже не представляет труда. Например, число 76 = 60 + 16 делится на 4, а число 94 = 80 + 14 не делится.