Примени математику

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.

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

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

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

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

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

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

Решения

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