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

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ БЕЛОЯРОСКОГО РАЙОНА «СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №3 г. БЕЛОЯРСКИЙ»
Проект в номинации №7. «Нерешенные задачи и как их решать – теоретические исследования сформулированных проблем в различных отраслях знания»
Тема проекта:
«Использование арифметики вычетов для решения олимпиадных задач»
	Автор:
	Матусевич Кирилл Викторович
	Класс: 8 б
	Научный руководитель проекта:
	Товстоног Елена Анатольевна
	«Общеобразовательная средняя
	(полная) школа № 3
	г. Белоярский»
	учитель математики
Белоярский
2015

Содержание

ПЛАН РАБОТЫ... 3

ВВЕДЕНИЕ.. 4

ОСНОВНАЯ ЧАСТЬ.. 5

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

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

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

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

ЗАКЛЮЧЕНИЕ.. 19

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

ПРИЛОЖЕНИЕ.. 21

ПЛАН РАБОТЫ

Методы работы:

·        изучение литературы;

·        построение системы аксиом, необходимых для доказательства свойств арифметики вычетов;

·        доказательство свойств арифметики вычетов и решение на их основе олимпиадных задач.

Сроки проведения работы: с сентября по февраль 2014-2015 учебного года.

Этапы работы:

·        1 этап – изучение проблемы (сентябрь);

·        2 этап – сбор информации по проблеме (октябрь);

·        3 этап – обработка и анализ информации (ноябрь);

·        4 этап – оформление документации (декабрь, январь);

·        5 этап – презентация учебного проекта (февраль).

Предмет исследования: методы решения задач, связанных с делением целых чисел и решением уравнений в целых числах.

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

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

Задачи исследования:

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

-       изучить свойства вычетов;

-       научиться решать задачи на доказательство делимости целых чисел;

-       научиться решать линейные диофантовы уравнения с двумя неизвестными;

-       оформить результаты исследования.

Предполагаемые результаты: научиться решать задачи на доказательство делимости целых чисел; научится решать линейные диофантовы уравнения с двумя неизвестными, с помощью арифметики вычетов.

 

ВВЕДЕНИЕ

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

Делимость чисел и решение управней в целых числах рассматривается в рамках одного из разделов математики – теории чисел. Основы теории чисел зародились еще в Древнем Египте и Вавилоне. Вавилонские клинописные математические тексты включают таблицы умножения и обратных чисел, квадратов и кубов чисел натурального ряда. Самой древней археологической находкой в истории арифметики является обломок глиняной таблички, датируемый 1800 годами до нашей эры. Он содержит список Пифагоровых троек. Весомый вклад в становление теории чисел внесли Евклид, Диофант и пифагорейцы. Пифагорейцы рассматривали только целые положительные числа и полагали число собранием единиц. Единицы были неделимы и располагались в виде правильных геометрических тел. Пифагорейцам характерно определение «фигурных чисел» («треугольных», «квадратных» и других). Изучая свойства чисел, они разбили их на чётные и нечётные, простые и составные. Пифагорейцы нашли бесконечное множество целых решений уравнения a²+b²=c², так называемых пифагоровых троек, и вывели для них общую формулу. Евклид посвятил несколько книг «Начал» теории делимости, в основе этой теории лежит алгоритм Евклида для нахождения общего наибольшего делителя двух чисел. Следствием алгоритма является возможность разложения любого числа на простые сомножители, а также единственность такого разложения. Диофант в своем труде «Арифметика» перечислил задачи по нахождению целочисленных решений для уравнений (называемых сейчас диофантовыми).

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

Любая научная теория, в том числе и математическая, строится на основе определенной системы аксиом (исходных положений, принимаемых в рамках данной теории истинными без требования доказательства и используемых в основе доказательства других ее положений). Поскольку моя работа затрагивает достаточно узкий круг вопросов, я постарался минимизировать понятийный аппарат, используемый в работе, стараясь сохранить целостность логики теоретического изложения.

ОСНОВНАЯ ЧАСТЬ

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

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

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

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

Определение 1.1. Число a делится на число  (или, что то же самое, число  делит число ), если существует такое число x, что . Например: 6 делится на 3, так как ; -15 делится на 5, так как .

Этот факт называется делимостью числа а на число  и обозначается как . Запись  означает не какое-то действие, которое надлежит произвести над числами а и b, а некоторое утверждение, касающееся этих чисел. Например:

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

Определение 1.2. Разделить число а на число b (b>0) с остатком — значит представить число а в виде Число  при этом называется неполным частным, а число  — остатком от деления a на . Очевидно,  тогда и только тогда, когда . В этом случае x равно частному от деления а на b. Например, разделим 17 на 3: , здесь 5 – неполное частное, 2 – остаток от деления 17 на 3.

Можно доказать, что для произвольных чисел a и b (b>0) справедлива теорема о делении с остатком.

Теорема 1.1. (о делении с остатком). Для произвольных чисел a и b (b>0) существуют и единственны такие числа r и x что , причем .

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

В частности из этой теоремы следует, что если 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. Например:  поэтому 17 и 14 сравнимы по модулю 3.

Сравнимость чисел a и b по модулю m записывается так: , что читается: a сравнимо с b по модулю m.

Очевидно, что запись , не имеет смысла, так как нельзя рассматривать остатки от деления числа b на 0 (делить на 0 нельзя).

Из определения сравнимых по модулю чисел следует, что:

1) , для любого числа а, так как любое число делится на 1 без остатка (или остаток от деления a на 1 равен 0);

2) если , то  Верно и обратное, если , то .

3)  для любого k (остаток от деления km на m равен 0);

4) если r – остаток от деления a на m, то  (любое число сравнимо со своим остатком);

5) если , то  (свойство симметричности);

6)  (свойство рефлективности);

7) если и , то  (свойство транзитивности).

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

Свойство 1.1. Если число а можно представить в виде, где t — целое, то  Верно и обратное утверждение: если , то a можно представить в виде , где t — целое.

Доказательство.

Число b можно представить в виде  , тогда r – остаток от деления b на m (Определение 1.2.). Так, как , то подставив в это равенство выражение для b, получим , .

Следовательно, двум целым а и b отвечает один и тот же остаток r от деления на m. Значит .

Докажем обратное утверждение: если , то , где t — целое.

Так, как , то  и , (Определение 1.3). Из второго равенства выразим r: . Подставив в первое равенство, получим: , где  — целое. Следовательно, если , то , где t — целое.

Что и требовалось доказать.

Пример: так как  Так как , то  где t – целое (в данном случае t=-2).

Выражение «верно и обратное утверждение» буду заменять общепринятым «тогда и только тогда», что обозначается “”.

Свойство 1.2.   .

Доказательство.

Так, как  (Свойство 1.1), то , следовательно  (Определение 1.1).

Что и требовалось доказать.

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

Сравнения обладают свойствами, подобными свойствам уравнений и неравенств, позволяющими выполнять над ними арифметические операции.

Свойство 2.1. Сравнения можно почленно складывать. Если  и , то .

Доказательство.

Так как , то , где , а так как , то  где . Поэтому , где . Следовательно, .

Что и требовалось доказать.

Свойство 2.2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.

Доказательство.

Пусть . Сложим его с очевидным сравнением  (Свойство 2.1), тогда .

Что и требовалось доказать.

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

Свойство 2.3. Сравнения можно почленно вычитать. Если и  , то .

Свойство 2.4. К любой части сравнения можно прибавить любое число, кратное модулю. Если , то

Свойство 2.5. Сравнения можно почленно перемножать. Если  и , то .

Свойство 2.6. Обе части сравнения можно умножить на одно и то же число. Если , то .

Свойство 2.7. Обе части сравнения можно возвести в одну и ту же степень. Если, то .

Свойство 2.8 (следствие Свойств 2.1 – 2.7). Если в выражении многочлена с целыми коэффициентами  заменим числами  сравнимыми с прежними по модулю m, то новое выражение  будет сравнимо с прежним по модулю m.

Свойство 2.9. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем. Если , НОД(a, b)=k и НОД(k, m)=1, то
.

Доказательство.

Пусть , НОД(a, b)=k, НОД(k, m)=1, тогда , , поэтому:
  (Свойство 1.2). Так, как НОД(k, m)=1, то
  только в том случае, если , следовательно, , или .

Что и требовалось доказать.

Свойство 2.10. Если сравнение a с b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей. Если , то , где m=НОК(m₁, m₂).

Доказательство.

Если , то  делится на m₁ и m₂. Значит  делится на m=НОК(m₁, m₂). Следовательно .

Что и требовалось доказать.

Поскольку сравнения по модулю m тесно связаны с остатками от деления на m, почти все задачи, в которых речь идет о делимости чисел, можно решать с помощью сравнений.

Пример 2.1. Найдем признаки делимости на 4.

Пусть дано произвольное натуральное число a, десятичная запись которого , где a_n, a_n-1,…,a₁, a₀ – цифры числа a.

Запишем a в развернутой форме: .

Так как , если , то . Следовательно, целое число при делении на 4 «ведет себя» так же, как и число, составленное из его двух последних цифр. Поэтому, если число, составленное из двух последних цифр данного числа, делится на 4, то и само число делится на 4.

Так как , то  Поэтому, если сумма удвоенной предпоследней и последней цифр данного числа делится на 4, то и само число делится на 4.

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

Пусть m>1 – произвольное натуральное число. При делении на m могут получиться m различных остатков: 0, 1, 2, ....m-1.

Пусть r – остаток от деления a на m, тогда a=mx+r (Определение 1.2), следовательно, a-r=mx, поэтому  (Определение 1.1), значит,  (Свойство 1.2).

В связи с этим возникает идея рассматривать сравнения не на всем бесконечном множестве целых чисел, а на конечном множестве остатков от деления на m. Тогда любому целому числу a будет соответствовать определенный остаток r из конечного множества остатков, который будем называть вычетом по модулю m, или просто вычетом.

Очевидно, что каждому вычету r соответствует бесконечно много целых чисел, которые при делении на m дают остаток равный r.

Определение 3.1. Введем на множестве остатков от деления на m действия сложения и умножения. Суммой (соответственно, произведением) двух остатков a и b назовем остаток от деления на m обычной суммы (произведения) чисел a и b.

Для любых остатков а, b и c очевидно верны следующие свойства:

3.1.             +;

3.2.             +(+)=(+)+;

3.3.             +0=;

3.4.             =;

3.5.             ()=();

3.6.             ;

3.7.             a(b+c)=ab+ac.

Справедливость этих свойств следует из аналогичных свойств действий над целыми числами и свойств сравнений.

Арифметику остатков от деления на 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 – арифметиках, замечаем, что:

3.8.             для каждого числа 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. (если , то
).

В Таблице 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 – арифметике обладают свойствами, подобными свойствам отрицательных чисел в обычной арифметике:

3.8.1.      ;

3.8.2.      .

Например, в 7 – арифметике: -3=4, -5=2,  и ; в 10 – арифметике: -8=2, -7=3,  и ).

Используя свойство 3.8, определим операцию вычитания в m – арифметике:
a-b=a+(-b).

При вычислении разности в m – арифметике можно использовать следующий прием: из уменьшаемого вычесть вычитаемое и, если результат получился отрицательный, прибавить m. Этот прием основан на Свойстве 2.4. (если , то
). Например, вычислим 7-19 в 23 – арифметике: 7-19=-12=-12+23=11.  Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях.

m – арифметика обладает очень важным свойством: если в любом верном числовом равенстве из обыкновенной арифметики, содержащем, кроме чисел, только знаки сложения, вычитания, умножения и скобки, заменить каждое число его остатком от деления на m, то получим равенство, верное в смысле m – арифметики. (Это утверждение следует из Свойства 2.8). Само собой разумеется, что показатель степени не следует заменять остатком от деления на m. Показатель степени играет в формуле другую роль, нежели числа, не являющиеся показателями: он есть просто сокращенное обозначение того, сколько раз надо взять сомножителем основание степени. Пример: из верных равенств: ;   мы получаем этим способом верные 10 – арифметические равенства:  ; .

Рассматривая таблицы умножения (Приложение 1), замечаем, что для некоторых m – арифметик произведение не нулевых чисел может быть равно нулю (например, в 4 – арифметике: ; в 6 – арифметике: ; в 10 – арифметике:
, ; и т.д.). В таких случаях говорят, что в m – арифметике имеются делители нуля, т.е. такие числа  и , что ab=0.

Анализируя таблицы умножения (Приложение 1) m – арифметик, замечаем, что:

3.9.            делителями нуля являются числа, не взаимно простые с m (т.е. имеющие с m общие делители отличные от единицы). Например, в 4 – арифметике: ; в 10 – арифметике:  ,

3.10.        среди ненулевых остатков по модулю m, взаимно простых с m нет делителей нуля.

Доказательство.

Предположим, что найдутся два остатка a и b по модулю m, такие, что ,  и НОД(a, m)=1, НОД(b, m)=1, но ab=0 в m – арифметике.

Это значит, что число ab делится на m, поскольку НОД(a, m)=1, то , следовательно, . Пришли к противоречию, следовательно, среди ненулевых остатков по модулю m, взаимно простых с m нет делителей нуля.

Что и требовалось доказать.

Из свойства 3.10 следует, что если a – взаимно просто с m,  и , то  Но тогда все элементы вида a, 2a,…,(m-1)a различны и, следовательно, среди них есть только один элемент равный единице. Это значит, что:

3.11.        если  и a – взаимно просто с m, то существует такой остаток b, для которого ab=1 (например, в 3 – арифметике: ; в 4 – арифметике: ; в 5 – арифметике: ; и т.д.). Такой остаток обозначают  или  и называют обратным к a. Если же , то остатка обратному к a не существует (делители нуля не имеют обратных элементов).

Очевидно, что если для некоторых двух остатков a и b верно равенство a^-1=b^-1, то a=b.

Когда числа маленькие, то для нахождения обратных чисел можно применить простой приём: добавлять к числителю (или вычитать из числителя) величину модуля m, пока числитель не поделится нацело. Частное и будет искомым обратным. Например, найдем 2^-1 в 13 – арифметике: . Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Описанный выше прием для нахождения обратных чисел основывается на Свойстве 2.4. (если , то ) и Свойстве 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 – арифметике обладают следующими свойствами:

3.11.1.  (a^-1)^-1=a;

3.11.2.  (-a)^-1=-a^-1;

3.11.3.  (ab)^-1=a^-1b^-1.

Используя свойство 3.11, определим операцию деления в m – арифметике: , где  и b не является делителем нуля (b взаимно просто с m). В m – арифметике нельзя делить на 0 и на делители нуля, поскольку в последнем случае получим не однозначный результат.

При вычислении частного в m – арифметике можно для малых чисел использовать тот же прием, что и при нахождении обратного: добавлять к числителю (или вычитать из числителя) величину модуля m, пока числитель не поделится нацело. Полученное частное и будет искомым. Например, найдем  в 13 – арифметике: . Эта запись не является верной, с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Этот способ нахождения частного в m – арифметике основывается на Свойстве 2.4 (если , то ) и Свойстве 2.9 (обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем).

При выполнении деления в m – арифметике можно использовать следующее полезное равенство: , где n – взаимно просто с m.

Очевидно, что если модуль – простое число, то в такой арифметике делителей нуля нет (все остатки взаимно просты с модулем), в этом случае деление на любой не равный нулю остаток всегда выполнимо. Такую арифметику принято называть p – арифметикой. Примеры p – арифметик: 2, 3, 5, 7, 11, 13, и т.д. арифметики.

Деление в p – арифметике обладают свойствами, подобными свойствам деления в обычной арифметике.

Арифметику вычетов точно так же, как и сравнения по модулю, можно использовать для решения задач на делимость. Для этого нужно все данные числа заменить остатками и выполнять над ними арифметические действия, по правилам m – арифметики.

Пример 3.1. Вычислим 3¹⁰⁰ в 7 – арифметике:

  Следовательно,
 . Остаток от деления 3¹⁰⁰ на 7 равен 4.

Пример 3.2. Найдем остаток от деления 2¹⁰⁰⁰ на 5. Вычислим 2¹⁰⁰⁰ в 5 – арифметике:  Следовательно,  Поэтому остаток от деления 2¹⁰⁰⁰ на 5 равен 1.

Пример 3.3. Делится ли  на 2014?

 поэтому в 2014 – арифметике число 2013 будет записываться как -1, тогда . Следовательно,  делится на 2014.

Пример 3.4. Доказать, что при любом натуральном n число 37ⁿ⁺²+16ⁿ⁺¹+23ⁿ делится на 7.

Рассмотрим данное выражение в 7 – арифметике. ;  , следовательно, данное выражение в 7 – арифметике будет записано так: . Тогда .

Поэтому 37ⁿ⁺²+16ⁿ⁺¹+23ⁿ делится на 7.

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

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

Определение 4.2. Уравнение вида ax+by=c, где a, b, c – целые, x, y – неизвестные называют линейным диофантовым уравнением с двумя неизвестными. Если НОД(a, b, c)=1 (коэффициенты уравнения взаимно просты), то уравнение называют приведенным. Решить диофантово уравнение, значит найти все целые значения x и y, при которых уравнение обращается в верное равенство, или доказать, что решений нет.

Теорема 4.2. Если в приведенном линейном диофантовом уравнении ax+by=c (1),  (a и b не взаимно простые), то уравнение (1) не имеет решений.

Доказательство.

Пусть , тогда , , тогда, подставив в уравнение (1) получим: . Следовательно, , или  .

 – целое. Так как уравнение (1) приведенное, то НОД(a, b, c)=1, следовательно  – не может быть целым. Пришли к противоречию, поэтому если в приведенном линейном диофантовом уравнении ax+by=c, a и b не взаимно простые, то уравнение не имеет решений.

Что и требовалось доказать.

Рассмотрим решение линейных диофантовых уравнений с двумя неизвестными в m – арифметике.

Пусть ax+by=c – приведенное уравнение, , тогда, перейдя к вычетам по модулю b, получим:  где  – остаток от деления a на b,  - остаток от деления c на b,  – решение уравнения в арифметике вычетов по модулю b. Согласно определению операции деления в m – арифметике,  – всегда существует и, причем только одно, равное частному от деления  на , в арифметике вычетов по модулю b, т.е. .

Пусть  найдено, тогда  (3) (Свойство 1.1), где . Выразим из исходного уравнения y: . Подставив в последнее равенство выражение для x (3), получим: ,

Пример 4.1. Решить уравнение 14x-10y=6 в целых числах.

Разделим обе части данного уравнения на 2: 7x−5y=3 (1).

Запишем полученное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например, 5. Тогда: , или .

Переменные записываем с чертой вверху, поскольку это не переменная, значение которой нужно найти, а ее вычет по модулю 5.

Следовательно, . Поэтому

Выразим из уравнения (1) y:  и, подставив в него найденное выражение для x (2), получим:

Ответ: .

Пример 4.2. Решить уравнение 39x + 22y = 10 в целых числах.

Поступим так же, как и в Примере 4.4. Запишем данное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например 22:
 , или .

Следовательно, .

Найдем 17^-1 в 22 – арифметике:
 =-9=13 Следовательно, 17^-1=13.

Тогда,  .

Выразим из исходного уравнения y и подставим в полученное равенство найденное значение x:

Ответ: .

Пример 4.3. Решить уравнение 26x - 34y = 13 в целых числах.

Данное уравнение приведенное НОД(26, 34, 13)=1. Так как , то оно не имеет решений в целых числах (Теорема 4.2).

Ответ: решений нет.

Пример 4.4. Решить уравнение 43x + 37y = 21 в целых числах.

Запишем данное уравнение в m – арифметике: в качестве m возьмём один из коэффициентов при переменных, например 43: , или . Тогда, , .

Выразим из исходного уравнения x, и подставим в полученное равенство найденное значение y:

Ответ:

ЗАКЛЮЧЕНИЕ

Арифметика вычетов — один из тех разделов математики, которые зарождались как некоторые формальные рассуждения, и только спустя годы нашли свое практическое применение.

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

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

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

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

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

Работа над этим проектом позволила занять мне второе место в районном этапе Всероссийской олимпиады школьников и стать призером отборочного этапа международной олимпиады «Покори Воробьевы горы!» (Приложение 2).

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

1.        Дынкин Е. Б., Успенский В. А. Математические беседы. – М., Л: Государственное издательство технико – теоретической литературы, 1952.

2.        Виленкин Н. Сравнения и классы вычетов // Квант – 1978. - №10. С. – 4 – 9.

3.        Геронимус А. Сравнения по простому модулю // Квант – 1978. - №11. С. – 6 – 11.

4.        Геронимус А. Диофантовы уравнения по простому модулю // Квант – 1978. - №12. С. – 2 – 7.

5.        Спивак А. В. Арифметика. – М.: Бюро Квантум, 2007.

6.        Спивак А. В. Арифметика – 2. – М.: Бюро Квантум, 2008.

7.        Воробьев Н. Н. Признаки делимости. – М., Наука. Гл. ред. физ. – мат. лит., 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

Краткое описание документа:

ВВЕДЕНИЕ

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

Делимость чисел и решение управней в целых числах рассматривается в рамках одного из разделов математики – теории чисел. Основы теории чисел зародились еще в Древнем Египте и Вавилоне. Вавилонские клинописные математические тексты включают таблицы умножения и обратных чисел, квадратов и кубов чисел натурального ряда. Самой древней археологической находкой в истории арифметики является обломок глиняной таблички, датируемый 1800 годами до нашей эры. Он содержит список Пифагоровых троек. Весомый вклад в становление теории чисел внесли Евклид, Диофант и пифагорейцы. Пифагорейцы рассматривали только целые положительные числа и полагали число собранием единиц. Единицы были неделимы и располагались в виде правильных геометрических тел. Пифагорейцам характерно определение «фигурных чисел» («треугольных», «квадратных» и других). Изучая свойства чисел, они разбили их на чётные и нечётные, простые и составные. Пифагорейцы нашли бесконечное множество целых решений уравнения a²+b²=c², так называемых пифагоровых троек, и вывели для них общую формулу. Евклид посвятил несколько книг «Начал» теории делимости, в основе этой теории лежит алгоритм Евклида для нахождения общего наибольшего делителя двух чисел. Следствием алгоритма является возможность разложения любого числа на простые сомножители, а также единственность такого разложения. Диофант в своем труде «Арифметика» перечислил задачи по нахождению целочисленных решений для уравнений (называемых сейчас диофантовыми).