занятие 13

Тема: Делимость и остатки

2. Остатки

     Задача. Докажите, что n^3 + 2n делится на 3 для любого натурального n.

Решение. Число n может давать при делении на 3 один из трех остатков: 0, 1, 2. Рассмотрим три случая:

Если n дает остаток 0, то и n^3 и 2n делятся на 3, и поэтому n^3 + 2n также делится на 3.

Если n дает остаток 1, то n^3  дает остаток 1,  2n - остаток 2, и сумма остатков                   1 + 2 делится на 3.

Если n дает остаток 2, то   дает остаток 1,   - остаток 2; 2n - остаток 1, а сумма остатков 2 + 1 делится на 3.

Требуемое доказано.

     Обратите внимание! Ключевой момент решения данной задачи - это полный перебор всех возможных остатков от деления. В задачах такого типа это и есть полноценное решение.  А ваша задача - научиться определять по внешнему виду задачи, полезен ли при ее решении перебор остатков.

Задачи для самостоятельного решения

     Задача 16. Докажите, что   делится на 5 при любом натуральном n.

     Задача 17. Докажите, что   не делится на 3 ни при каком натуральном n.

     Задача 18. Докажите, что   делится на 24 при любом нечетном n. Подсказка: докажите, что указанное число делится и на 3, и на 9.

     Задача "не в тему №1". Две лошади пили из одной бочки. Гнедая лошадь выпила половину трети четверти бочки, а вороная - четверть половины трети бочки. Какая лошадь выпила больше воды?

     Задача "не в тему №2". В клубах толстяков "Толстый", "Полный" и "Жирный" по 10 человек. Однажды после совместного обеда они решили провести турнир по игре "Кто тяжелее?". Правила игры таковы: члены двух клубов по жребию разбиваются на пары (один человек - из одного клуба, другой - из другого), и толстяки в каждой паре меряются весом. Тот, кто оказался тяжелее, приносит своей команде очко. Известно, что веса всех толстяков за время турнира не менялись. Могло ли случиться, что во встрече Толстых с Полными со счетом 9 : 1 победили Полные, во встрече Полных с Жирными со счетом 9 : 1 победили Жирные, а во встрече Жирных с Толстыми со счетом 9 : 1 победили Толстые?

Во-первых, не торопитесь отвечать "нет", во-вторых, в задачах такого типа достаточно просто привести пример.

Решения и ответы

     Задача 16. Докажите, что   делится на 5 при любом натуральном n. Возможные остатки при делении числа на 5: 0, 1, 2, 3, 4.

1) Если при делении  n на 5 получается остаток 0, то оба слагаемых делятся на 5, и вся сумма делится на 5.

2) Если n дает остаток 1, то у первого слагаемого остаток 1, а у второго 4; сумма остатков 1 + 4 = 5 делится на 5, значит, все число делится на 5.

3) Если n дает остаток 2, то у первого слагаемого остаток 2, у второго - 3, сумма остатков 2 + 3 = 5 делится на 5, значит, все число делится на 5.

Объясню, откуда взялись остатки 2 и 3. Для первого слагаемого имеем произведение 5 одинаковых множителей n. А правило про остатки гласит:  Произведение любых натуральных чисел и произведение их остатков имеют одинаковые остатки.

Итак, перемножаем 2 • 2 • 2 • 2 • 2 = 32 и "запускаем кассу еще раз": остаток от деления 32 на 5 равен 2. Далее, число n при делении на 5 имеет остаток 2, тогда число 4n имеет остаток 8, делим 8 на 5, получаем остаток 3. Если по-прежнему непонятно, нужно еще раз прочитать про работу кассы, которая выдает остатки в занятии 12.

4) Если n дает остаток 3, то у первого слагаемого остаток 3 (243 делим на 5), у второго - 2 (12 делим на 5), сумма остатков 3 + 2 = 5 делится на 5, значит, все число делится на 5.

5) Если n дает остаток 4 , то у первого слагаемого остаток 4 (5120 делим на 5), у второго - 1 (16 делим на 5), сумма остатков 4 + 1 = 5 делится на 5, значит, все число делится на 5.

Итак, доказали, что данное число точно делится на 5 при любом значении n.

     Задача 17. Докажите, что   не делится на 3 ни при каком натуральном n.

Также сделаем полный перебор возможных остатков. Если n делится нацело на 3, то также делится на 3, но при добавлении 1 получим остаток 1. Если при делении на 3 n дает остаток 1, то и    дает остаток 1, конечный остаток равен 2, а значит, данное число не делится на 3. Ну и, наконец, если при делении на 3 n дает остаток 2, то  дает остаток 2 • 2 = 4, делим на 3, получаем остаток 1 да плюс единица, снова получаем остаток 2.

Итак, данному числу не судьба быть поделенным на 3 без остатка.

     Задача 18. Докажите, что   делится на 24 при любом нечетном n.

Докажем, что данное число делится на 3.

1) для n остаток 0, для всего выражения 0 • 0 • 0 - 0 = 0

2) для n остаток 2, для всего выражения 2 • 2 • 2 = 8, делим на 3, остаток 2, 2 - 2 = 0

Остаток 1 не рассматриваем, так как в условии n  - нечетное число.

Докажем, что данное число делится на 8.

1) для n остаток 1, для всего выражения  1 • 1 • 1 - 1 = 0

2) для n остаток 3, для всего выражения 3 • 3 • 3, делим на 8, остаток 3, 3 - 3 = 0

3) для n остаток 5, для всего выражения 5 • 5 • 5, делим на 8, остаток 5, 5 - 5 = 0

4) для n остаток 7, для всего выражения 7 • 7 • 7, делим на 8, остаток 7, 7 - 7 = 0

Остатки 0, 2, 4 и 6 не рассматриваем, так они получаются при делении четных чисел на 8, а по условию n  нечетное.

Итак, мы доказали, что данное число при любом нечетном n делится нацело и на 3, и на 8, значит, оно делится на 24.

     Задача "не в тему №1". 

Гнедая лошадь выпила   всей бочки, а вороная   всей бочки. Стало быть, они выпили одинаковое количество воды.

        
     Задача "не в тему №2". Пусть в каждый из клубов входят толстяки с весом 110, 111, 112, 113, 114, 115, 116, 117, 118, 119 кг. Рассмотрим пары "Толстые" - "Полные":
110 - 111, 111 - 112, 112 - 113, 113 - 114, 114 - 115, 115 - 116, 116 - 117, 117 - 118, 118 - 119, 
119 - 110. Тогда со счетом 9 : 1 побеждают "Толстые". Точно также можно организовать и другие встречи со счетом 9 : 1 с победой нужного клуба.