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

Проект ученика. Рассматривали на "Зашибумнике".
Цель: найти простой способ нахождения остатка при делении больших многозначных чисел на натуральное число.
Задачи:
1. Установить факт существования рационального способа решения сложных      олимпиадных задач на делимость чисел.
2. Применение этого способа, предоставляющего лёгкое и быстрое нахождение решения олимпиадных задач, не выполняя громоздких вычислений.
Актуальность
Теория чисел – наука о целых числах. Из множества целых чисел можно перейти к множеству остатков  по некоторому модулю. Понятие сравнимости по данному модулю было введено немецким учёным Карлом Гауссом.
В своей книге «Арифметика исследования» (1801) К. Гаусс не только точно определил отношение сравнимости по данному модулю, но и систематически развил теорию остатков (или сравнений) – важнейший раздел теории чисел. На множестве остатков проще производить вычисления, доказывать теоремы, исследовать математические закономерности, поэтому данная тема актуальна.
Введение
     Часто в повседневной жизни мы сталкиваемся с понятием «остаток», ведь невозможно использовать одни  целые числа. А математика для всех нас начинается именно с целых чисел. В своей работе  мы рассмотрим «Арифметику остатков» или арифметику сравнений. Многие вопросы элементарной арифметики связаны с этой темой: и деление с остатком, и признаки делимости, и отыскание наибольшего общего делителя, и многое другое. Ведь часто встречаются такие задачи, при которых главную роль играют не сами числа, входящие в условие задач, а остатки от деления этих чисел. Решая олимпиадные задачи  на делимость чисел, мы сталкиваемся  с такой проблемой: как, не выполняя громоздких вычислений, найти остаток от деления на натуральное число суммы, произведения больших чисел и степеней с натуральным показателем или  установить делимость нацело.
В связи с этой проблемой  была поставлена цель: найти простой способ нахождения остатка при делении на натуральное число.
Для этого надо решить следующие задачи:
Установить факт существования простого способа решения сложных олимпиадных задач на делимость чисел. Если этот способ существует, найти его.
Гипотеза: существует ли наиболее рациональный способ нахождения остатков при делении больших чисел на натуральное число, чем непосредственный способ деления?
Основная часть. Сравнение целых чисел по модулю.
С арифметикой остатков мы сталкиваемся буквально на каждом шагу.
Пример. Когда мы идём в школу, на часах бывает  ровно 8, а когда ложимся  спать, часы показывают 10, а 10 – 8 = 2. Но разве проходит  2 часа с того момента, как  мы ушли  в школу? Нет, не 2, а целых 14. Дело в том, что стрелки, дойдя до 12.00, каждый раз начинают отсчет времени заново, с нуля. Часы нам показывают не полное время, прошедшее с момента, когда они показывали 0.00, а лишь остаток от деления его на 12.
     В процессе  изучения математики,  во время участия  в математических  олимпиадах, на вступительных экзаменах также могут встретиться задачи, в которых  требуется  выяснить, какой  остаток   даёт какое-либо  выражение  при делении на данное число. Каждый может научиться решать такие задачи в уме. Надо только знать немного арифметику, но не обычную, которую в школе учат, а так называемую «арифметику остатков» или «арифметику сравнений». Так называется глава серьёзной математической науки – «теории чисел». Приведём примеры.
Задача 1. Не приводя  обычных   вычислений, найти остаток   от деления  на  7 следующей  суммы: 8+79+780+7781+7772+777783.
Задача 2. Каков будет остаток   от деления числа 7778;7779;7780;7781;7782;7783 на 7?
Задача 3. Число 137 возвели в сотую степень. Какова последняя цифра десятичной записи результата?
Задача 4. Какой остаток при делении даёт число;1003;^1003?
Решение приведённых задач «в лоб» приводит к большим вычислениям и даже с помощью калькулятора  вызывает затруднение.               
Можно еще много привести примеров и задач, в которых основную роль играет не частное от деления одного целого числа на другое, а остаток. Для решения такого вида задач была создана «арифметика остатков». Познакомимся с ней поближе.
Делитель «В теории чисел»  называют «модулем», а числа, дающие при делении на 7, например,  одинаковые остатки, называются «сравнимыми по модулю 7».
Тот факт, что два числа a и b при делении на некоторый модуль m  дают одинаковые остатки, т. е. сравнимы по модулю m записывают так
a ;b (mod m), «;»- знак сравнения.
Рассмотрим таблицу:
Индекс 0 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 32 33 34
35 36 37 38 39 40 41
42 43 44 45 46 47 ...
… … … … … … …

В этой таблице выписаны все целые неотрицательные числа подряд: в первой строке - первые семь, во второй - следующие семь и т. д. Какие же числа оказались при этом в одном  столбце?
Соседние числа столбца отличаются друг от друга на семь, а значит,  при делении на семь дают одинаковые остатки.
 В первом столбике оказались числа, дающие при делении на 7 остаток  0, во втором столбце - остаток 1 и т.д.
Итак, целые неотрицательные числа разбились на 7 классов с индексами от 0 до 6.
Правило определения класса.
Чтобы узнать, в каком классе находится некоторое число, надо найти остаток от деления этого числа на 7. Этот остаток равен индексу класса.
Следствие:
Если разность двух чисел делится на 7 без остатка, то эти числа попадают в один столбец, в один класс.
Вывод 1:
В один класс попадают все числа, дающие при делении на (7)
 модуль один и тот же остаток.
Вывод 2:
Два числа принадлежат одному классу тогда и только тогда, когда их разность делится без остатка на модуль.
Вывод 3:
Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса (в частности, индексом этого числа).
Теперь мы можем решить задачу № 1 из приведенных выше:
Найти остаток от деления на 7 суммы:
8+79+780+7781+77782+777783
 Решение. Найдем остатки от деления на 7 каждого слагаемого:
8=7+1 (ост.1)
79= 77+2(ост.2)
80=777+3 (ост.3)
7781=7777+4(ост.4)
7782=77777+5(ост.5)
77783=777777+6(ост.6)
Воспользуемся выводом 3 и заменим в данной сумме каждое слагаемое индексом его класса - индекс суммы от этого не изменится. Остается найти остаток от деления суммы.
1+2+3+4+5+6=21; 21 делится на 7, значит,  и данная в условии сумма делится на 7 без остатка. Ответ: остаток 0.
Пользуясь обозначениями теории чисел, вывод 3 можно сформулировать так:
Если А;B(mоd m) и С;D(mоd m), то А+С;В+D(mоd m).
Другими словами, сравнения по одному и тому же модулю можно складывать. Используя обозначения, решение задачи 1 можно записать так:
8;1(mоd 7)
79;2(mоd 7)
……….
777783;6(mоd 7) ;78+79+780+7781+77782+777783 ;1+2+3+4+5+6=21
;0(mоd 7)
 Вывод 4: Остаток от деления произведения нескольких чисел на модуль m не изменится, если один из сомножителей (или даже каждый из сомножителей) заменить числом того же класса.
С помощью обозначений: Если А;(mоd m) и С;D(mоd m), то АС;ВD(mоd m), т.е. сравнения по одному и тому же модулю можно перемножать.
С помощью вывода 4, можно уже решить задачу № 2 . Каков будет остаток от деления числа из задачи №2?
7778;7779;7780;7781;7782;7783;1;2;3;4;5;6;720 ;6(mоd 7) (это числа тех же классов, т. е. заменяем числа остатками и перемножаем.) Ответ: остаток равен 6.
Все рассуждения применимы и в том случае. Когда вместо модуля 7 используется любое другое натуральное число m; 1. В этом случае вместо таблицы из семи столбцов надо рассматривать таблицу из m столбцов.
Задача 3.
Число 137 возвели в сотую степень. Какова последняя цифра десятичной записи результата?
 Решение. Последняя цифра натурального числа есть остаток от деления числа на 10, поэтому используется сравнение по модулю 10.
Согласно выводу 4 имеем: ;137;^100; 7^100(mod 10). Т.е. ;137;^100 оканчивается той же цифрой, что и 7100. При возведении в степень нам достаточно следить за последней цифрой степени: 7^1;7, 7^2 ;9, 7^3 ;3, 7^4;1,7^5; 7, 7^6;9, т.е. получится периодическая последовательность
7;9;1;7;…
На 4-ом, 8-ом, 12-ом. 16-ом и т.д. месте в этой последовательности (на любом месте кратном 4) стоит число 1, значит и на 1000-ом месте будет 1.
Ответ: ;137;^100 оканчивается цифрой 1.
Еще легче решается задача №4.
Задача 4. Какой остаток дает при делении на 3 число ;1003;^103?
                Решение.
;1003;^1003; 1^1003 (mоd 3)=1. Ответ: остаток равен 1.
В заключение приведём упражнения и задачи, позволяющие закрепить навыки применения введенных понятий и выводов.
1.  Даны три числа: 78,210 и 346. Сравнимы ли они с 27 по модулю?
2.  Среди чисел 123, 211, 134, 214, 303 найти все пары чисел, сравнимых между собой по модулю 5.
3.  Записать с помощью сравнения следующие предложения:
а) число а дает остаток 3 при делении на 5;
б) число в дает остаток 1 при делении на 5;
в) числа m и n оканчиваются одной и той же цифрой;
г) число а оканчивается 0;
д) число а оканчивается цифрой 7.
4.  Найти остаток от деления на 8 следующих степеней:
3^13+5^13+7^13
5. Найти остатки от деления на 8 суммы 3^13+5^13+7^13
6. Найти остаток от деления на следующих степеней: 3^14, 7^14, 9^14.               
7. Найти остаток от деления ;13;^49 на 48.
8. Доказать, что ;43;^23+;23;^43 делится на 66
9. Доказать, что; 776;^776 +;777;^777+;778;^778 не делится на 3.
10. Найти две последние цифры десятичной записи чисел2^49, 3^101, ;17;^28.
Ответы и решения.
1. 27;5(mod 11), 78;1 (mod 11), 210;1(mod 11), 346;5(mod 11).
Ответ: 78 и 210-нет, 346-да.
2. 123;3 (mod 5), 211;1 (mod 5), 134;4(mod 5), 214;4(mod 5), 303;3(mod 5), 21;1(mod 5).
Ответ: 123;303(mod 5), 211;21(mod 5),214;134(mod 5).
3. а) a;3 (mod 5); б) в;1 (mod 5); в) m;n (mod 10); г) a;o (mod 10); д) a;7(mod 10)
4. 3^13=9^6 ;3^1 ;;1;^6;3(mod 8) =3 (mod 8)               
5^13=;25;^6 ;;5;^1;1^6;5(mod 8) =5(mod 8)
7^13=49;;7;^1=1^6;7 (mod 8) =7(mod 8). Ответ: остатки равны 3, 5 и 7 соответственно.
5.  3^13+5^13+7^13;3+5+7(mod8);7(mod 8). Ответ: остаток равен 7.
6.  3^14=9^7=;81;^3;9;1^3;9(mod 10)=9(mod 10)
7^14=;49;^7;9^7(mod 10);9(mod 10). (Смотреть предыдущий пример)
9^14=;81;^7;1^7(mod 10)=1(mod 10).  Ответ: остатки равны 9, 9 и 1 соответственно.
7. ;13;^49=;169;^24;13;;25;^4 ;13(mod 48)= ;625;^12 ;13(mod 48);1^12 ;13 (mod 48) =
13(mod 48). Ответ: остаток равен 13.
№ 8. (Пример на доказательство).
 Доказательство: 66=6 ;11, поэтому для доказательства надо доказать, что данная сумма кратна 6 и кратна 11.
;43;^23+;23;^43;1^(23 )+  5^43  (mod 6)=1+;25;^21;5^1 (mod 6);1+5(mod 6) =
6(mod 6);0(mod 6), т. е. сумма кратна 6.
;43;^23+;23;^43;;10;^23+ 1^43(mod 11) =;100;^11;10+1(mod 11);11(mod 11);0(mod 11)               
Т. е. сумма кратна 11. Следовательно, данная сумма кратна 66.
№9. Доказать, что; 776;^776 +;777;^777+;778;^778 не делится на 3.
 Доказательство.
Найдём остатки от деления на 3 каждого слагаемого суммы.
;776;^777;2^776(mod 3)= 4^388(mod 3); 4^388(mod 3);1^388(mod 3)=1(mod 3)
;777;^777=0(mod 3),
;778;^778;1^778(mod 3)=1(mod 3). Складывая,  получим:
;776;^776+;777;^777+;778;^778;1+0+1=2(mod 3)
Т. е. данная сумма при делении на 3 даёт остаток 2. Чтд.
10 а)  2^49=(2^7)7 =;128;^7=;28;^7(mod 100)= ;28;^6 ;28=;784;^3 ;28 ;;84;^3 ;28(mod100) =
7056 ;2352;56 ;52(mod 100) = 2912;12(mod 100).
б)  3^101=(3^5)20  ;3=;243;^20 ;3;;43;^20 ;3(mod 100) =( ;43;^2)10 ;3=;1849;^10  ;3
;;49;^10 ;3(mod 100)= ;2401;^5 ;3;1^5 ;3=3(mod 100)
;в) 17;^28=(;17;^2)14 =;289;^14;;89;^14(mod 100)= ;7921;^7;;21;^7(mod 100)=( ;21;^2)3  ;21;
;;441;^3 ;21;;41;^3 ;21(mod 100) =1681 ;861;81 ;61(mod 100) =1941;41(mod 100).
Ответ: последние две цифры соответственно равны 12; 03; 41.
Выводы:
1. Установили  факт существования рационального способа решения сложных      олимпиадных задач на делимость чисел.
2. Сформулировали правило определения класса. Чтобы узнать, в каком классе находится некоторое число, надо найти остаток от деления этого числа на некоторое число – m (модуль). Остаток равен индексу класса.
• В один класс попадают все числа,  дающие при делении на модуль один и тот же остаток.  Два числа принадлежат к одному и тому же классу тогда и только тогда, когда их разность делится без остатка на модуль.
• Остаток от деления суммы на модуль не изменится, если одно из слагаемых или каждое слагаемое заменить другим числом того же класса (в частности, индексом того же класса). Остаток от деления произведения нескольких чисел на модуль m не изменится, если один из сомножителей (или даже каждый из сомножителей)  заменить числом того же класса.
3. Этот способ применили на примерах и показали, что можно получить ответ,  не выполняя громоздких вычислений.
Основные свойства сравнений напоминают свойства обычных равенств: сравнения можно не только складывать, а также вычитать, перемножать, возводить в степень, умножать на любое целое число, не равное нулю.
4. Рекомендуем всем учащимся изучить этот способ из «Арифметики остатков» и в дальнейшем самостоятельно его использовать не только на олимпиадах, но и на внеклассных уроках и на экзаменах.
Заключение.
      Изучив «арифметику остатков», мы узнали много нового, и это нам поможет в дальнейшей учёбе. С помощью «арифметики остатков» теперь мы сможем легко решать разные сложные задачи на делимость чисел. Эта тема имеет самостоятельную ценность – арифметика сравнений представляет собой простой пример «необычной» арифметики, в которой действуют сложение и умножение, возведение в степень, вычитание и деление, подчиняющиеся тем же законам, что и в обычной арифметике. Необычность ее в том, что в ней имеется лишь конечное число не равных друг другу или несравнимых друг с другом чисел.

Литература.
1. Гусев В.А., Орлов А.И., Розенталь А. Л. Внеклассная работа по математике. Москва, «Просвещение», 2004.
2. Колягин Ю.М., учебник «Алгебра и начала  анализа», 10 класс.

Научный руководитель – Кобаидзе  Н. И.