Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Другие методич. материалы / Проект "Использование теории вычетов для решения олимпиадных задач"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

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

библиотека
материалов


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

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

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

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








Автор:


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


Класс: 8 б


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


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


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


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


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


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










Белоярский

2015

Овал 1

Содержание




ПЛАН РАБОТЫ



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ


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

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

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

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

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



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



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

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

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

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

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

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

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

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

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

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

В частности из этой теоремы следует, что если b1, то должно быть r0, откуда xa, если b1, то xa.

Всякое число, делящее одновременно числа a и b, называется общим делителем этих чисел. Наибольший из общих делителей чисел a и b называется их наибольшим общим делителем и обозначают НОД(a, b).

Если наибольший общий делитель чисел а и b равен единице, то эти числа называются взаимно простыми. Иначе говоря, числа a и b называются взаимно простыми, если они одновременно не делятся ни на какое число кроме единицы.

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

Определение 1.3. Если двум целым а и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m или сравнимыми по модулю m. Например: hello_html_m5aac3094.gif поэтому 17 и 14 сравнимы по модулю 3.

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

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

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

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

  2. если hello_html_m19de5d1e.gif, то hello_html_m7cc0651b.gif Верно и обратное, если hello_html_556554e7.gif, то hello_html_m19de5d1e.gif.

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

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

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

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

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

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

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

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

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

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

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

Так, как hello_html_m417b61d8.gif, то hello_html_m42d3e9b.gif и hello_html_2620b141.gif, (Определение 1.3). Из второго равенства выразим r: hello_html_69dfcab1.gif. Подставив в первое равенство, получим: hello_html_91d2985.gif, где hello_html_m2e28a3e3.gif — целое. Следовательно, если hello_html_m4c6aa39b.gif, то hello_html_54d13525.gif, где t — целое.

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

Пример: так как hello_html_62f7eb39.gif Так как hello_html_600629d9.gif, то hello_html_34c1aa3.gif где t – целое (в данном случае t2).

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

Свойство 1.2. hello_html_38f6bbd4.gif hello_html_m166d7f67.gif hello_html_24acad74.gif.

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

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

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



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



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

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

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

Так как hello_html_4f0db4c1.gif, то hello_html_m55010205.gif, где hello_html_3df82cee.gif, а так как hello_html_m4c80fed8.gif, то hello_html_m2cdd8034.gif где hello_html_m7988ab56.gif. Поэтому hello_html_m1da7ac32.gif, где hello_html_31bb7662.gif. Следовательно, hello_html_m5e758529.gif.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть hello_html_38f6bbd4.gif, НОД(a, b)k, НОД(k, m)1, тогда hello_html_m662a996c.gif, hello_html_m6a402be7.gif, поэтому:
hello_html_4ceccd4a.gif (Свойство 1.2). Так, как НОД(km)1, то
hello_html_2a2fb8b8.gif только в том случае, если hello_html_728ecae0.gif, следовательно, hello_html_3c6bae0b.gif, или hello_html_m5febb859.gif.

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

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

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

Если hello_html_m76dc39eb.gif, то hello_html_7f75c091.gif делится на m1 и m2. Значит hello_html_m3a2763fa.gif делится на mНОК(m1, m2). Следовательно hello_html_m417b61d8.gif.

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

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

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

Пусть дано произвольное натуральное число a, десятичная запись которого hello_html_66b38958.gif, где an, an1,…,a1, a0 – цифры числа a.

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

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

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


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



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

Пусть r – остаток от деления a на m, тогда amxr (Определение 1.2), следовательно, armx, поэтому hello_html_m12300f78.gif (Определение 1.1), значит, hello_html_m16bb926f.gif (Свойство 1.2).

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

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

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

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

    1. hello_html_77a1cb35.gif+hello_html_m3a263fa6.gif;

    2. hello_html_m3a263fa6.gif+(hello_html_63fe3678.gif+hello_html_m30fa8acf.gif)=(hello_html_m3a263fa6.gif+hello_html_63fe3678.gif)+hello_html_m30fa8acf.gif;

    3. hello_html_m3a263fa6.gif+0=hello_html_m3a263fa6.gif;

    4. hello_html_m45f9f230.gif=hello_html_40b5f333.gif;

    5. hello_html_m3a263fa6.gif(hello_html_3065f942.gif)=(hello_html_m45f9f230.gif)hello_html_m30fa8acf.gif;

    6. hello_html_m59e515b4.gif;

    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 – арифметиках, замечаем, что:

    1. для каждого числа a существует число (a), такое, что a(a)0 (например, в 7 – арифметике: 34, так как 340; 52, так как 520; в 10 – арифметике: 82, 73). Число (a) называют противоположным числу a. Следовательно, в m – арифметике любое число можно записывать в двух разных формах со знаком минус и без него.

Найти число, противоположное числу а в m – арифметике просто: нужно из m вычесть a. Например, найдем число противоположное 7 в 13 – арифметике: 71376. Эта запись не является верной с точки зрения m – арифметики, однако ее удобно использовать при вычислениях. Описанный выше метод нахождения противоположного числа в m – арифметике основывается на Свойстве 2.4. (если hello_html_m417b61d8.gif, то hello_html_dfa219b.gif
hello_html_3bfd72cb.gif).

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

      1. hello_html_m26d48778.gif;

      2. hello_html_m148f0d23.gif.

Например, в 7 – арифметике: 34, 52, hello_html_7caf4d4d.gif и hello_html_34483aec.gif; в 10 – арифметике: 82, 73, hello_html_3e91cc1.gif и hello_html_2ef3df61.gif).

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

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

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

Рассматривая таблицы умножения (Приложение 1), замечаем, что для некоторых m – арифметик произведение не нулевых чисел может быть равно нулю (например, в 4 – арифметике: hello_html_m28765884.gif; в 6 – арифметике: hello_html_m1776bfa1.gif; в 10 – арифметике: hello_html_m6b4819d.gif
hello_html_m454033fc.gif, hello_html_m4b7f2581.gif; и т.д.). В таких случаях говорят, что в m – арифметике имеются делители нуля, т.е. такие числа hello_html_a3c9387.gif и hello_html_73eb1563.gif, что ab0.

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

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

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

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

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

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

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

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

    1. если hello_html_a3c9387.gif и a – взаимно просто с m, то существует такой остаток b, для которого ab1 (например, в 3 – арифметике: hello_html_4a249f2d.gif; в 4 – арифметике: hello_html_m924db8e.gif; в 5 – арифметике: hello_html_76550b7d.gif; и т.д.). Такой остаток обозначают hello_html_7975c575.gif или hello_html_7abe906a.gif и называют обратным к a. Если же hello_html_m64bb7a6b.gif, то остатка обратному к a не существует (делители нуля не имеют обратных элементов).

Очевидно, что если для некоторых двух остатков a и b верно равенство a1b1, то ab.

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

      1. (a1)1=a;

      2. (a)1a1;

      3. (ab)1a1b1.

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

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

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

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

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

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

Пример 3.1. Вычислим 3100 в 7 – арифметике: hello_html_m3827ce19.gif

hello_html_1e1a2267.gif Следовательно, hello_html_74a1110e.gif
hello_html_m1c292b46.gif. Остаток от деления 3100 на 7 равен 4.

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

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

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

Пример 3.4. Доказать, что при любом натуральном n число 37n216n123n делится на 7.

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

Поэтому 37n216n123n делится на 7.

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



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

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

Теорема 4.2. Если в приведенном линейном диофантовом уравнении axbyc (1), hello_html_m3bcea387.gif (a и b не взаимно простые), то уравнение (1) не имеет решений.

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

Пусть hello_html_1383bf88.gif, тогда hello_html_2eb4366c.gif, hello_html_12e74799.gif, тогда, подставив в уравнение (1) получим: hello_html_5c15c19f.gif. Следовательно, hello_html_3f0767c8.gif, или hello_html_45c5535c.gif .

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

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

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

Пусть axbyc – приведенное уравнение, hello_html_m76e9e443.gif, тогда, перейдя к вычетам по модулю b, получим: hello_html_m39dc67b4.gif где hello_html_m7b4f4e24.gif – остаток от деления a на b, hello_html_2ba651c5.gif - остаток от деления c на b, hello_html_6916d802.gifрешение уравнения в арифметике вычетов по модулю b. Согласно определению операции деления в m – арифметике, hello_html_6916d802.gif – всегда существует и, причем только одно, равное частному от деления hello_html_2ba651c5.gif на hello_html_m7b4f4e24.gif, в арифметике вычетов по модулю b, т.е. hello_html_m68688e70.gif.

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

Пример 4.1. Решить уравнение 14x10y6 в целых числах.

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

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

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

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

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

Ответ: hello_html_4a859a64.gif.

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

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

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

Найдем 171 в 22 – арифметике: hello_html_1d4ffaa5.gif
hello_html_m31b33130.gif913 Следовательно, 17113.

Тогда, hello_html_157d8488.gif hello_html_483aa0c7.gif.

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

Ответ: hello_html_m17754b48.gif.

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

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

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

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

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

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

Ответ: hello_html_129fd686.gif

ЗАКЛЮЧЕНИЕ



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

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

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

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

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

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

Работа над этим проектом позволила занять мне второе место в районном этапе Всероссийской олимпиады школьников и стать призером отборочного этапа международной олимпиады «Покори Воробьевы горы!» (Приложение 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


















a1

-

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
















a1

-

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














a1

-

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












a1

-

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










a1

-

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








a1

-

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






a1

-

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




a1

-

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


a1

-

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


a1

-

1

6

4

3

9

2

8

7

5

10

hello_html_3a6298f6.png

hello_html_m374dde14.png



Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

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

ВВЕДЕНИЕ

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

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

Автор
Дата добавления 28.04.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров904
Номер материала 258288
Получить свидетельство о публикации
Похожие материалы

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