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. Пусть q1, q2, q3, ... - частные от деления на m чисел 101, 102, 103, ... соответственно с остатками m1, m2, m3, ... Тогда справедливо представление
из которого следует, что числа n и
fm(n)= n0+m1n1+m2n2+. ..+mknk
дают одинаковые остатки при делении на m. Кроме того, если при последовательном вычислении остатков m1, m2, m3, ... уже найден остаток mk, то остаток от деления на m числа
равен остатку от деления на m слагаемого 10mk в последней сумме.
2.17. Полагая в признаке Паскаля m = 2, m = 3, m = 5 и m = 9, получаем для (k+1)-значного числа п следующие числа:
f2(n)= n0,
f3(n)= n0+n1+n2+. ..+nk,
f5(n)= n0,
f9(n)= n0+n1+n2+. ..+nk.
Эти числа определяют в точности те же признаки делимости, что и сформулированные в задачах 2.4, 2.8, 2.1, 2.9.
2.18. Полагая в признаке Паскаля m = 4 и m = 8, получаем для k-значного числа n следующие числа:
f4(n)= n0+2n1, f8(n)= n0+2n1+4n2.
Получаемые в результате признаки делимости на 4 и на 8 несколько отличаются от приведенных в задачах 2.5 и 2.6, однако вряд ли могут рассматриваться как более простые, поскольку, на наш взгляд, требуют чуть больше вычислений.
2.19. Доказательство модификации признака Паскаля, по существу, ничем не отличается от доказательства, приведенного в решении задачи 2.16. Разница состоит лишь в том, что деление каких-то из чисел 101, 102, 103, ... на m нужно провести не с остатком, а с недостатком, т. е. в соответствующих формулах
10k = qkm + mk
положительные числа mk взять на m меньшими прежних (отрицательными), a qk - на 1 большими прежних.
2.20. Производя в признаке Паскаля деление степеней десятки на 11 попеременно то с остатком, то с недостатком, имеем
10 = 11 - 1, m1 = -1,
10m1 = -10 = -11 + 1, m2 = 1,
10m2 = 10 = 11 - 1, m3 = 1,
откуда получаем, что число дает тот же остаток при делении на 11, что и число
f11(n)= n0-n1+n2-n3+. ..+(-1)knk.
Поэтому для делимости числа n на 11 необходимо и достаточно, чтобы суммы n0 + n2 + ... и n1 + n3 + ... отличались друг от друга на число, кратное 11.
2.21. Подставляя значение m = 11 в утверждения, сформулированные в решениях задач 2.11 и 2.12, и используя признак делимости на 11, получаем способы проверки сложения и умножения. Если у числа n, представляющего собой истинный ответ, заменить одну цифру на неверную, то число f11(n) обязательно изменится на некоторое число, меньшее 11 (даже меньшее 10), а значит, будет давать другой, уже неверный остаток от деления на 11. Поэтому, сравнив его с верным остатком, можно обнаружить ошибку. Более того, если известно, в какой именно цифре числа n возможна-ошибка, эту цифру можно однозначно восстановить.
2.22. Действуя согласно модифицированному признаку Паскаля, при m = 7 имеем
10 = 7 + 3, m1 = 3,
10m1 = 30 = 28 + 2, m2 = 2,
10m2 = 20 = 21 - 1, m3 = -1,
10m3 = -10 = -7 -3, m4 = -3,
10m4 = -30 = -28 - 2, m5 = -2,
10m5 = -20 = -21 + 1, m6 = 1,
10m6 = 10 = 7 + 3, m7 = 3, ... ,