дает при делении на 37 тот же остаток, что и сумма n₀ + n₁ + n₂ + ... + n_k, поскольку в полученном представлении числа n второе выражение делится на 999 = 37*27. Если указанная сумма является более чем трехзначным числом, то к ней можно применить те же рассуждения, что и к исходному числу n, и этот процесс можно продолжать до тех пор, пока не получится трехзначное число. Наконец, любое трехзначное число сводится к двузначному переходом к разности чисел и

2.24. Учитывая равенство 1001 = 7*11*13, получаем, что недостаток m₁ при делении числа 103 (на любое из чисел 7, 11, 13) равен -1. Остаток m₂ от деления числа 10³ равен остатку от деления числа 10³m₁ = -1000 = -1001 + 1, т. е. равен 1. Недостаток m₃ от деления числа 10⁶, равен недостатку от деления числа 10³m₂ = 1000 = 1001 - 1, т.е. равен -1, и т. д. Поэтому если все цифры числа n разбиты на тройки, образующие трехзначные числа n₀, n₁, n₂, n₃, ..., n_k (начиная справа), то число

n = n₀+10³n₁ +10⁶n₂ +10⁹n₃+ ...+10^3kn_k

дает при делении на любое из чисел 7, 11, 13 тот же остаток, что и число

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

Такие же рассуждения можно применить к указанной сумме еще и еще раз до тех пор, пока не получится трехзначное число (возможно, отрицательное). Остаток от деления этого числа на 7, 11, 13 будет таким же, как и у исходного числа n.

2.25. Заметим, что число 10m - 1 не имеет общих делителей с числом 10, так как око не делится ни на 2, ни на 5. Поэтому число n + n₀m делится на 10m - 1 тогда и только тогда, когда на 10m - 1 делится число

10 (n + n₀m) = 10n + 10mn₀ = (10n + n₀)+ (10m - 1)n₀, т. е. когда на 10m - 1 делится первое выражение 10n + n₀ в полученном представлении. Полагая в доказанном утверждении m = 2, получаем, что число 10n + n₀ делится на 19 только одновременно с числом n + 2n₀. Таким образом, мы имеем следующий признак делимости на 19. В данном числе 10n + n₀ отбросим последнюю цифру n₀ и, удвоив ее, прибавим к числу я, составленному из остальных цифр исходного числа. Проделав эту процедуру несколько раз, придем к не более чем двузначному числу, которое будет делиться на 19 в том и только в том случае, если на 19 делилось исходное число. Например, для числа 3 086 379 получаем последовательность чисел 308 655, 30 875, 3097, 323, 38, последнее из которых, а значит, и исходное кратно 19.

2.26. Так как число 10m + 1 взаимно просто с числом 10, то число n - n₀m делится на 10m + 1 только одновременно с числом

10 (n - n₀m) = 10n - 10mn₀ = (10n + n₀) - (10m + 1)n₀, т. е. одновременно с числом 10n + n₀. Полагая в доказанном утверждении m = 3, получаем следующий признак делимости на 31. В данном числе 10n + n₀ отбросим последнюю цифру n₀ и, утроив ее, вычтем из числа n, составленного из остальных цифр исходного числа. Повторяя эту процедуру, мы придем к не более чем двузначному числу (возможно, отрицательному), которое будет делиться на 31 только одновременно с исходным числом. Например, для числа 2 886 379 имеем последовательность чисел 288 610, 28 861, 2883, 279, 0, последнее из которых, а значит, и исходное кратно 31.

2.27. Число 10m + 3 не имеет общих делителей с числом 10, так как оно не делится ни на 2, ни на 5. Поэтому число n + n₀(3m + 1) делится на 10m + 3 только одновременно с числом

10(n + n₀(3m + 1)) = (10n + n₀) + (30m + 9)n₀ = (10n + n₀) + 3(10m + 3)n₀, т. е. одновременно с числом 10n + n₀. Полагая m = 1, получаем признак делимости на 13, согласно которому, отбросив в данном числе последнюю цифру n₀ и прибавив учетверенную (3m + 1 = 4) эту цифру к числу n, составленному из остальных цифр исходного числа, получим число, которое будет делиться на 13 только одновременно с исходным числом. Учитывая признак делимости на 13, описанный в задаче 2.24, мы рассмотрим указанную схему лишь в применении к трехзначным числам. Например, для числа 481 последовательно получаем числа 52, 13, последнее из которых, а значит, и исходное кратно 13.

2.28. Так как число 10m - 3 взаимно просто с числом 10, то число n - n₀(3m - 1) делится на 10m - 3 только одновременно с числом

10 (n - n₀(3m - 1)) = (10n + n₀) - (30m - 9)n₀ = (10n + n₀) - 3(10m - 3)n₀, т. е. одновременно с числом 10n + n₀. Полагая m = 2, получаем признак делимости на 17, согласно которому, отбросив в данном числе последнюю цифру n₀ и вычтя упятеренную (3m - 1 = 5) эту цифру из числа n, составленного из остальных цифр исходного числа, мы получим число, которое будет делиться на 17 только одновременно с исходным числом. Например, применяя эту процедуру несколько раз к числу 1067 481, последовательно получим числа 106 743, 10 659, 1020, 102,0, последнее из которых, а значит, и исходное, делится на 17.