Исследовательская работа по теме "Арифметика остатков"

МБОУ Средняя общеобразовательная школа №7

Исследовательская работа по теме:

«Арифметика остатков»

Выполнил:

 Луцев Андрей Романович,

ученик 7А класса

МБОУ СОШ №7

г. Сальск

Руководитель:

Устимова Нина Владимировна,

учитель математики МБОУ СОШ №7 г. Сальска

                                                                Сальск, 2012

Содержание

1. Введение.

2. Основная часть.

3. Практическая часть.

4. Заключение.

5. Литература.

Введение

Решая олимпиадные задачи  на делимость чисел, я столкнулся с проблемой:

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

В связи с этой проблемой  мной была поставлена цель: найти простой способ нахождения остатка при делении на натуральное число.

Для этого мне нужно было решить следующие задачи:

1. Установить факт существования простого способа решения сложных олимпиадных задач на делимость чисел.
2. Если этот способ существует, найти его.

Математика для всех нас начинается с целых чисел. Всюду – дома, в школе, в магазине, в троллейбусе или автобусе – мы складываем, умножаем, делим целые числа. Иногда разделить нацело нельзя – получается остаток, и многое зависит от того, каков этот остаток. Такие случаи я и рассматриваю в своей работе «Арифметика остатков» или арифметика сравнений. «Арифметика остатков» - одна из глав высшей арифметики, имеет отношение и к элементарной арифметике. Многие вопросы элементарной арифметики связаны с этой темой: и деление с остатком, и признаки делимости, и отыскание наибольшего общего делителя, и многое другое. Но эта тема имеет и самостоятельную ценность – арифметика сравнений представляет собой простой пример «необычной», «экзотической» арифметики, в которой действуют сложение и умножение, возведение в степень, вычитание и деление, подчиняющиеся тем же законам, что и в обычной арифметике. Необычность ее в том, что в ней имеется лишь конечное число не равных друг другу или несравнимых друг с другом чисел.

 На основе сказанного выдвинута гипотеза: существует наиболее рациональный способ нахождения остатков при делении больших чисел на натуральное число.

Основная часть

Со скоростью ЭВМ.

Каков будет остаток от деления числа 7778*7779*7780*7781*7782*7783 на 7?

 Для решения этой задачи нам не потребуется ЭВМ. Каждый научится решать такие задачи в уме. Надо только знать немного арифметику, но не обычную, которую в школе учат, а так называемую «арифметику остатков» или «арифметику сравнений». Так называется глава серьёзной математической науки – «теории чисел».

Сравнение целых чисел по модулю.

С арифметикой остатков мы сталкиваемся буквально на каждом шагу. Вот несколько примеров.

Пример 1. В коридоре висит счетчик. Взглянем на него. Он показывает, предположим, 0729 киловатт-часов. А на самом деле сколько электроэнергии израсходовано с момента установки счетчика? 729 кВт . ч? Или 10729? Или, может быть 30729? По показанию счетчика этого не скажешь. Ведь после 9999 на счетчике будет 0000, и счет начнется сначала. Счетчик так задуман, что указывает не полный расход энергии, а только остаток от деления израсходованного числа киловатт-часов на 10000.

Пример 2. Когда мы пошли в школу, на часах было ровно 8, а когда ложились спать, часы показывали 10, а 10 – 8 = 2. Но разве прошло 2 часа с того момента, как мы ушли в школу? Нет, не 2, а целых 14. Дело в том, что стрелки, дойдя до 12.00, каждый раз начинают отсчет времени заново, с нуля. Часы нам показывают не полное время, прошедшее с момента, когда они показывали 0.00, а лишь остаток от деления его на 12.

Можно еще много привести примеров и задач, в которых основную роль играет не частное от деления одного целого числа на другое, а остаток. Для решения такого вида задач была создана «арифметика остатков». Познакомимся с ней поближе.

Рассмотрим остатки от деления на 7. Делитель в теории чисел называется «модулем», а числа, дающие при делении на модуль 7 одинаковые остатки, называются «равноостаточными» или «сравнимыми по модулю 7». Два числа а и b при делении на некоторый модуль m дают одинаковые остатки, т.е. сравнимы по модулю m, записывается так:

                        .

Рассмотрим следующую таблицу:

  Эта таблица построена следующим образом: все целые числа выписаны подряд построчно, по семь чисел в каждой строке. Поэтому соседние числа одного столбца отличаются на 7, а значит при делении на 7 будут давать одинаковые остатки. В первом столбце оказались числа, делящиеся на 7 без остатка, во втором – дают при делении на 7 остаток 1 и т.д.  Известно, что при делении на m, образуется m различных видов остатков: 0, 1, 2, …, m – 1. Остатки в таблице выделены жирным шрифтом – это верхние числа каждого столбца. Можно сказать, что в один столбец попали те и только те числа, которые при делении на 7 равноостаточны, т.е. сравнимы по модулю 7. Итак, все числа разбились на 7 классов: в класс с индексом 0 попали числа, которые при делении на 7 дают в остатке 0 (делятся на 7 без остатка), в класс с индексом 1 – числа, дающие при делении на 7 в остатке 1, и т.д.

Правило определения класса. Чтобы узнать, в каком классе находится некоторое число, надо найти остаток от деления этого числа на m. Этот остаток равен индексу класса. 

    Если разность двух чисел делится на 7 без остатка, то оба числа попадают в один столбец, в один класс. Делаем выводы.

Вывод 1. В один класс попадают все числа, дающие при делении на модуль один и тот же остаток.

Вывод 2. Два числа принадлежат к одному и тому же классу тогда и только тогда, когда их разность делится без остатка на модуль.

Вывод 3. Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса (в частности, индексом того же класса). В буквенном виде это свойство можно записать так:

если  и , то , т.е. сравнения можно складывать.

Вывод 4.  Остаток от деления произведения нескольких чисел на модуль М не изменится, если один из сомножителей ( или даже каждый из сомножителей)  заменить числом того же класса.

   Основные свойства сравнений напоминают свойства обычных равенств: сравнения можно также вычитать, перемножать, возводить в степень, умножать на любое целое число, не равное нулю:

,

,

,

.

Практическая часть

Пример 1. Не проводя обычных вычислений, найти остаток от деления на 7 следующей суммы:      8+79+780+7781+77782+777783.

Решение: остатки от деления слагаемых на 7 равны 1,2,3,4,5,6; например, 77782=77777+5, а 777783=777777+6, значит индексы классов, в которых находятся слагаемые, равны 1,2,3,4,5,6.

Воспользуемся выводом третьим и заменим в данной сумме каждое слагаемое индексом его класса – индекс суммы от этого не изменится. Остаётся найти остаток от деления суммы   на 7

1+2+3+4+5+6=21

Эта сумма делится на 7 без остатка, значит, и данная в условии сумма делится на 7 без остатка.

Используя обозначения, можно решение этой задачи записать так:

8 ≡ 1(mod 7), 79 ≡ 2(mod 7), 780 ≡3(mod 7), 7781 ≡4(mod 7), 77782 ≡5(mod 7), 777783 ≡6(mod 7) ,

8+79+780+7781+77782+777783 ≡ 1+2+3+4+5+6 = 21 ≡ 0    (mod 7)

Ответ: сумма делится на 7 без остатка.

Теперь мы уже можем попытаться решить задачу, с которой начали:

 «Со скоростью ЭВМ».

Каков будет остаток от деления числа 7778*7779*7780*7781*7782*7783 на 7?

 Вместо суммы здесь стоит произведение.  Посмотрим, не обладает ли произведение таким же свойством, что и сумма.

Рассмотрим произведение нескольких, скажем, трех чисел: А, В и С.

Что произойдёт если в произведении АВС число А заменить другим числом того же класса А1? Так как А1 отличается от А на число, кратное 7, то А1=А+7К, где К – некоторое  целое число.

Значит, А1ВС = (А+7К) ВС = АВС+7КВС.

Отсюда видно, что АВС и А1ВС принадлежат к одному классу (отличаются на число кратное 7) .

   Мы можем заменить каждое число индексом его класса. Пользуясь обозначениями теории чисел, можно записать:

если  А ≡ В (mod M), C ≡ D (mod M),то AC ≡ BD (mod M),

т.е. сравнения по одному и тому же модулю можно перемножить.

Теперь нам не трудно решить первую задачу (со скоростью ЭВМ).

 Остаток не изменится, если мы все сомножители заменим индексами их классов, равными 1,2,3,4,5 и 6 соответственно.

Так как 1*2*3*4*5*6 =720 = 20 ≡ 6 (mod 7),

Ответ:  искомый остаток равен 6.

Все наши рассуждения применимы и в том случае, когда вместо модуля 7 используется любое другое натуральное число М, отличное от единицы. В этом случае, вместо таблицы из семи столбцов придётся рассматривать таблицу, содержащую М столбцов.

Пример 2. Доказать, что 776776 + 777777 + 778778 не делится на 3.

Решение: воспользуемся арифметикой вычетов по модулю 3. Так как 776 ≡ 2 (mod 3), то 7762 ≡ 4 ≡ 1 (mod 3), а 776776=  (7762)388 ≡1388 ≡ 1 (mod 3).

 778 ≡ 1 (mod 3) и 778778 ≡ 1778 ≡ 1 (mod 3).

 777 ≡ 0 (mod 3) и 777777 ≡ 0 (mod 3).

Складывая эти сравнения, получим: 776776 + 777777 + 778778 ≡ 1 + 0 + 1 ≡ 2 (mod 3), т.е. данная сумма даёт при делении на 3 остаток, равный 2.

Пример 3. Задача из учебника «Алгебра и начала анализа»10класс под редакцией Ю.М.Колягина. Найти остаток от деления 3946 на 5.

Решение: 39 = 4 (mod 5), 3946 = 446 (mod 5)

Выпишем степени 4: 41 = 4  42 = 16  43 = 64, т.е. 4 в нечётной степени, 6 в чётной степени. Число 46- чётное, значит последняя цифра  446 равна 6. 6 ≡ 1 (mod 5).

Ответ: остаток 1.

Пример 4.

В некотором месяце 3 четверга пришлись на четные числа.

Какой день недели был 26 числа этого месяца?

Решение:

В месяце 3 четных четверга, значит всего 5 четвергов т.к. в неделе 7 дней, то четверги чередуются: четный и нечетный.

Первый четверг – может быть 1,2 или 3 числом, если в месяце 31 день, и 1или 2 числом если в месяце 30 дней.

Значит: Первый четверг – 2 число, а Пятый четверг: 30, следовательно 26 число – это воскресенье.

Ответ: 26 число – это воскресенье.

Заключение.

Изучив «Арифметику остатков», я теперь легко решаю многие олимпиадные задачи на делимость чисел.

Литература.

В своей работе я использовал информацию из книг:

Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике. Москва, «Просвещение»,1984.

Фарков А.В., математические олимпиады в школе. М.,«Просвещение»,2011.

Колягин Ю.М., учебник «Алгебра и начало анализа», 10 класс.

Тезисы.

Тема: «Арифметика остатков».

Автор работы: ученик 7 «А» класса МОУ СОШ №7 Луцев Андрей Романович.

Руководитель: Устимова Нина Владимировна.

Цель: Выяснение существования лёгкого способа решения олимпиадных задач на делимость чисел, не выполняя громоздких вычислений.

Задача:

1. Установить факт существования рационального способа решения сложных олимпиадных задач на делимость чисел.
2. В случае положительного ответа – поиск этого способа, предоставляющего лёгкое и быстрое нахождение решения олимпиадных задач, не выполняя громоздких вычислений.

В ходе работы выявлено:

1. С помощью «арифметики остатков» можно легко решать разные сложные задачи.

Вывод 1. В один класс попадают все числа, дающие при делении на модуль один и тот же остаток.

Вывод 2. Два числа принадлежат к одному и тому же классу тогда и только тогда, когда их разность делится без остатка на модуль.

Вывод 3. Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса.

Вывод 4.  Остаток от деления произведения нескольких чисел на модуль М не изменится, если один из сомножителей  заменить числом того же класса.

Пример 2.

В месяце 5 четвергов, так как четверги чередуются по четности и не четности.

30 дней – 1,2 четверг.  31 день -1,2,3 четверг

7*4+2=30 – 5 четверг.  29 – среда   26 – воскресенье.

Заключение.

Изучив «Арифметику остатков», я теперь легко решаю многие олимпиадные задачи на делимость чисел.