МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Занятие 14 (15 января 2010 года). Делимость

Признак чего-то называется достаточным, если всегда, когда этот признак выполняется, выполняетcя и это что-то.

Пример 1. Чтобы быть девочкой, достаточно быть девочкой Машей.

Пример 2. Достаточным признаком 2×2 = 4 является приближение динозавра.

Пример 3. Для чётности числа достаточно, чтобы оно заканчивалось на 0, 2, 4 или 6.

Признак чего-то называется необходимым, если всегда, когда это что-то выполняется, выполняетcя и этот признак.

Пример 4. Чтобы быть девочкой Машей, необходимо быть девочкой.

Пример 5. Необходимым признаком приближения динозавра является 2×2 = 4.

Пример 6. Для чётности числа необходимо, чтобы оно заканчивалось на 0, 2, 4, 6, 8 или 1.

Признаки, которые одновременно необходимые и достаточные, обычно так и называют — необходимыми и достаточными.

Необходимые и достаточные признаки удобны тогда, когда проверить их легче, чем то, признаком чего они являются. Большинство признаков делимости имеют вид „a делится на b тогда и только тогда, когда c делится на b”, причём c < a, что, собственно, и облегчает проверку.

Необходимые и достаточные признаки делимости числа:

Для работы с отдельными цифрами в числе удобно ввести следующую запись числа: a_na_{n − 1}...a₂a₁, где a₁ — последняя цифра, a₂ — предпоследняя и т. д.

Доказательство признака делимости на 10.
a_na_{n − 1}...a₂a₁ = a_na_{n − 1}...a₂0 + a₁ = a_na_{n − 1}...a₂ · 10 + a₁.
Таким образом, число имеет тот же остаток при делении на 10, что и его последняя цифра, так что оно делится на 10 тогда и только тогда, когда его последняя цифра — 0.

Доказательство признака делимости на 3.
a_na_{n − 1}...a₂a₁ = a₁ + 10·a₂ + 100·a₃ + ... = (сумма цифр числа) + 3·(3·a₂ + 33·a₃ + ...).
Так что оно делится на 3 тогда и только тогда, когда на 3 делится его сумма цифр.

Пример 7. 4567 = 7 + 10·6 + 100·5 + 1000·4 = (7+6+5+4) + 9·6 + 99·5 + 999·4 = (7+6+5+4) + 3·(3·6 + 33·5 +333·4) = 22 + 3·(3·6 + 33·5 + 333·4)
22 имеет остаток 1 при делении на 3, так что и 22 + 3·(ещё что-то) тоже имеет остаток 1 при делении на 3.

Доказательство признака делимости на 2.
a_na_{n − 1}...a₂a₁ = a_na_{n − 1}...a₂0 + a₁ = a_na_{n − 1}...a₂·5·2 + a₁.
Так что оно делится на 2 тогда и только тогда, когда на 2 делится его последняя цифра.

Задача 1. Докажите оставшиеся признаки делимости.

Задача 2. Придумайте и докажите признаки деления на 16 и 125.

Обозначим сумму всех цифр на чётных местах в числе m за s, а сумму цифр на нечётных местах — за S. Признак делимости на 11: (S − s) должно делиться на 11.

Доказательство. a_na_{n − 1}...a₂a₁ = a₁ + 10·a₂ + 100·a₃ + ... = S + 99a₃ + 9999a₅ + ... + 10(s + 99a₄ + ...) = S − s + 11·(9a₃ + 909a₅ + ... + s + 90a₃ + ...)

Задача 3. Придумайте и докажите признаки делимости на а) 13 и б)37. Подсказка: в пункте а) полезно знать, что 1001 делится на 13.

Задача 4. Делится ли число 11×21×31×41× 51 − 1 на 10?

Задача 5. Найдите все натуральные числа, которые больше своей последней цифры в 5 раз.

Задача 6. Известно, что натуральное число n в 3 раза больше суммы своих цифр. Докажите, что n делится на 27.

Задача 7. Может ли число, сумма цифр которого равна 2010, быть квадратом целого числа?

Задача 8. Ваня задумал простое трёхзначное число, все цифры которого различны. На какую цифру оно может оканчиваться, если его последняя цифра равна сумме первых двух? (Число называется простым, если оно делится нацело только на 1 и на само себя.)

* * *

Задача 9. Докажите, что сумма высот треугольника меньше его периметра.

Задача 10. На поле брани встретились армии Толстых и Тонких по 1000 человек в каждой. Сначала каждый Толстый выстрелил в одного из Тонких. Затем каждый уцелевший Тонкий выстрелил в одного из Толстых. Наконец, каждый уцелевший Толстый ещё раз выстрелил в одного из Тонких. После этого у каждой армии кончились патроны. Докажите, что в живых осталось не менее 500 солдат.