Паницкова_8Б_проект Алгоритм Евклида и линейные диофантовы уравнения.

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа №15 с углубленным изучением отдельных предметов

Имени Героя Советского Союза Расковой Марины Михайловны»

Энгельсского муниципального района Саратовской области.

Индивидуальный годовой проект по алгебре

«Алгоритм Евклида и линейные диофантовы уравнения»

Выполнила: Паницкова Мария Алексеевна

Класс: 8Б

Учитель алгебры: Затеева Валентина Павловна

Оглавление

Введение. 3

Глава 1. Алгоритм Евклида; линейные диофантовы уравнения 4

1. Кто такой Евклид 4

1.2 Кто такой Диофант 4

1.3 Что такое алгоритм Евклида 5

1.4 Что такое диофантовы уравнения 6

Глава 2. Практическая часть. 7

2.1 Решение задач с помощью алгоритма Евклида 7

2.2 Решение задач с помощью диофантовых уравнений 8

Заключение 10

Список литературы 11

Введение

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

Диофантовы уравнения – это уравнения или системы алгебраических уравнений с рациональными коэффициентами, решения которых отыскиваются в целых или рациональных числах.

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

Цель проекта: сбор, изучение, обработка и обобщение полученного материала по данной теме.

Задачи проекта:

1. Рассмотреть биографии Евклида и Диофанта.

2. Понять что такое алгоритм Евклида и диофантовы уравнения.

3. Примеры на практике.

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

Объект проекта: Алгоритм Евклида; линейные диофантовы уравнения.

Методы исследования:

1. Метод сбора научно-популярной литературы.

2. Метод анализа научно-популярной литературы

Практическая значимость проекта: обогащение знаний по алгебре.

Хронологические рамки проекта: с 1 сентября по 1 мая 2019-2020 уч. Г.

Глава 1.

Алгоритм Евклида; линейные диофантовы уравнения

1. Кто такой Евклид.

К наиболее достоверным сведениям о жизни Евклида относится то немногое, что говорил о нём один из античных философов – Прокл Диадох. Он отметил, что Евклид был моложе  Платоновского кружка, но старше  Архимеда и Эратосфена, «жил во времена  Птолемея I Сотера». Следует, однако, отметить, что средневековые же авторы отождествляли Евклида с учеником  Сократа, философом  Евклидом из Мегар.

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

Некоторые современные авторы трактуют утверждение Прокла — Евклид жил во времена  Птолемея I Сотера — в том смысле, что Евклид жил при дворе Птолемея и был основателем  Александрийской библиотеки.

Главный труд «Начала», написанный в размере 15 книг, содержит основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объёмов, включавшего элементы теории пределов, оказал огромное влияние на развитие математики. Так же были работы по астрономии, оптике, теории музыки.

1. Кто такой Диофант.

Диофант Александрийский  — древнегреческий  математик, живший предположительно в третьем веке до нашей эры. Нередко упоминается как «отец алгебры». Автор «Арифметики» — книги, посвящённой нахождению положительных  рациональных решений неопределённых уравнений. В наше время под  «диофантовыми уравнениями»  обычно понимают уравнения с целыми  коэффициентами, решения которых требуется найти среди целых чисел.

Несмотря на то, что про Диофанта так же почти ничего не известно, как и про Евклида, Теон Александрийский, который жил около 350 года до нашей эры, писал о нём в своих записях. Отсюда можно сделать вывод , что Диофант существовал примерно в рамках этого периода.

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

Интересный факт, что в честь Диофанта назван кратер на видимой стороне Луны.

В  Палатинской антологии  содержится эпиграмма-задача, из которой можно сделать вывод о том, сколько лет прожил Диофант:

«Прах Диофанта гробница покоит; дивись ей и камень

Мудрым искусством его скажет усопшего век.

Волей богов шестую часть жизни он прожил ребенком.

И половину шестой встретил с пушком на щеках.

Только минула седьмая, с подругой он обручился.

С нею, пять лет проведя, сына дождался мудрец;

Только полжизни отцовской возлюбленный сын его прожил.

Отнят он был у отца ранней могилой своей.

Дважды два года родитель оплакивал тяжкое горе,

Тут и увидел предел жизни печальной своей.»

Составив и решив нужное уравнение, можно понять, что Диофант прожил примерно 84 года.

1. Что такое алгоритм Евклида.

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

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

Древнегреческие математики называли этот алгоритм  «взаимное вычитание». Он не был открыт Евклидом, так как упоминание о нём имеется уже в топике Аристотеля (IV век до нашей эры). В  «Началах» Евклида  он описан дважды — в 7 книге для нахождения наибольшего общего делителя двух натуральных чисел, и в 10 книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

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

Суть алгоритма довольно проста: большее число нужно делить на меньшее. Затем меньшее делится на первый остаток, мы при этом получаем второй остаток. Дальше первый остаток делится на второй и так далее. Последний не равный нулю остаток и будет являться наименьшим общим кратным.

1.4 Что такое диофантовы уравнения.

Решение  уравнений  в  целых  числах  является  одной  из  древнейших математических задач. Уже  в  начале  второго тысячелетия до нашей эры вавилоняне умели решать системы таких уравнений с двумя неизвестными. Наибольшего расцвета эта область математики достигла в Древней Греции. Основным источником для нас является «Арифметика» Диофанта, содержащая различные типы уравнений и систем. Создание древнегреческими учёными теории рациональных чисел привело к рассмотрению рациональных решений неопределённых уравнений. Хотя сочинения Диофанта содержит решения лишь некоторых конкретных уравнений, считается, что он владел некоторыми общими приёмами.

Диофантово уравнение – это уравнение вида P(x1, x2, …, xn) = 0, где P(x1, …, xn) – многочлен с целыми коэффициентами.

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

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

При решении уравнений в целых и натуральных числах можно условно выделить следующие основные методы:

1. Способ перебора вариантов.

2. Алгоритм Евклида.

3. Цепные дроби.

4. Метод разложения на множители.

5. Метод остатков.

При первом способе достаточно просто подбирать варианты решения.

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

Решая уравнения методом разложения на множители, следует применять соответствующие формулы. Как пример, это может быть формула разности квадратов.

Пятый способ основан на исследовании и сравнении остатков правой и левой части, от деления на некое число.

Глава 2

Практическая часть.

2.1 Решение задач с помощью алгоритма Евклида.

С помощью алгоритма Евклида как правило ищут наибольший общий делитель, и решают задачи, целью которых найти НОД.

Чтобы найти наибольший общий делитель двух чисел:

1) надо большее из двух чисел разделить на меньшее;

2) потом меньшее из чисел на остаток при первом делении;

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

Рассмотрим пример. Найти НОД (645; 381).

Решение:

Разделим с остатком 645 на 381. Мы получим: 645=381·1+264.

Далее разделим с остатком 381 на 264, получим: 381=264·1+117.

Теперь разделим с остатком 264 на 117, получим: 264=117·2+30.

Продолжим процесс деления, разделим с остатком 117 на 30, получим: 117=30·3+27. Далее, 30=27·1+3. Следующий шаг – делим 27 на 3, получаем, что 27=3·9 +0, т. Е. 27 делится на 3 без остатка. Значит, наибольший общий делитель чисел 27 и 3 равен 3, следовательно, и наибольший общий делитель чисел 645 и 381 равен 3, т. Е. последнему отличному от нуля остатку.

Таким образом, НОД (645; 381) = 3.

Прием разыскания наибольшего общего делителя, примененный в этом примере, и представляет собой алгоритм Евклида.

Наибольший общий делитель так же можно искать и у нескольких чисел одновременно:

Найдите наибольший общий делитель четырех чисел 78, 294, 57078, 294, 570 и 3636.

Решение

Введем обозначения: a1=78, a2=294, a3=570, a4=36a1=78

Начнем с того, что найдем НОД чисел 78 и 294: d2= НОД (78, 294) =6.

Теперь приступим к нахождению d3= НОД (d2, a3) = НОД (6, 570)

Согласно алгоритму Евклида 570=6·95. Это значит, что d3= НОД (6, 570) =6

Найдем d4=НОД (d3, a4) =НОД (6, 36). 36 делится на 66 без остатка. Это позволяет нам получить d4= НОД (6, 36) =6.

D4=6, то есть, НОД (78, 294, 570, 36) = 6.

Ответ: НОД (78, 294, 570, 36) = 6.

2.2 Решение задач с помощью диофантовых уравнений.

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

Рассмотрим уравнение 13x – 36y = 2. 

Шаг №1

36/13=2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом: 13x – 13*2y – 10y=2.  Преобразуем его: 13(x-2y) – 10y=2. Введем новую переменную z=x – 2y. Теперь мы получили уравнение: 13z – 10y=2.

Шаг №2

13/10=1 (3 в остатке). Исходное уравнение 13z – 10y=2 можно переписать следующим образом: 10z – 10y + 3z=2.  Преобразуем его: 10(z – y) + 3z=2. Введем новую переменную m=z – y. Теперь мы получили уравнение: 10m + 3z=2. 

Шаг №3

10/3=3 (1 в остатке). Исходное уравнение 10m + 3z=2 можно переписать следующим образом: 3*3m + 3z + 1m=2.  Преобразуем его: 3(3m+z) + 1m=2. Введем новую переменную n=3m+z. Теперь мы получили уравнение: 3n + 1m=2. 

M=2 – 3n, причем n может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через n, которое может быть любым числом.

Y=z – m; z=n – 3m, m=2 – 3n ⇒ z=n-3*(2-3n), y=n-3*(2-3n) – (2-3n) = 13n-8; y=13n – 8 

x=2y+z ⇒ x=2(13n-8) + (n-3*(2-3n)) = 36n-22; x=36n-22

Пусть n=1. Тогда y=5, x=24. 13_*(14)-36_*5=2

Пусть n=5. Тогда y=57, x=158. 13_*(158)-36_*(57) = 2

У одной продавщицы были только пятирублёвые и двухрублёвые монетки. Сколькими способами она может набрать 57 рублей сдачи?

Решение

Пусть у нас будет x двухрублевых и y пятирублевых монеток. Составим уравнение: 2х+5y=57. Преобразуем уравнение: 2(x+2y) + y=57. Пусть z=x+2y. Тогда 2z+y=57. Следовательно, y=57-2z, x=z-2y=z-2(57-2z) ⇒ x=5z-114. Обратите внимание, переменная z не может быть меньше 23 (иначе x, число двухрублевых монеток, будет отрицательным) и больше 28 (иначе y, число пятирублевых монеток, будет отрицательным). Все значения от 23 до 28 нам подходят. Получается пять способов.

Некто подошел к клетке, в которой сидели фазаны и кролики. Сначала он подсчитал головы, их оказалось 15. Потом он подсчитал ноги, их было 42. Сколько кроликов и сколько фазанов было в клетке?

Решение: пусть х – число кроликов, а y – число фазанов. Тогда по условию x + y=15. Но ведь у кролика 4 ноги, у фазана 2, значит, у всех кроликов – 4x ног, а у всех фазанов – 2y ног, и по условию 4x + 2y=42.                       

Имеем систему уравнений
x + y=15,          

4x + 2y=42    

x=6, y=9.     

Заключение

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

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

Список литературы

1. Вагутен В.Н. Алгоритм Евклида и основная теорема арифметики // Квант. – 1972. – №6

2. https://ru.wikipedia.org

3. Гельфонд А.О. Решение уравнений в целых числах. – М.: МЦНМО, 2004

4. https://infourok.ru