2020-06-29
97Определение 1. Говорят, что целое число m делится на целое же, отличное от нуля, число n или, что число n делит число m и пишут m ⋮ n или n|m, если существует такое целое число k, что m = nk.
В этом случае m называют кратным числа n, n — делителем числа m. Итак, говоря, что m делится на n и записывая m ⋮ n, мы всегда подразумеваем выполнение трех условий: 1) m, n ∈ Z, 2) n ≠ 0, 3) m = nk при некотором целом k. Приведем основные свойства делимости[2]:
0. Согласно условию n ≠ 0 в определении, число 0 не может выступать делителем никакого числа, даже нуля (хотя 0 = 0 · k при всяком k); с другой стороны, 0 делится на любое целое число, кроме самого нуля.
1. m ⋮1 (всякое целое число делится на единицу).
2. n ⋮ n при n ≠ 0 (всякое целое, кроме нуля, делится на себя).
3. Если m ⋮ n и l — любое целое число, то ml ⋮ n.
4. Если m ⋮ n и n ⋮ k, то m ⋮ k.
5. Если m ⋮ n и k ⋮ n, то (m ± k) ⋮ n.
6. Если m ⋮ n и n ⋮ m, то | m | = | n | (m, n ≠ 0).
7. Если m ⋮ n, то | m | ≥ | n |.
Частные признаки делимости на 2, 3, 4, 5, 9, 11 привязаны к десятичной системе счисления[7]. Эти признаки изучают в школьном курсе математики, рассмотрим признаки делимости на 9 и 11.
Натуральное число an 10n + an−1 10n−1 + … + a110 + a0 = an an−1 … a1 a0 делится на 9 тогда и только тогда, когда на 9 делится сумма цифр этого числа в десятичной записи, т.е.
| an an−1 … a2 a1 a0 ⋮ 9 ⇐⇒ (a0 + a1 + a2 + … + an−1 + an) ⋮ 9 | (1) |
Натуральное число an10n + an−110n−1 + … + a110 + a0 = anan−1…a1a0 делится на 11 тогда и только тогда, когда на 11 делится разность суммы цифр, стоящих на четных местах в десятичной записи этого числа, и суммы цифр, стоящих на нечетных местах, т.е.
| anan−1…a1a0⋮11 ⇐⇒ (a0 − a1 + … + (−1)(n−1) an−1 + (−1)n an)⋮11 | (2) |
Известные нам признаки делимости часто допускают те или иные модификации. Приведем, например, обобщение признака делимости на три. Для его формулировки договоримся об обозначениях: если A и B — натуральные числа, то под AB будем понимать натуральное число, которое получается выписыванием сначала цифр числа A (в том же порядке, как они следуют в A), затем — цифр числа B. Назовем операцию составления числа AB склеиванием чисел A и B, а число AB (результат склеивания) — склейкой этих чисел. Склеивание можно выразить через арифметические операции следующим образом: если a — число знаков в десятичной записи A, b — число знаков в десятичной записи B, то AB = A · 10b + B, BA = B · 10a + A. Операция склеивания может быть определена по аналогии для любого набора натуральных чисел, например, A = 12, B = 345, C = 6789, тогда ABC = 123456789, CBA = 678934512.
В этих терминах и обозначениях сформулируем в виде задачи обобщенный признак делимости на 3:
Задача 1. Доказать, что склейка натуральных чисел делится на 3 тогда и только тогда, когда делится на 3 сумма этих же чисел, т.е.
 A1A2… Ak ⁞3 ⇐⇒ (A1 + A2 +... + Ak) ⁞ 3
| (3) |
Решение: Для случая склеивания двух чисел: AB ⁞ 3 ⇐⇒ (A· 10b +B) ⁞ 3 ⇐⇒ (A· 9... 9 +A+B) ⁞ 3 ⇐⇒ (A+B) ⁞ 3, т.к. отбрасывание или добавление слагаемого, делящегося на 3, не нарушает делимости суммы на 3 (у нас такое слагаемое — это произведение A на число, записанное с помощью b девяток, где b — число знаков в десятичной записи B). Случай склеивания k чисел ничем не отличается от этого.
Заметим, что если A1, A2, …, Ak — цифры (т.е. однозначные целые неотрицательные числа), то (3) примет вид школьного признака делимости. Но к следующей задаче школьный признак трудно было бы применить.
Задача 2. Доказать, что делится на 3 число P = 123... 91011... 99100101... 99910001001... 199920002001, склеенное из натуральных чисел от 1 до 2001 включительно.
Решение: Согласно обобщенному признаку делимости на 3, указанное число делится на 3, если делится на 3 сумма S всех натуральных чисел от 1 до 2001 включительно. Сумма же S находится как сумма 2001 членов арифметической прогрессии с первым членом a1 = 1 и 2001-ым членом a2001 = 2001: S = 
= 1001 · 2001. Очевидно, что S делится на 3, поэтому и исходное число делится на 3.
