Выбрать главу

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, ... ,