Проект Использование теории вычетов для решения олимпиадных задач

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ БЕЛОЯРОСКОГО РАЙОНА «СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №3 г. БЕЛОЯРСКИЙ»

Проект в номинации №7. «Нерешенные задачи и как их решать – теоретические исследования сформулированных проблем в различных отраслях знания»

Тема проекта:

«Использование арифметики вычетов для решения олимпиадных задач»











Автор:


Матусевич Кирилл Викторович


Класс: 8 б


Научный руководитель проекта:


Товстоног Елена Анатольевна


«Общеобразовательная средняя


(полная) школа № 3


г. Белоярский»


учитель математики



















Белоярский

2015


Содержание

13 TOC \o "1-3" \h \z \u 1413 LINK \l "_Toc412893592" 14ПЛАН РАБОТЫ 13 PAGEREF _Toc412893592 \h 1431515
13 LINK \l "_Toc412893593" 14ВВЕДЕНИЕ 13 PAGEREF _Toc412893593 \h 1441515
13 LINK \l "_Toc412893594" 14ОСНОВНАЯ ЧАСТЬ 13 PAGEREF _Toc412893594 \h 1451515
13 LINK \l "_Toc412893595" 141. Сравнения по модулю. Свойства сравнений 13 PAGEREF _Toc412893595 \h 1451515
13 LINK \l "_Toc412893596" 142. Арифметика сравнений 13 PAGEREF _Toc412893596 \h 1481515
13 LINK \l "_Toc412893597" 143. Арифметика вычетов по модулю m 13 PAGEREF _Toc412893597 \h 14101515
13 LINK \l "_Toc412893598" 144. Решение линейных диофантовых уравнений 13 PAGEREF _Toc412893598 \h 14161515
13 LINK \l "_Toc412893599" 14ЗАКЛЮЧЕНИЕ 13 PAGEREF _Toc412893599 \h 14191515
13 LINK \l "_Toc412893600" 14СПИСОК ЛИТЕРАТУРЫ 13 PAGEREF _Toc412893600 \h 14201515
13 LINK \l "_Toc412893601" 14ПРИЛОЖЕНИЕ 13 PAGEREF _Toc412893601 \h 14211515
15
ПЛАН РАБОТЫ

Методы работы:
изучение литературы;
построение системы аксиом, необходимых для доказательства свойств арифметики вычетов;
доказательство свойств арифметики вычетов и решение на их основе олимпиадных задач.
Сроки проведения работы: с сентября по февраль 2014-2015 учебного года.
Этапы работы:
1 этап – изучение проблемы (сентябрь);
2 этап – сбор информации по проблеме (октябрь);
3 этап – обработка и анализ информации (ноябрь);
4 этап – оформление документации (декабрь, январь);
5 этап – презентация учебного проекта (февраль).
Предмет исследования: методы решения задач, связанных с делением целых чисел и решением уравнений в целых числах.
Цель исследования: рассмотрение основных методов решения задач, связанных с делением целых чисел и решением уравнений в целых числах в аспекте их реализации при подготовке к олимпиадам разного уровня.
Гипотеза - изучение свойств арифметики вычетов позволит определить общие методы решения олимпиадных задач, связанных с делением целых чисел и решением уравнений в целых числах.
Задачи исследования:
построить систему аксиом, необходимых для доказательства свойств вычетов;
изучить свойства вычетов;
научиться решать задачи на доказательство делимости целых чисел;
научиться решать линейные диофантовы уравнения с двумя неизвестными;
оформить результаты исследования.
Предполагаемые результаты: научиться решать задачи на доказательство делимости целых чисел; научится решать линейные диофантовы уравнения с двумя неизвестными, с помощью арифметики вычетов.

ВВЕДЕНИЕ

Задания, связанные с делением целых чисел и решением уравнений в целых числах присутствуют в качестве заданий практически на каждой олимпиаде по математике. Существует много методов их решения, которые не входят в школьную программу по математике, однако их полезно знать участникам олимпиад.
Делимость чисел и решение управней в целых числах рассматривается в рамках одного из разделов математики – теории чисел. Основы теории чисел зародились еще в Древнем Египте и Вавилоне. Вавилонские клинописные математические тексты включают таблицы умножения и обратных чисел, квадратов и кубов чисел натурального ряда. Самой древней археологической находкой в истории арифметики является обломок [ Cкачайте файл, чтобы посмотреть ссылку ], датируемый 1800 годами до нашей эры. Он содержит список [ Cкачайте файл, чтобы посмотреть ссылку ]. Весомый вклад в становление теории чисел внесли [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ] и пифагорейцы. Пифагорейцы рассматривали только целые положительные числа и полагали число собранием единиц. Единицы были неделимы и располагались в виде правильных геометрических тел. Пифагорейцам характерно определение «[ Cкачайте файл, чтобы посмотреть ссылку ]» («треугольных», «квадратных» и других). Изучая свойства чисел, они разбили их на чётные и нечётные, простые и составные. Пифагорейцы нашли бесконечное множество целых решений уравнения a2+b2=c2, так называемых пифагоровых троек, и вывели для них общую формулу. Евклид посвятил несколько книг «Начал» [ Cкачайте файл, чтобы посмотреть ссылку ], в основе этой теории лежит [ Cкачайте файл, чтобы посмотреть ссылку ] для нахождения [ Cкачайте файл, чтобы посмотреть ссылку ] двух чисел. Следствием алгоритма является возможность разложения любого числа на простые сомножители, а также единственность такого разложения. Диофант в своем труде «Арифметика» перечислил задачи по нахождению целочисленных решений для уравнений (называемых сейчас [ Cкачайте файл, чтобы посмотреть ссылку ]).
Целью моего проекта является рассмотрение основных методов решения задач, связанных с делением целых чисел в аспекте их реализации при подготовке к олимпиадам разного уровня.
Любая научная теория, в том числе и математическая, строится на основе определенной системы аксиом (исходных положений, принимаемых в рамках данной теории истинными без требования доказательства и используемых в основе доказательства других ее положений). Поскольку моя работа затрагивает достаточно узкий круг вопросов, я постарался минимизировать понятийный аппарат, используемый в работе, стараясь сохранить целостность логики теоретического изложения.
ОСНОВНАЯ ЧАСТЬ

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

Первая глава является теоретической, в ней рассмотрены понятия, связанные с делимостью целых чисел, которые изучаются в математике младшей и средней школы на интуитивном уровне.
В дальнейшем будем считать известными основные свойства арифметических действий над целыми числами, а также простейшие свойства равенств и неравенств. Под «числом» всегда, если не оговорено противное, далее будет пониматься целое число.
При изучении обстоятельств, связанных с делением целых чисел, одним из первых встает вопрос о выполнимости этого действия для данных двух чисел, т.е. о делимости этих чисел. При рассмотрении остальных арифметических действий над целыми числами подобный вопрос, очевидно, не возникает.
Определение 1.1. Число a делится на число 13 QUOTE 1415 (или, что то же самое, число 13 QUOTE 1415 делит число 13 QUOTE 1415), если существует такое число x, что 13 QUOTE 1415. Например: 6 делится на 3, так как 13 QUOTE 1415;
·15 делится на 5, так как 13 QUOTE 1415.
Этот факт называется делимостью числа а на число 13 QUOTE 1415 и обозначается как 13 QUOTE 1415. Запись 13 QUOTE 1415 означает не какое-то действие, которое надлежит произвести над числами а и b, а некоторое утверждение, касающееся этих чисел. Например: 13 QUOTE 1415
Деление целых чисел выполнимо не всегда. Поэтому целесообразно наряду с действием деления рассматривать и другое, более общее действие, которое всегда выполнимо, а в случае выполнимости действия деления, по существу, совпадает с ним. Таким действием является деление с остатком.
Определение 1.2. Разделить число а на число b (b>0) с остатком значит представить число а в виде 13 QUOTE 1415Число 13 QUOTE 1415 при этом называется неполным частным, а число 13 QUOTE 1415 остатком от деления a на 13 QUOTE 1415. Очевидно, 13 QUOTE 1415 тогда и только тогда, когда 13 QUOTE 1415. В этом случае x равно частному от деления а на b. Например, разделим 17 на 3: 13 QUOTE 1415, здесь 5 – неполное частное, 2 – остаток от деления 17 на 3.
Можно доказать, что для произвольных чисел a и b (b
·0) справедлива теорема о делении с остатком.
Теорема 1.1. (о делении с остатком). Для произвольных чисел a и b (b
·0) существуют и единственны такие числа r и x что 13 QUOTE 1415, причем 13 QUOTE 1415.
В связи с ограничениями, по количеству страниц доказательство теоремы о делении с остатком не привожу.
В частности из этой теоремы следует, что если b
·1, то должно быть r
·0, откуда x
·a, если b
·1, то x
·a.
Всякое число, делящее одновременно числа a и b, называется общим делителем этих чисел. Наибольший из общих делителей чисел a и b называется их наибольшим общим делителем и обозначают НОД(a, b).
Если наибольший общий делитель чисел а и b равен единице, то эти числа называются взаимно простыми. Иначе говоря, числа a и b называются взаимно простыми, если они одновременно не делятся ни на какое число кроме единицы.
Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m.
Определение 1.3. Если двум целым а и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m или сравнимыми по модулю m. Например: 13 QUOTE 1415 поэтому 17 и 14 сравнимы по модулю 3.
Сравнимость чисел a и b по модулю m записывается так: 13 QUOTE 1415, что читается: a сравнимо с b по модулю m.
Очевидно, что запись 13 QUOTE 1415, не имеет смысла, так как нельзя рассматривать остатки от деления числа b на 0 (делить на 0 нельзя).
Из определения сравнимых по модулю чисел следует, что:
13 QUOTE 1415, для любого числа а, так как любое число делится на 1 без остатка (или остаток от деления a на 1 равен 0);
если 13 QUOTE 1415, то 13 QUOTE 1415 Верно и обратное, если 13 QUOTE 1415, то 13 QUOTE 1415.
13 QUOTE 1415 для любого k (остаток от деления km на m равен 0);
если r – остаток от деления a на m, то 13 QUOTE 1415 (любое число сравнимо со своим остатком);
если 13 QUOTE 1415, то 13 QUOTE 1415 (свойство симметричности);
13 QUOTE 1415 (свойство рефлективности);
если13 QUOTE 1415 и 13 QUOTE 1415, то 13 QUOTE 1415 (свойство транзитивности).
Сравнения обладают и другими свойствами. Рассмотрим только некоторые из них, необходимые для понимания дальнейшего изложения, не нарушая целостности теории.
Свойство 1.1. Если число а можно представить в виде13 QUOTE 1415, где t целое, то 13 QUOTE 1415 Верно и обратное утверждение: если 13 QUOTE 1415, то a можно представить в виде 13 QUOTE 1415, где t целое.
Доказательство.
Число b можно представить в виде 13 QUOTE 1415 13 QUOTE 1415, тогда r – остаток от деления b на m (Определение 1.2.). Так, как 13 QUOTE 1415, то подставив в это равенство выражение для b, получим 13 QUOTE 1415, 13 QUOTE 1415.
Следовательно, двум целым а и b отвечает один и тот же остаток r от деления на m. Значит 13 QUOTE 1415.
Докажем обратное утверждение: если 13 QUOTE 1415, то 13 QUOTE 1415, где t целое.
Так, как 13 QUOTE 1415, то 13 QUOTE 1415 и 13 QUOTE 1415, (Определение 1.3). Из второго равенства выразим r: 13 QUOTE 1415. Подставив в первое равенство, получим: 13 QUOTE 1415, где 13 QUOTE 1415 целое. Следовательно, если 13 QUOTE 1415, то 13 QUOTE 1415, где t целое.
Что и требовалось доказать.
Пример: так как 13 QUOTE 1415 Так как 13 QUOTE 1415, то 13 QUOTE 1415 где t – целое (в данном случае t
·
·2).
Выражение «верно и обратное утверждение» буду заменять общепринятым «тогда и только тогда», что обозначается “13 QUOTE 1415”.
Свойство 1.2. 13 QUOTE 1415 13 QUOTE 1415 13 QUOTE 1415.
Доказательство.
Так, как 13 QUOTE 1415 (Свойство 1.1), то 13 QUOTE 1415, следовательно 13 QUOTE 1415 (Определение 1.1).
Что и требовалось доказать.

Арифметика сравнений

Сравнения обладают свойствами, подобными свойствам уравнений и неравенств, позволяющими выполнять над ними арифметические операции.
Свойство 2.1. Сравнения можно почленно складывать. Если 13 QUOTE 1415 и 13 QUOTE 1415, то 13 QUOTE 1415.
Доказательство.
Так как 13 QUOTE 1415, то 13 QUOTE 1415, где 13 QUOTE 1415, а так как 13 QUOTE 1415, то 13 QUOTE 1415 где 13 QUOTE 1415. Поэтому 13 QUOTE 1415, где 13 QUOTE 1415. Следовательно, 13 QUOTE 1415.
Что и требовалось доказать.
Свойство 2.2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.
Доказательство.
Пусть 13 QUOTE 1415. Сложим его с очевидным сравнением 13 QUOTE 1415 (Свойство 2.1), тогда 13 QUOTE 1415.
Что и требовалось доказать.
Остальные свойства сравнений доказываются аналогично, поэтому, чтобы не перегружать работу, приведу их без доказательства.
Свойство 2.3. Сравнения можно почленно вычитать. Если13 QUOTE 1415 и 13 QUOTE 1415 13 QUOTE 1415, то 13 QUOTE 1415.
Свойство 2.4. К любой части сравнения можно прибавить любое число, кратное модулю. Если 13 QUOTE 1415, то 13 QUOTE 1415
Свойство 2.5. Сравнения можно почленно перемножать. Если 13 QUOTE 1415 и 13 QUOTE 1415, то 13 QUOTE 1415.
Свойство 2.6. Обе части сравнения можно умножить на одно и то же число. Если 13 QUOTE 1415, то 13 QUOTE 1415.
Свойство 2.7. Обе части сравнения можно возвести в одну и ту же степень. Если13 QUOTE 1415, то 13 QUOTE 1415.
Свойство 2.8 (следствие Свойств 2.1 – 2.7). Если в выражении многочлена с целыми коэффициентами 13 QUOTE 1415 заменим 13 QUOTE 1415числами 13 QUOTE 1415 сравнимыми с прежними по модулю m, то новое выражение 13 QUOTE 1415 будет сравнимо с прежним по модулю m.
Свойство 2.9. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем. Если 13 QUOTE 1415, НОД(a, b)
·k и НОД(k, m)
·1, то 13 QUOTE 141513 QUOTE 1415.
Доказательство.
Пусть 13 QUOTE 1415, НОД(a, b)
·k, НОД(k, m)
·1, тогда 13 QUOTE 1415, 13 QUOTE 1415, поэтому:  13 QUOTE 1415 (Свойство 1.2). Так, как НОД(k, m)
·1, то 13 QUOTE 1415 только в том случае, если 13 QUOTE 1415, следовательно, 13 QUOTE 1415, или 13 QUOTE 1415.
Что и требовалось доказать.
Свойство 2.10. Если сравнение a с b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей. Если 13 QUOTE 1415, то 13 QUOTE 1415, где m
·НОК(m1, m2).
Доказательство.
Если 13 QUOTE 1415, то 13 QUOTE 1415 делится на m1 и m2. Значит 13 QUOTE 1415 делится на m
·НОК(m1, m2). Следовательно 13 QUOTE 1415.
Что и требовалось доказать.
Поскольку сравнения по модулю m тесно связаны с остатками от деления на m, почти все задачи, в которых речь идет о делимости чисел, можно решать с помощью сравнений.
Пример 2.1. Найдем признаки делимости на 4.
Пусть дано произвольное натуральное число a, десятичная запись которого 13 QUOTE 1415, где an, an
·1,,a1, a0 – цифры числа a.
Запишем a в развернутой форме: 13 QUOTE 1415.
Так как 13 QUOTE 1415, если 13 QUOTE 1415, то 13 QUOTE 1415. Следовательно, целое число при делении на 4 «ведет себя» так же, как и число, составленное из его двух последних цифр. Поэтому, если число, составленное из двух последних цифр данного числа, делится на 4, то и само число делится на 4.
Так как 13 QUOTE 1415, то 13 QUOTE 1415 Поэтому, если сумма удвоенной предпоследней и последней цифр данного числа делится на 4, то и само число делится на 4.

Арифметика вычетов по модулю m

Пусть m
·1 – произвольное натуральное число. При делении на m могут получиться m различных остатков: 0, 1, 2, ....m
·1.
Пусть r – остаток от деления a на m, тогда a
·mx
·r (Определение 1.2), следовательно, a
·r
·mx, поэтому 13 QUOTE 1415 (Определение 1.1), значит, 13 QUOTE 1415 (Свойство 1.2).
В связи с этим возникает идея рассматривать сравнения не на всем бесконечном множестве целых чисел, а на конечном множестве остатков от деления на m. Тогда любому целому числу a будет соответствовать определенный остаток r из конечного множества остатков, который будем называть вычетом по модулю m, или просто вычетом.
Очевидно, что каждому вычету r соответствует бесконечно много целых чисел, которые при делении на m дают остаток равный r.
Определение 3.1. Введем на множестве остатков от деления на m действия сложения и умножения. Суммой (соответственно, произведением) двух остатков a и b назовем остаток от деления на m обычной суммы (произведения) чисел a и b.
Для любых остатков а, b и c очевидно верны следующие свойства:
13 QUOTE
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·–
·
·
·
·
·–
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Справедливость этих свойств следует из аналогичных свойств действий над целыми числами и свойств сравнений.
Арифметику остатков от деления на m (арифметику вычетов по модулю m) принято называть m – арифметикой. Таким образом, в m – арифметике, мы ограничили значения чисел, сравнимых по модулю m только возможными остатками от деления этих чисел на m. Следовательно, все теоремы, выполняющиеся для арифметики сравнений, будут выполняться и в m – арифметике. m – арифметика отличается от обычной арифметики, изучаемой в школе, но во многом похожа на нее. Эта новая арифметика оказывается очень полезной при решении многих задач из обычной арифметики и алгебры. Поскольку в m – арифметики все действия выполняются над m – числами, то в дальнейшем будем m – число (вычет по модулю m) обозначать, как a (как в обычной арифметике), во всех случаях, когда это не приведет к путанице.
Используя определение 3.1, можно составить таблицы сложения и умножения для любой m – арифметики. Таблицы сложения и умножения для 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11 – арифметик приведены в Приложении 1.
Рассмотрев таблицы сложения в m – арифметиках, замечаем, что:
для каждого числа a существует число (
·a), такое, что a
·(
·a)
·0 (например, в 7 – арифметике:
·3
·4, так как 3
·4
·0;
·5
·2, так как 5
·2
·0; в 10 – арифметике:
·8
·2,
·7
·3). Число (
·a) называют противоположным числу a. Следовательно, в m – арифметике любое число можно записывать в двух разных формах со знаком минус и без него.
Найти число, противоположное числу а в m – арифметике просто: нужно из m вычесть a. Например, найдем число противоположное 7 в 13 – арифметике:
·7
·13
·7
·6. Эта запись не является верной с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Описанный выше метод нахождения противоположного числа в m – арифметике основывается на Свойстве 2.4. (если 13 QUOTE 1415, то 13 QUOTE 141513 QUOTE 1415).
В Таблице 3.1. приведены противоположные числа в 13 – арифметике.

Таблица 3.1. Противоположные числа в 13 – арифметике

a
0
1
2
3
4
5
6
7
8
9
10
11
12


·a
0
12
11
10
9
8
7
6
5
4
3
2
1


Таблицы противоположных чисел для 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11 – арифметик приведены в Приложении 1.
Противоположные числа в m – арифметике обладают свойствами, подобными свойствам отрицательных чисел в обычной арифметике:
13 QUOTE 1415;
13 QUOTE 1415.
Например, в 7 – арифметике:
·3
·4,
·5
·2, 13 QUOTE 1415 и 13 QUOTE 1415; в 10 – арифметике:
·8
·2,
·7
·3, 13 QUOTE 1415 и 13 QUOTE 1415).
Используя свойство 3.8, определим операцию вычитания в m – арифметике:a
·b
·a
·(
·b).
При вычислении разности в m – арифметике можно использовать следующий прием: из уменьшаемого вычесть вычитаемое и, если результат получился отрицательный, прибавить m. Этот прием основан на Свойстве 2.4. (если 13 QUOTE 1415, то 13 QUOTE 141513 QUOTE 1415). Например, вычислим 7
·19 в 23 – арифметике: 7
·19
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях.
m – арифметика обладает очень важным свойством: если в любом верном числовом равенстве из обыкновенной арифметики, содержащем, кроме чисел, только знаки сложения, вычитания, умножения и скобки, заменить каждое число его остатком от деления на m, то получим равенство, верное в смысле m – арифметики. (Это утверждение следует из Свойства 2.8). Само собой разумеется, что показатель степени не следует заменять остатком от деления на m. Показатель степени играет в формуле другую роль, нежели числа, не являющиеся показателями: он есть просто сокращенное обозначение того, сколько раз надо взять сомножителем основание степени. Пример: из верных равенств: 13 QUOTE 1415; 13 QUOTE 1415 13 QUOTE 1415 мы получаем этим способом верные 10 – арифметические равенства: 13 QUOTE 1415 13 QUOTE 1415; 13 QUOTE 1415.
Рассматривая таблицы умножения (Приложение 1), замечаем, что для некоторых m – арифметик произведение не нулевых чисел может быть равно нулю (например, в 4 – арифметике: 13 QUOTE 1415; в 6 – арифметике: 13 QUOTE 1415; в 10 – арифметике: 13 QUOTE 141513 QUOTE 1415, 13 QUOTE 1415; и т.д.). В таких случаях говорят, что в m – арифметике имеются делители нуля, т.е. такие числа 13 QUOTE 1415 и 13 QUOTE 1415, что ab
·0.
Анализируя таблицы умножения (Приложение 1) m – арифметик, замечаем, что:
делителями нуля являются числа, не взаимно простые с m (т.е. имеющие с m общие делители отличные от единицы). Например, в 4 – арифметике: 13 QUOTE 1415; в 10 – арифметике: 13 QUOTE 1415 13 QUOTE 1415, 13 QUOTE 1415
среди ненулевых остатков по модулю m, взаимно простых с m нет делителей нуля.
Доказательство.
Предположим, что найдутся два остатка a и b по модулю m, такие, что 13 QUOTE 1415, 13 QUOTE 1415 и НОД(a, m)
·1, НОД(b, m)
·1, но ab
·0 в m – арифметике.
Это значит, что число ab делится на m, поскольку НОД(a, m)
·1, то 13 QUOTE 1415, следовательно, 13 QUOTE 1415. Пришли к противоречию, следовательно, среди ненулевых остатков по модулю m, взаимно простых с m нет делителей нуля.
Что и требовалось доказать.
Из свойства 3.10 следует, что если a – взаимно просто с m, 13 QUOTE 1415 и 13 QUOTE 1415, то 13 QUOTE 1415 Но тогда все элементы вида a, 2a,,(m
·1)a различны и, следовательно, среди них есть только один элемент равный единице. Это значит, что:
если 13 QUOTE 1415 и a – взаимно просто с m, то существует такой остаток b, для которого ab
·1 (например, в 3 – арифметике: 13 QUOTE 1415; в 4 – арифметике: 13 QUOTE 1415; в 5 – арифметике: 13 QUOTE 1415; и т.д.). Такой остаток обозначают 13 QUOTE 1415 или 13 QUOTE 1415 и называют обратным к a. Если же 13 QUOTE 1415, то остатка обратному к a не существует (делители нуля не имеют обратных элементов).
Очевидно, что если для некоторых двух остатков a и b верно равенство a
·1
·b
·1, то a
·b.
Когда числа маленькие, то для нахождения обратных чисел можно применить простой приём: добавлять к числителю (или вычитать из числителя) величину модуля m, пока числитель не поделится нацело. Частное и будет искомым обратным. Например, найдем 2
·1 в 13 – арифметике: 13 QUOTE 1415. Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Описанный выше прием для нахождения обратных чисел основывается на Свойстве 2.4. (если 13 QUOTE 1415, то 13 QUOTE 1415) и Свойстве 2.9.(обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем).
В Таблице 3.2. приведены обратные числа в 13 – арифметике.

Таблица 3.2. Обратные числа в 13 – арифметике.

a
1
2
3
4
5
6
7
8
9
10
11
12

a-1
1
7
9
10
8
11
2
5
3
4
6
12


Таблицы обратных чисел для 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11 – арифметик приведены в Приложении 1.
Обратные числа в m – арифметике обладают следующими свойствами:
(a
·1)
·1=a;
(
·a)
·1
·
·a
·1;
(ab)
·1
·a
·1b
·1.
Используя свойство 3.11, определим операцию деления в m – арифметике: 13 QUOTE 1415, где 13 QUOTE 1415 и b не является делителем нуля (b взаимно просто с m). В m – арифметике нельзя делить на 0 и на делители нуля, поскольку в последнем случае получим не однозначный результат.
При вычислении частного в m – арифметике можно для малых чисел использовать тот же прием, что и при нахождении обратного: добавлять к числителю (или вычитать из числителя) величину модуля m, пока числитель не поделится нацело. Полученное частное и будет искомым. Например, найдем 13 QUOTE 1415 в 13 – арифметике: 13 QUOTE 1415. Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Этот способ нахождения частного в m – арифметике основывается на Свойстве 2.4 (если 13 QUOTE 1415, то 13 QUOTE 1415) и Свойстве 2.9 (обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем).
При выполнении деления в m – арифметике можно использовать следующее полезное равенство: 13 QUOTE 1415, где n – взаимно просто с m.
Очевидно, что если модуль – простое число, то в такой арифметике делителей нуля нет (все остатки взаимно просты с модулем), в этом случае деление на любой не равный нулю остаток всегда выполнимо. Такую арифметику принято называть p – арифметикой. Примеры p – арифметик: 2, 3, 5, 7, 11, 13, и т.д. арифметики.
Деление в p – арифметике обладают свойствами, подобными свойствам деления в обычной арифметике.
Арифметику вычетов точно так же, как и сравнения по модулю, можно использовать для решения задач на делимость. Для этого нужно все данные числа заменить остатками и выполнять над ними арифметические действия, по правилам m – арифметики.
Пример 3.1. Вычислим 3100 в 7 – арифметике: 13 QUOTE 1415
13 QUOTE 1415 Следовательно, 13 QUOTE 1415 13 QUOTE 1415. Остаток от деления 3100 на 7 равен 4.
Пример 3.2. Найдем остаток от деления 21000 на 5. Вычислим 21000 в 5 – арифметике: 13 QUOTE 1415 Следовательно, 13 QUOTE 1415 Поэтому остаток от деления 21000 на 5 равен 1.
Пример 3.3. Делится ли 13 QUOTE 1415 на 2014?
13 QUOTE 1415поэтому в 2014 – арифметике число 2013 будет записываться как
·1, тогда 13 QUOTE 1415. Следовательно, 13 QUOTE 1415 делится на 2014.
Пример 3.4. Доказать, что при любом натуральном n число 37n
·2
·16n
·1
·23n делится на 7.
Рассмотрим данное выражение в 7 – арифметике. 13 QUOTE 1415; 13 QUOTE 1415 13 QUOTE 1415, следовательно, данное выражение в 7 – арифметике будет записано так: 13 QUOTE 1415. Тогда 13 QUOTE 1415.
Поэтому 37n
·2
·16n
·1
·23n делится на 7.
Решение линейных диофантовых уравнений

m – арифметику можно использовать для решения уравнений с целыми коэффициентами в целых числах. Эти уравнения называют диофантовыми, по имени древнегреческого математика Диофанта Александрийского, который впервые рассмотрел уравнения такого типа и методы их решения в своей работе «Арифметика».
Определение 4.2. Уравнение вида ax
·by
·c, где a, b, c – целые, x, y – неизвестные называют линейным диофантовым уравнением с двумя неизвестными. Если НОД(a, b, c)=1 (коэффициенты уравнения взаимно просты), то уравнение называют приведенным. Решить диофантово уравнение, значит найти все целые значения x и y, при которых уравнение обращается в верное равенство, или доказать, что решений нет.
Теорема 4.2. Если в приведенном линейном диофантовом уравнении ax
·by
·c (1), 13 QUOTE 1415 (a и b не взаимно простые), то уравнение (1) не имеет решений.
Доказательство.
Пусть 13 QUOTE 1415, тогда 13 QUOTE 1415, 13 QUOTE 1415, тогда, подставив в уравнение (1) получим: 13 QUOTE 1415. Следовательно, 13 QUOTE 1415, или 13 QUOTE 1415 .
13 QUOTE 1415 – целое. Так как уравнение (1) приведенное, то НОД(a, b, c)=1, следовательно 13 QUOTE 1415 – не может быть целым. Пришли к противоречию, поэтому если в приведенном линейном диофантовом уравнении ax
·by
·c, a и b не взаимно простые, то уравнение не имеет решений.
Что и требовалось доказать.
Рассмотрим решение линейных диофантовых уравнений с двумя неизвестными в m – арифметике.
Пусть ax
·by
·c – приведенное уравнение, 13 QUOTE 1415, тогда, перейдя к вычетам по модулю b, получим: 13 QUOTE 1415 где 13 QUOTE 1415 – остаток от деления a на b, 13 QUOTE 1415 - остаток от деления c на b, 13 QUOTE 1415 – решение уравнения в арифметике вычетов по модулю b. Согласно определению операции деления в m – арифметике, 13 QUOTE 1415 – всегда существует и, причем только одно, равное частному от деления 13 QUOTE 1415 на 13 QUOTE 1415, в арифметике вычетов по модулю b, т.е. 13 QUOTE 1415.
Пусть 13 QUOTE 1415 найдено, тогда 13 QUOTE 1415 (3) (Свойство 1.1), где 13 QUOTE 1415. Выразим из исходного уравнения y: 13 QUOTE 1415. Подставив в последнее равенство выражение для x (3), получим: 13 QUOTE 1415, 13 QUOTE 1415
Пример 4.1. Решить уравнение 14x
·10y
·6 в целых числах.
Разделим обе части данного уравнения на 2: 7x
·5y
·3 (1).
Запишем полученное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например, 5. Тогда: 13 QUOTE 1415, или 13 QUOTE 1415.
Переменные записываем с чертой вверху, поскольку это не переменная, значение которой нужно найти, а ее вычет по модулю 5.
Следовательно, 13 QUOTE 1415. Поэтому 13 QUOTE 1415
Выразим из уравнения (1) y: 13 QUOTE 1415 и, подставив в него найденное выражение для x (2), получим: 13 QUOTE 1415
Ответ: 13 QUOTE 1415.
Пример 4.2. Решить уравнение 39x
· 22y
· 10 в целых числах.
Поступим так же, как и в Примере 4.4. Запишем данное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например 22: 13 QUOTE 1415, или 13 QUOTE 1415.
Следовательно, 13 QUOTE 1415.
Найдем 17
·1 в 22 – арифметике: 13 QUOTE 1415 13 QUOTE 1415
·
·9
·13 Следовательно, 17
·1
·13.
Тогда, 13 QUOTE 1415 13 QUOTE 1415.
Выразим из исходного уравнения y и подставим в полученное равенство найденное значение x: 13 QUOTE 1415
Ответ: 13 QUOTE 1415.
Пример 4.3. Решить уравнение 26x
· 34y
· 13 в целых числах.
Данное уравнение приведенное НОД(26, 34, 13)=1. Так как 13 QUOTE 1415, то оно не имеет решений в целых числах (Теорема 4.2).
Ответ: решений нет.
Пример 4.4. Решить уравнение 43x
· 37y
· 21 в целых числах.
Запишем данное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например 43: 13 QUOTE 1415, или 13 QUOTE 1415. Тогда, 13 QUOTE 1415, 13 QUOTE 1415.
Выразим из исходного уравнения x, и подставим в полученное равенство найденное значение y: 13 QUOTE 1415
Ответ: 13 QUOTE 1415
ЗАКЛЮЧЕНИЕ

Арифметика вычетов один из тех разделов математики, которые зарождались как некоторые формальные рассуждения, и только спустя годы нашли свое практическое применение.
В моей работе рассмотрены методы решения задач, связанных с делением целых чисел и решением уравнений в целых числах с помощью арифметики вычетов.
Материалы данной работы могут быть использованы при подготовке к олимпиадам по математике и ЕГЭ, при проведении внеклассных мероприятий с целью развития и расширения познавательного кругозора, развития логического мышления.
Были решены поставленные задачи: построена система аксиом, необходимая для доказательства свойств вычетов, изучены и доказаны свойства вычетов, решены задачи на доказательство делимости целых чисел и получены общие методы решения линейных диофантовых уравнения с двумя неизвестными. Результаты работы оформлены в виде текста проекта и презентации.
Была достигнута цель исследования: рассмотрены методы решения задач, связанных с делением целых чисел и решением уравнений в целых числах в аспекте их реализации при подготовке к олимпиадам разного уровня.
Гипотеза: изучение свойств арифметики вычетов позволит определить общие методы решения олимпиадных задач, связанных с делением целых чисел и решением уравнений в целых числах – подтвердилась.
Работа над этим проектом позволила занять мне второе место в районном этапе Всероссийской олимпиады школьников и стать призером отборочного этапа международной олимпиады «Покори Воробьевы горы!» (Приложение 2).

СПИСОК ЛИТЕРАТУРЫ

Дынкин Е. Б., Успенский В. А. Математические беседы. – М., Л: Государственное издательство технико – теоретической литературы, 1952.
Виленкин Н. Сравнения и классы вычетов // Квант – 1978. - №10. С. – 4 – 9.
Геронимус А. Сравнения по простому модулю // Квант – 1978. - №11. С. – 6 – 11.
Геронимус А. Диофантовы уравнения по простому модулю // Квант – 1978. - №12. С. – 2 – 7.
Спивак А. В. Арифметика. – М.: Бюро Квантум, 2007.
Спивак А. В. Арифметика – 2. – М.: Бюро Квантум, 2008.
Воробьев Н. Н. Признаки делимости. – М., Наука. Гл. ред. физ. – мат. лит., 1988.

ПРИЛОЖЕНИЕ

Таблицы сложения и умножения в 2-арифметике

+
0
1









x
0
1

0
0
1









0
0
0

1
1
0









1
0
1


Таблицы противоположных и обратных чисел в 2-арифметике

a
0
1

















a
0
1


·a
0
1

















a
·1
-
1


Таблицы сложения и умножения в 3-арифметике

+
0
1
2









x
0
1
2

0
0
1
2









0
0
0
0

1
1
2
0









1
0
1
2

2
2
0
1









2
0
2
1


Таблицы противоположных и обратных чисел в 3-арифметике

a
0
1
2















a
0
1
2


·a
0
2
1















a
·1
-
1
2


Таблицы сложения и умножения в 4-арифметике

+
0
1
2
3








x
0
1
2
3

0
0
1
2
3








0
0
0
0
0

1
1
2
3
0








1
0
1
2
3

2
2
3
0
1








2
0
2
0
2

3
3
0
1
2








3
0
3
2
1


Таблицы противоположных и обратных чисел в 4-арифметике

a
0
1
2
3













a
0
1
2
3


·a
0
3
2
1













a
·1
-
1
-
3


Таблицы сложения и умножения в 5-арифметике

+
0
1
2
3
4





x
0
1
2
3
4

0
0
1
2
3
4





0
0
0
0
0
0

1
1
2
3
4
0





1
0
1
2
3
4

2
2
3
4
0
1





2
0
2
4
1
3

3
3
4
0
1
2





3
0
3
1
4
2

4
4
0
1
2
3





4
0
4
3
2
1





Таблицы противоположных и обратных чисел в 5-арифметике

a
0
1
2
3
4











a
0
1
2
3
4


·a
0
4
3
2
1











a
·1
-
1
3
2
4




Таблицы сложения и умножения в 6-арифметике

+
0
1
2
3
4
5



x
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




Таблицы противоположных и обратных чисел в 6-арифметике

a
0
1
2
3
4
5









a
0
1
2
3
4
5


·a
0
5
4
3
2
1









a
·1
-
1
-
-
-
5




Таблицы сложения и умножения в 7-арифметике

+
0
1
2
3
4
5
6


x
0
1
2
3
4
5
6

0
0
1
2
3
4
5
6


0
0
0
0
0
0
0
0

1
1
2
3
4
5
6
0


1
0
1
2
3
4
5
6

2
2
3
4
5
6
0
1


2
0
2
4
6
1
3
5

3
3
4
5
6
0
1
2


3
0
3
6
2
5
1
4

4
4
5
6
0
1
2
3


4
0
4
1
5
2
6
3

5
5
6
0
1
2
3
4


5
0
5
3
1
6
4
2

6
6
0
1
2
3
4
5


6
0
6
5
4
3
2
1





Таблицы противоположных и обратных чисел в 7-арифметике

a
0
1
2
3
4
5
6







a
0
1
2
3
4
5
6


·a
0
6
5
4
3
2
1







a
·1
-
1
4
5
2
3
6



Таблицы сложения и умножения в 8-арифметике

+
0
1
2
3
4
5
6
7


x
0
1
2
3
4
5
6
7

0
0
1
2
3
4
5
6
7


0
0
0
0
0
0
0
0
0

1
1
2
3
4
5
6
7
0


1
0
1
2
3
4
5
6
7

2
2
3
4
5
6
7
0
1


2
0
2
4
6
0
2
4
6

3
3
4
5
6
7
0
1
2


3
0
3
6
1
4
7
2
5

4
4
5
6
7
0
1
2
3


4
0
4
0
4
0
4
0
4

5
5
6
7
0
1
2
3
4


5
0
5
2
7
4
1
6
3

6
6
7
0
1
2
3
4
5


6
0
6
4
2
0
6
4
2

7
7
0
1
2
3
4
5
6


7
0
7
6
5
4
3
2
1


Таблицы противоположных и обратных чисел в 8-арифметике

a
0
1
2
3
4
5
6
7





a
0
1
2
3
4
5
6
7


·a
0
7
6
5
4
3
2
1





a
·1
-
1
-
3
-
5
-
7


Таблицы сложения и умножения в 9-арифметике

+
0
1
2
3
4
5
6
7
8


x
0
1
2
3
4
5
6
7
8

0
0
1
2
3
4
5
6
7
8


0
0
0
0
0
0
0
0
0
0

1
1
2
3
4
5
6
7
8
0


1
0
1
2
3
4
5
6
7
8

2
2
3
4
5
6
7
8
0
1


2
0
2
4
6
8
1
3
5
7

3
3
4
5
6
7
8
0
1
2


3
0
3
6
0
3
6
0
3
6

4
4
5
6
7
8
0
1
2
3


4
0
4
8
3
7
2
6
1
5

5
5
6
7
8
0
1
2
3
4


5
0
5
1
6
2
7
3
8
4

6
6
7
8
0
1
2
3
4
5


6
0
6
3
0
6
3
0
6
3

7
7
8
0
1
2
3
4
5
6


7
0
7
5
3
1
8
6
4
2

8
8
0
1
2
3
4
5
6
7


8
0
8
7
6
5
4
3
2
1



Таблицы противоположных и обратных чисел в 9-арифметике

a
0
1
2
3
4
5
6
7
8



a
0
1
2
3
4
5
6
7
8


·a
0
8
7
6
5
4
3
2
1



a
·1
-
1
5
-
7
2
-
4
8




Таблицы сложения и умножения в 10-арифметике

+
0
1
2
3
4
5
6
7
8
9


x
0
1
2
3
4
5
6
7
8
9

0
0
1
2
3
4
5
6
7
8
9


0
0
0
0
0
0
0
0
0
0
0

1
1
2
3
4
5
6
7
8
9
0


1
0
1
2
3
4
5
6
7
8
9

2
2
3
4
5
6
7
8
9
0
1


2
0
2
4
6
8
0
2
4
6
8

3
3
4
5
6
7
8
9
0
1
2


3
0
3
6
9
2
5
8
1
4
7

4
4
5
6
7
8
9
0
1
2
3


4
0
4
8
2
6
0
4
8
2
6

5
5
6
7
8
9
0
1
2
3
4


5
0
5
0
5
0
5
0
5
0
5

6
6
7
8
9
0
1
2
3
4
5


6
0
6
2
8
4
0
6
2
8
4

7
7
8
9
0
1
2
3
4
5
6


7
0
7
4
1
8
5
2
9
6
3

8
8
9
0
1
2
3
4
5
6
7


8
0
8
6
4
2
0
8
6
4
2

9
9
0
1
2
3
4
5
6
7
8


9
0
9
8
7
6
5
4
3
2
1



Таблицы противоположных и обратных чисел в 10-арифметике

a
0
1
2
3
4
5
6
7
8
9

a
0
1
2
3
4
5
6
7
8
9


·a
0
9
8
7
6
5
4
3
2
1

a
·1
-
1
-
7
-
-
-
3
-
9



Таблица сложения в 11-арифметике

+
0
1
2
3
4
5
6
7
8
9
10

0
0
1
2
3
4
5
6
7
8
9
10

1
1
2
3
4
5
6
7
8
9
10
0

2
2
3
4
5
6
7
8
9
10
0
1

3
3
4
5
6
7
8
9
10
0
1
2

4
4
5
6
7
8
9
10
0
1
2
3

5
5
6
7
8
9
10
0
1
2
3
4

6
6
7
8
9
10
0
1
2
3
4
5

7
7
8
9
10
0
1
2
3
4
5
6

8
8
9
10
0
1
2
3
4
5
6
7

9
9
10
0
1
2
3
4
5
6
7
8

10
10
0
1
2
3
4
5
6
7
8
9





Таблица умножения в 11-арифметике

x
0
1
2
3
4
5
6
7
8
9
10

0
0
0
0
0
0
0
0
0
0
0
0

1
0
1
2
3
4
5
6
7
8
9
10

2
0
2
4
6
8
10
1
3
5
7
9

3
0
3
6
9
1
4
7
10
2
5
8

4
0
4
8
1
5
9
2
6
10
3
7

5
0
5
10
4
9
3
8
2
7
1
6

6
0
6
1
7
2
8
3
9
4
10
5

7
0
7
3
10
6
2
9
5
1
8
4

8
0
8
5
2
10
7
4
1
9
6
3

9
0
9
7
5
3
1
10
8
6
4
2

10
0
10
9
8
7
6
5
4
3
2
1



Таблицы противоположных и обратных чисел в 11-арифметике

a
0
1
2
3
4
5
6
7
8
9
10

a
0
1
2
3
4
5
6
7
8
9
10


·a
0
10
9
8
7
6
5
4
3
2
1

a
·1
-
1
6
4
3
9
2
8
7
5
10











13PAGE \* MERGEFORMAT142615


ПЛАН РАБОТЫ

ВВЕДЕНИЕ

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

Арифметика сравнений

Арифметика вычетов по модулю m

Решение линейных диофантовых уравнений

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Приложение 1

Приложение 2