Примени математику (Гашков, Сергеев) - страница 13

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

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

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

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

2.24. Общий признак для 7, 11, 13 Пользуясь описанной в задаче 2.23 идеей разбиения цифр на группы, предложите признаки делимости на 7, 11, 13, сводящиеся к проверке делимости некоторого трехзначного числа на 7, 11, 13 соответственно.

2.25. Делимость на 19 Докажите, что число 10n + n_>0 делится на 10m - 1 только одновременно с числом n + n_>0m. С помощью этого утверждения получите признак делимости на 19.

2.26. Делимость на 31 Докажите, что число 10n + n_>0 делится на 10m + 1 только одновременно с числом n - n_>0m. С помощью этого утверждения получите признак делимости на 31.

2.27. Еще о делимости на 13 Докажите, что число 10n + n_>0 делится на 10m + 3 только одновременно с числом n + n_>0(3m + 1). с помощью этого утверждения получите признак делимости на 13.

2.28. Делимость на 17 Докажите, что число 10n + n_>0 делится на 10m - 3 только одновременно с числом n - n_>0(3m - 1). С помощью этого утверждения получите признак делимости на 17.

Решения

2.1. Число делится на 5 в том и только в том случае, если его последняя цифра равна 0 или 5. Действительно, если последняя цифра числа n равна n_>0, то само число n имеет вид 10n_>1 + n_>0. Так как число 10n_>1 делится на 5, то остаток от деления числа n на 5 совпадает с остатком от деления на 5 цифры n_>0. Поэтому остаток от деления числа на 5 равен нулю в том и только в том случае, если его последняя цифра делится на 5, т. е. равна 0 или 5.