Проверьте, что в результата указанной замены признак Паскаля сохранит силу.
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 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.
2.2.Запишем данное число n в виде 100n 1+ n 0, где n 0- двузначное число, образованное двумя последними цифрами числа n. Так как число 100n 1 делится на 25, то остаток от деления числа n на 25 равен остатку от деления на 25 числа n 0. Следовательно, число n делится на 25 в том и только в том случае, если остаток от деления числа n 0на 25 равен 0, т. е. если две последние цифры числа n образуют одну из четырех комбинаций 00, 25, 50 или 75.
2.3.Число n делится на 5 kв том и только в том случае, если на 5 kделится число n 0, полученное из числа n отбрасыванием всех его цифр, кроме k последних. Действительно, запишем число n в виде 10 kn 1+ n 0. Тогда число 10 kn 1 делится на 5 k, а значит, остатки от деления чисел n и n 0на 5 kсовпадают и, стало быть, могут равняться 0 только временно.
2.4.Число n делится на 2 kв том и только в том случае, если на 2 kделится число n 0, полученное из числа n отбрасыванием всех его цифр, кроме к последних. Данное утверждение следует из представления числа n в виде 10 kn 1+ n 0 и того факта, что число 10 kn 1делится на 2 k.
Читать дальше