Учебный проект " Алгоритм Евклида и линейные диофантовы уравнения.

АЛГОРИТМ ЕВКЛИДА И ЛИНЕЙНЫЕ ДИОФАНТОВЫ УРАВНЕНИЯ

Выполнила: ученица 8 б класса

Малютина Дарья

Учитель: Затеева Валентина Павловна

2019

АКТУАЛЬНОСТЬ ИССЛЕДОВАНИЯ

В школьном курсе математики диофантовы уравнения не изучаются, но, например, в заданиях ЕГЭ встречаются диофантовы уравнения 2-ой степени, также уравнения часто встречаются и в олимпиадных задачах.

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

ЦЕЛЬ И ЗАДАЧИ ПРОЕКТА

Цель: Научиться решать текстовые задачи, по которым можно составить деофантово уравнение.

Задачи:

• Найти информацию о том, как был открыт алгоритм Евклида.
• Узнать, где применяют диофантовы уравнения в наше время.
• Изучить основные приёмы и методы решения линейных диофантовых уравнений в целых числах.

ЕВКЛИД

Евкли́д (от греч. «добрая слава» ) — древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биографические сведения об Евклиде крайне скудны. Достоверным можно считать лишь то, что его научная деятельность протекала в Александрии в III в. до н. э.

АЛГОРИТМ ЕВКЛИДА

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его . Это один из старейших численных алгоритмов, используемых в наше время.

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо.

ОПИСАНИЕ АЛГОРИТМА НАХОЖДЕНИЯ НОД ДЕЛЕНИЕМ

1. Большее число делим на меньшее

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления.

3. Переходим к пункту 1.

• пример :

Найти НОД для 40 и 15.

40/15 = 2 (остаток 10)

15/10 = 1 (остаток 5)

10/5 = 2 (остаток 0).

Конец: НОД - это делитель. НОД (40, 15) = 5

ОПИСАНИЕ АЛГОРИТМА НАХОЖДЕНИЯ НОД ВЫЧИТАНИЕМ

1. Из большего числа вычитаем меньшее

2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла)

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания

4. Переходим к пункту 1

• Пример :

Найти НОД для 40 и 15.

40 - 15 = 25

25 - 15 = 10

15 - 10 = 5

10 - 5 = 5

5 - 5 = 0 Конец: НОД - это уменьшаемое или вычитаемое. НОД (40, 15) = 5

ДИОФАНТ АЛЕКСАНДРИЙСКИЙ

Диофант (Александрийский) – древнегреческий математик, живший в 3 веке до нашей эры. В своем основном труде "Арифметика", состоящем из 13 книг, он дал решение большого числа задач и, в частности, уравнений, которые теперь называют его именем.

ДИОФАНТОВЫ УРАВНЕНИЯ

Диофа́нтово уравнение — это уравнение вида P(x1, x2, ..., xn) = 0, где P(x1, ..., xn) - многочлен с целыми коэффициентами. Диофантовым уравнение названо в честь древнегреческого математика Диофанта. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.

Общий вид линейного диофантова уравнения с двумя неизвестными: ax+by = c (числа a и b взаимно просты ).

Решение задач

Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?

Решение.  Пусть х - количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног. Составим уравнение: 5х + 8у = 39.

   Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у=(39 – 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3. Ответ: (3; 3)

Решение задач

В каталоге картинной галереи всего 96 картин. На каких-то страницах расположено 4 картины, а на каких-то 6. Сколько страниц каждого вида есть в каталоге?

Решение. Пусть х – количество страниц с четырьмя картинами, у – количество страниц с шестью картинами, тогда по условию этой задачи можно составить уравнение:4x+6y=96.

Решаем это уравнение относительно 4х, то есть:

4х=96-6у.

Делим все уравнение на этот коэффициент:

4х=96-6у | :4;

х=(96-6у):4.

Остатки при делении на 4: 1,2,3. Подставим вместо у эти числа.

Если у=1, то х=(96-6∙1):4=90:4 - Не походит, решение не в целых числах.

Если у=2, то х=(96-6∙2):4=21 – Подходит.

Если у=3, то х=(96-6∙3):4=78:4 - Не походит, решение не в целых числах.

Итак, частным решением является пара (21;2), а это значит, что на 21 странице расположено по 4 картины, а на 2 страницах по 6 картин.

3=7-4∙1. Выразим 4=3∙1+1, = 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙2-7∙1=1. Итак, получается х=1; у=2. А это значит, что молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки. " width="640"

Решение задач

В магазине продаётся шоколад двух видов: молочный и горький. Весь шоколад хранится в коробках. Молочного шоколада на складе имеется 7 коробок, а горького 4. Известно, что горького шоколада было на одну плитку больше. Сколько плиток шоколада находятся в коробках каждого вида?

Решение. Пусть х – количество плиток молочного шоколада в одной коробке, у – количество плиток горького шоколада в одной коробке, тогда по условию этой задачи можно составить уравнение:4у-7х=1.

Решим это уравнение, используя алгоритм Евклида.

4у-7х=1;

Выразим 7=4∙1+3, = 3=7-4∙1.

Выразим 4=3∙1+1, = 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙2-7∙1=1.

Итак, получается х=1; у=2.

А это значит, что молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки.

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ТЕОРИИ ДИОФАНТОВЫХ УРАВНЕНИЙ.

Неожиданно, лет 20-30 назад, было осознано, что эту чисто абстрактную теорию можно использовать для построения алгоритмов, которые нужны для криптографии, чтобы зашифровывать и безопасно передавать секретные сообщения, а также снимать и класть деньги в банкоматах и т. п. Теория эта оказалась востребована на практике.

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ТЕОРИИ ДИОФАНТОВЫХ УРАВНЕНИЙ.

Знаменитый мост «Золотые Ворота», находящийся в Сан-Франциско был построен с применением теории диофантовых уравнений.

ВЫВОД

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

Выявила, где в наше время можно встретить диофантовы уравнения.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

•   Г. Фалин, А. Фалин “ Линейные диофантовы уравнения”, МГУ, 2012г.
• “ Задачи в целых числах”, М, «Просвещение», 2013г.
• Вагутен В. Н. Алгоритм Евклида и основная теорема арифметики // Квант. -1972.
• Абрамов С. А. Самый знаменитый алгоритм // Квант / под ред. А. Л. Семёнов, А. А. Гайфуллин — МИАН, 1985.
• https:// ru.wikipedia.org/wiki
• Галкин Е. В. Нестандартные задачи по математике. – Челябинск: Взгляд, 2005.

СПАСИБО ЗА ВНИМАНИЕ