Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2009/7klass/28r.doc Дата изменения: Fri Apr 24 18:32:59 2009 Дата индексирования: Sat Oct 17 02:26:13 2009 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п

Математический кружок 7 класс

Решения Занятия ?28 Остатки. 11.04.08

> Чтобы найти остаток суммы, надо сложить остатки слагаемых.
> Чтобы найти остаток произведения, надо найти произведение остатков.

Более точно: сумма чисел при делении на некоторое число дает тот же
остаток, что и сумма их остатков. Произведение чисел при делении на
некоторое число дает тот же остаток, что и произведение их остатков.

Например, посчитаем остаток 107*207 по модулю 4. Числа 107 и 207 при
делении на 4 дают остаток 3, если перемножить эти остатки получится 9. А 9
при делении на 4 дает остаток 1, значит, и 107*207 дает остаток 1.

Докажем это на примере конкретного модуля, например 7 (для остатков при
делении на другие числа все аналогично):

Пусть есть два числа: число a делится на 7 с остатком ra, а число b
делится на 7 с остатком rb: [pic] и [pic]

Тогда их сумма равна: [pic] - первая часть делится на 7, поэтому
остаток при делении на 7 у суммы будет такой же, как у числа [pic].

Для произведения:

[pic] - опять же первые слагаемые делятся на 7, поэтому остаток зависит
только от последнего слагаемого, т.е. остаток будет такой же, как у
числа [pic].

1. Сумму двух целых чисел умножили на их произведение. Докажите, получилось
чётное число.

Решение. Рассмотрим все случаи четности этих двух чисел. Если эти два числа
оба нечетные, то их сумма четная. Иначе, хотя бы одно из чисел четное,
поэтому и их произведение четно. Таким образом, в любом случае один из
сомножителей четный, т.е. и произведения четно.

2. Разность двух целых чисел умножили на их сумму и на их произведение.
Докажите, что получившееся число делится на 3.

Решение. Переберем возможные остатки, которые могут давать эти два числа,
при делении на 3,. Если хотя бы одно из чисел делится на 3, то и все
произведение делится на 3. Поэтому осталось разобрать случаи, когда оба
числа не делятся на 3. Если оба числа имеют равные остатки при делении на
3, то их разность делится на 3. Остается вариант, в котором одно из чисел
имеет остаток 1, а другое - 2. В этом случае сумма чисел делится на 3.

Замечание. Ключевым моментом в решении данной задачи было сведение ее к
перебору всех возможных остатков от деления на некоторое число (а именно
3). Данный метод очень часто применяется при решении различных задач.

3. Составьте таблицы сложения и умножения остатков при делении на 4, 5, 6.

Ответ.

|сложение mod 4 | |умножение mod 4 |


|0 |1 |2 |3 |4 |5 | | | | | |0 |1 |2 |3 |4 |5 | |0 |0 |1 |2 |3 |4 |5 |
| | | |0 |0 |0 |0 |0 |0 |0 | |1 |1 |2 |3 |4 |5 |0 | | | | |1 |0 |1 |2 |3
|4 |5 | |2 |2 |3 |4 |5 |0 |1 | | | | |2 |0 |2 |4 |0 |2 |4 | |3 |3 |4 |5
|0 |1 |2 | | | | |3 |0 |3 |0 |3 |0 |3 | |4 |4 |5 |0 |1 |2 |3 | | | | |4
|0 |4 |2 |0 |4 |2 | |5 |5 |0 |1 |2 |3 |4 | | | | |5 |0 |5 |4 |3 |2 |1 |
|

4. Докажите, что число 2005(2006(2007(2008 - 24 делится а) на 2004; б) на
2009.

Решение 4а). Найдем остаток при делении числа 2005(2006(2007(2008 на 2004.
Он равен 1*2*3*4=24, поэтому остаток числа 2005(2006(2007(2008 - 24 равен
24-24=0.

4б). Поскольку 2005=2009-4, у числа -4 такой же остаток при делении на
2009, что и у числа 2005. Остаток произведения не изменится, если какие-то
множители заменить на числа, дающие такой же остаток. Следовательно, у
числа (2009 - 4)(2009 - 3)(2009 - 2)(2009 - 1) такой же остаток при делении
на 2009, как и у числа (-4)(-3)(-2)(-1) = 24. Значит, у числа
2005(2006(2007(2008 - 24 остаток при делении на 2009 будет равен 24-24=0.

5. Какой остаток дает число 1030 - 330 при делении на 7?

Ответ: 0

Решение. Число 10 можно заменить на его остаток при делении на 7, т.е. на
3. Поэтому у числа 1030 такой же остаток при делении на 7, как и у числа
330 , а значит, при вычитании остатки сократятся, и получится число,
делящееся на 7.

Замечание. Объясним, почему число 10 можно было заменить его остатком 3. В
самом деле, 1030 это произведение 30 чисел равных 10, мы уже знаем, что в
произведении можно множители заменить на их остатки, по этому можно
получить произведении 30 чисел равных 3. То есть 330.

6. Докажите, что 711+911 делится на 8.

Решение. Число 7 можно заменить на -1, а 9 - на 1, поэтому у числа 711+911
такой же остаток при делении на 7, как и у числа (-1)11+111=-1+1=0.

7. Докажите, что сумма [pic]делится на 71.

Решение. Заменим каждое из чисел первого слагаемого на остаток по модулю
71, а второго - на наименьшее по модулю число с таким же остатком.
Получится: [pic]. Количество сомножителей во втором слагаемого нечетно,
поэтому [pic]. Два слагаемых имеют противоположный знак и одинаковые
модули, значит, их сумма равна нулю.

8. На какую цифру оканчивается число 777777?

Ответ: 7

Решение. Число 777 заканчивается на 7, значит, 777777 заканчивается на ту
же цифру, что и 7777. Число 72 заканчивается на 9, поэтому 74 заканчивается
на 1. Единица в любой степени будет единица, поэтому [pic] заканчивается на
1. Так как [pic], число 7777 заканчивается на 7.

9. Стёпа играл в солдатиков. Сначала он попытался построить их парами, но
один солдатик оказался лишним. Тогда Стёпа стал строить солдат тройками,
но снова один остался. Та же история повторялась и при построениях по 4,
по 5 и по 6. Стёпа уже приготовился выбрасывать непослушного, но тут
ему, наконец, удалось построить всех в колонну по 7. Сколько солдат
могло быть у Стёпы, если их было меньше 500?

Ответ 301.

Решение. Мысленно выкинем одного солдатика. Тогда количество оставшихся
должно делиться на 2, 3, 4, 5, 6. Найдем НОК чисел от 2 до 6. Это 60.
Значит, всех солдатиков без одного могло бы быть 60, 120, 180, 240, 300,
360, 420, 480. Но вспомним, что число всех солдатиков разделилось на 7.
Значит из чисел 61, 121, 181, 241, 301, 361, 421, 481 надо найти число,
делящееся на 7. Такое число там только одно - 301. Значит, у Степы был
301 солдатик.