Решения

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

2.2. Запишем данное число n в виде 100n₁ + n₀, где n₀ - двузначное число, образованное двумя последними цифрами числа n. Так как число 100n₁ делится на 25, то остаток от деления числа n на 25 равен остатку от деления на 25 числа n₀. Следовательно, число n делится на 25 в том и только в том случае, если остаток от деления числа n₀ на 25 равен 0, т. е. если две последние цифры числа n образуют одну из четырех комбинаций 00, 25, 50 или 75.

2.3. Число n делится на 5^k в том и только в том случае, если на 5^k делится число n₀, полученное из числа n отбрасыванием всех его цифр, кроме k последних. Действительно, запишем число n в виде 10^kn₁ + n₀. Тогда число 10^kn₁ делится на 5^k, а значит, остатки от деления чисел n и n₀ на 5^k совпадают и, стало быть, могут равняться 0 только временно.

2.4. Число n делится на 2^k в том и только в том случае, если на 2^k делится число n₀, полученное из числа n отбрасыванием всех его цифр, кроме к последних. Данное утверждение следует из представления числа n в виде 10^kn₁ + n₀ и того факта, что число 10^kn₁ делится на 2^k.

2.5. Проще всего в данном двузначном числе выделить наибольшее возможное четное число десятков (ведь любое число, кратное 20, кратно и 4), в результате чего останется число, меньшее 20, для которого проверка делимости на 4 уже не представляет труда. Например, число 76 = 60 + 16 делится на 4, а число 94 = 80 + 14 не делится.

2.6. Заметим, что любое четное число сотен делится на 8, а нечетное дает при делении на 8 остаток 4 и недостаток - 4. Поэтому, отбросив цифру сотен данного трехзначного числа, достаточно проверить, делится ли на 8 оставшееся двузначное число в чистом виде, если цифра сотен была четной, либо предварительно увеличенное или уменьшенное на 4, если цифра сотен была нечетной. Кроме того, для упрощения проверки делимости на 8 двузначного числа можно выделить в нем наибольшее возможное число десятков, кратное 4, в результате чего останется число, меньшее 40, для которого проверка делимости на 8 уже не представляет труда. Например, число 692 не делится на 8, так как 92 = 80 + 12 не делится на 8, а число 568 делится на 8, так как 68 - 4 = 64 делится на 8.

2.7. Пусть данное число n имеет вид

Поскольку то получаем

В полученном представлении числа n первое выражение делится как на 3, так и на 9, поэтому остатки от деления числа n и суммы всех его цифр n_k + n_k-1 + ... + n₁ + n₀ как на 3, так и на 9 совпадают.

2.8. Для упрощения проверки делимости суммы цифр данного числа на 3 можно заменять цифры их остатками или недостатками от деления на 3. Например, сумма цифр числа 2 795 438 дает тот же остаток при делении на 3, что и сумма 2 + 1 + 0 - 1 + 1 + 0 - 1 = 2.

2.9. Для упрощения проверки делимости суммы цифр данного числа на 9 можно отбрасывать те цифры, которые в сумме дают 9 или 18. Например, сумма цифр числа 7 543 782 861 дает тот же остаток при делении на 9, что и число 6, поскольку сумма всех остальных цифр (7 + 2) + (5 + 4) + (3 + 7 + 8) + (8 + 1) кратна 9.

2.10. Пусть число m k-значное. Тогда среди чисел от 10^k+1 до 10^k+1 + m хотя бы одно число делится на m. Это число имеет вид , а так как признак делимости на m не зависит от порядка цифр делимого, то числа и также кратны m. Поэтому число m является делителем разности этих чисел, равной 9, а значит, либо m = 3, либо m = 9 (случай m = 1 исключен в условии задачи).

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

2.12. Описанная в задаче проверка умножения основана на том, что если при подсчете произведения нескольких чисел не было сделано ошибки, то это произведение должно давать тот же остаток при делении на m (в задаче взято m = 9), что и произведение остатков от деления сомножителей на m. Проверка деления числа а на число b, в результате которого получены частное q и остаток r, сводится к проверке равенства

a = qb + r,

т. е. двух операций сразу: умножения и сложения. Это можно сделать, сравнив остатки от деления на m числа а и числа qb + r, в котором каждое из чисел q, b и r можно заменить остатком от деления на m. Если остатки не совпадут, то в вычислениях имеется ошибка.

2.13. Совпадение остатков от деления двух чисел на 9 не дает возможности утверждать равенство самих этих чисел: например, числа 49 и 40 имеют одинаковые остатки, но не совпадают друг с другом. Поэтому описанные в задачах 2.11 и 2.12 способы проверки вычислений не могут дать гарантии от ошибок. Та же пара чисел показывает, что даже в случае правильности всех цифр ответа, кроме, быть может, одной, этих проверок, вообще говоря, не достаточно (исключение составляет случай, когда в ответе нет ни одной цифры 0 и 9, поскольку тогда любое изменение одной цифры ответа влечет за собой изменение его остатка от деления на 9).

2.14. Если бы линейка стоила на 1 копейку дешевле, то общая стоимость товаров, выраженная в копейках, была бы кратна 4, так как в этом случае стоимость каждого вида перечисленных в условии предметов делилась бы на 4. Поскольку названа сумма 5 рублей 27 копеек, то число 27 - 1 = 26 должно делиться на 4 (см. задачу 2.5), что неверно. Таким образом, сумма подсчитана с ошибкой.

2.15. Представим данные числа в виде 6 = 2*3, 12 = 4*3, 15 = 3*5, 18 = 2*9, 24 = 8*3, 36 = 4*9, 45 = 9*5 и воспользуемся следующим утверждением: делимость на число m = pq, представляющее собой произведение взаимно простых чисел р и q, равносильна одновременной делимости на р и на q. Взаимная простота чисел р и q играет существенную роль, поскольку без этого требования утверждение было бы неверно. Например, несмотря на справедливость разложения 24 = 4*6, из делимости числа 12 на 4 и на 6 не следует его делимость на 24. В то же время делимость какого-либо числа на 8 и на 3 влечет за собой его делимость на 24.

2.16. Пусть q₁, q₂, q₃, ... - частные от деления на m чисел 10¹, 10², 10³, ... соответственно с остатками m₁, m₂, m₃, ... Тогда справедливо представление

из которого следует, что числа n и

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

дают одинаковые остатки при делении на m. Кроме того, если при последовательном вычислении остатков m₁, m₂, m₃, ... уже найден остаток m_k, то остаток от деления на m числа

равен остатку от деления на m слагаемого 10m_k в последней сумме.

2.17. Полагая в признаке Паскаля m = 2, m = 3, m = 5 и m = 9, получаем для (k+1)-значного числа п следующие числа:

f₂(n)= n₀,

f₃(n)= n₀+n₁+n₂+. ..+n_k,

f₅(n)= n₀,

f₉(n)= n₀+n₁+n₂+. ..+n_k.

Эти числа определяют в точности те же признаки делимости, что и сформулированные в задачах 2.4, 2.8, 2.1, 2.9.

2.18. Полагая в признаке Паскаля m = 4 и m = 8, получаем для k-значного числа n следующие числа:

f₄(n)= n₀+2n₁, f₈(n)= n₀+2n₁+4n₂.

Получаемые в результате признаки делимости на 4 и на 8 несколько отличаются от приведенных в задачах 2.5 и 2.6, однако вряд ли могут рассматриваться как более простые, поскольку, на наш взгляд, требуют чуть больше вычислений.

2.19. Доказательство модификации признака Паскаля, по существу, ничем не отличается от доказательства, приведенного в решении задачи 2.16. Разница состоит лишь в том, что деление каких-то из чисел 10¹, 10², 10³, ... на m нужно провести не с остатком, а с недостатком, т. е. в соответствующих формулах

10^k = q_km + m_k

положительные числа m_k взять на m меньшими прежних (отрицательными), a q_k - на 1 большими прежних.

2.20. Производя в признаке Паскаля деление степеней десятки на 11 попеременно то с остатком, то с недостатком, имеем

10 = 11 - 1, m₁ = -1,

10m₁ = -10 = -11 + 1, m₂ = 1,

10m₂ = 10 = 11 - 1, m₃ = 1,

откуда получаем, что число дает тот же остаток при делении на 11, что и число

f₁₁(n)= n₀-n₁+n₂-n₃+. ..+(-1)^kn_k.

Поэтому для делимости числа n на 11 необходимо и достаточно, чтобы суммы n₀ + n₂ + ... и n₁ + n₃ + ... отличались друг от друга на число, кратное 11.

2.21. Подставляя значение m = 11 в утверждения, сформулированные в решениях задач 2.11 и 2.12, и используя признак делимости на 11, получаем способы проверки сложения и умножения. Если у числа n, представляющего собой истинный ответ, заменить одну цифру на неверную, то число f₁₁(n) обязательно изменится на некоторое число, меньшее 11 (даже меньшее 10), а значит, будет давать другой, уже неверный остаток от деления на 11. Поэтому, сравнив его с верным остатком, можно обнаружить ошибку. Более того, если известно, в какой именно цифре числа n возможна-ошибка, эту цифру можно однозначно восстановить.

2.22. Действуя согласно модифицированному признаку Паскаля, при m = 7 имеем

10 = 7 + 3, m₁ = 3,

10m₁ = 30 = 28 + 2, m₂ = 2,

10m₂ = 20 = 21 - 1, m₃ = -1,

10m₃ = -10 = -7 -3, m₄ = -3,

10m₄ = -30 = -28 - 2, m₅ = -2,

10m₅ = -20 = -21 + 1, m₆ = 1,

10m₆ = 10 = 7 + 3, m₇ = 3, ... ,

откуда получаем, что число дает тот же остаток при делении на 7, что и число

f₇(n) = n₀ + 3n₁ + 2n₂ - (n₃ + 3n₄ + 2n₅)+...

2.23. Пусть все цифры числа n разбиты на тройки, образующие трехзначные числа n₀, n₁, n₂, ..., n_k (начиная справа). Тогда число