Алгоритмы Евклида
занимательные факты по алгебре (6 класс) по теме

Направление:  математическое

Исследовательская работа

Содержание:

1. Введение. Евклид и его «Начала»……………………………...  3

1. Алгоритм Евклида (нахождение наибольшего общего

     делителя) …………………………………………………………. 8

1. Заключение………………………………………………………   12

1. Список  литературы…………………………..............................   13

Введение

 Кто с детских лет занимается математикой,

тот развивает внимание, тренирует свой мозг,

свою волю, воспитывает в себе настойчивость

                                     и упорство в достижении цели.

А.И.Маркушевич

«Математика — это язык, в котором нет места неточным и туманным высказываниям» — это слова Пуанкаре, которые он произнёс во время своей речи о мировой науке в Сан-Луи очень много лет тому назад.

Конечно, математика — это очень краткое представление одного из способов формализации всего рационального мышления. Несомненно, в математике значение тренировки нашего мозга, которое происходит тогда, когда мы учимся в начальной, средней школах и в высших учебных заведениях, ведь практика, точно так же, как в любой игре, делает его сильнее. Невозможно сказать, сильнее ли мозг математика сегодня, если сравнивать с древнегреческими временами; однако если брать ещё больший масштаб эволюции, то, скорей всего, это именно так. В самом деле математика может играть огромную роль в генетике, что она может оказаться одним из немногих средств совершенствования человеческого мозга. Если это и вправду так, то для человечества не было бы ничего важнее, независимо от того придут ли люди к новой судьбе вместе или по отдельности. Возможно, что с помощью математики можно будет создавать физически, то есть анатомически, новые связи в мозге. Математика обладает способностью обострять ощущения, даже, несмотря на то, что быстрое увеличение материала до огромных объёмов стремится загубить всё дело.

Евклид и его «Начала»

Математические знания накапливались в Греции и греческих колониях в течение нескольких столетий. Постепенно стало ясно: нельзя логическим путем вывести нечто из ничего. Нужно зафиксировать первоначальные понятия и некоторые факты, из которых можно вывести все остальное. В геометрии они назывались постулатами, а в арифметике – аксиомами.

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

И такой мыслитель появился в третьем веке до н.э. в Александрии. Это был

Евклид                                                              Начала  Евклида

    Точных сведений о его биографии не сохранилось. Возможно, это связано с царской немилостью – согласно легенде, ученый был дерзок с владыкой Александрии и всего Египта, царем Птолемеем. Так о Евклиде писал первый комментатор Прокл: «Евклид, сын Наукрата, известный под именем «Геометра», ученый старого времени, по своему происхождению грек, по местожительству сириец, родом из Тира». Царь Птолемей I, чтобы возвеличить свое государство, привлекал в страну ученых и поэтов. В числе приглашенных ученых оказался и Евклид.  Когда монах начал изучать геометрию, у него возникли трудности. Не привыкший встречать затруднения, царь вызвал Евклида и спросил, нет ли какого-то особого, доступного лишь правителям способа усвоить эту науку. Евклид ответил: «Царской дороги в математике нет».

Сам Евклид доказал не так уж много новых теорем – хотя, разумеется, были и они. Но не в этом его главная заслуга. Мы благодарны Евклиду прежде всего за то, что он переработал и по-новому осмыслил уже известные результаты, показав другим пример того, как это можно и нужно делать.

      Впрочем, математики, сравниваемые по значению с Евклидом, появились нескоро – спустя два тысячелетия! В течение многих веков математикам казалось, что 13-томный труд Евклида нельзя улучшить – можно только дополнить новыми открытиями. Труд этот называется «Начала». До нас дошли не многие его сочинения. Основные из них – 15 книг под общим названием «Начала». Два тысячелетия эти книги оставались энциклопедией геометрии. И в наши дни в учебниках геометрии можно найти многие теоремы Евклида. Недаром изучаемую в школе геометрию называют евклидовой. Чем же замечательна его книга? В ней очень хорошо, продуманно изложены все знания по геометрии, накопленные к тому времени, и, главное, впервые была сделана попытка дать аксиоматическое изложение геометрии.

Кроме труда по геометрии, названного «Начала», до нас дошли книги Евклида, посвященные теории музыки и астрономии.

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

Евклид – первый математик александрийской школы. Он основал в Александрии - столице Египта  математическую школу и написал для ее учеников свой фундаментальный труд. Именно в Александрии Евклид основывает математическую школу и пишет большой труд по геометрии, объединенный под общим названием "Начала" - главный труд своей жизни. Полагают, что он был написан около 325 года до нашей эры. Предшественники Евклида - Фалес, Пифагор, Аристотель и другие много сделали для развития геометрии. Но все это были отдельные фрагменты, а не единая логическая схема. Как современников, так и последователей Евклида привлекала систематичность и логичность изложенных сведений. "Начала" состоят из тринадцати книг, построенных по единой логической схеме. Каждая из тринадцати книг начинается определением понятий (точка, линия, плоскость, фигура и т. д.), которые в ней используются, а затем на основе небольшого числа основных положений (5 аксиом и 5 постулатов), принимаемых без доказательства, строится вся система геометрии. В то время развитие науки и не предполагало наличия методов практической математики.  Его главная работа «Начала» (в латинизированной форме – «Элементы») содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел; в ней он подвел итог предшествующему развитию греческой математики и создал фундамент дальнейшего развития математики.  

      Аксиоматический метод со временем вошел во многие науки, причем не только естественные. Великий голландский философ Спиноза, например, аксиоматизировал этику.

      Дальнейшая судьба «Начал», несмотря на всю их образцовость, сложилась непросто. Средневековые фанатики – и христиане, и мусульмане  безжалостно  уничтожали древние рукописи, действуя  по принципу: «Если они противоречат нашим священным книгам, то они вредны; а если нет, то они ни к чему». И все-таки, в латинских и арабских переводах, «Начала» выжили, и их по достоинству оценили математики нового времени. Величайший ученый XVII века Исаак Ньютон, следуя Евклиду, назвал свою главную книгу «Начала натуральной философии». Да и в двадцатом веке наши дедушки и бабушки еще знакомились с геометрией по учебнику, изложение материала в котором следовало евклидовым «Началам».

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

      В «Началах» Евклида достойное место занимает часть математики, изучающая целые числа – арифметика или теория чисел. Это один из самых красивых разделов математики.

    Разложение чисел на простые множители показывает, что всякое число является либо простым, либо произведением двух или нескольких простых чисел. Можно поэтому сказать, что простые числа являются составными элементами натуральных чисел, как бы кирпичиками, из которых при помощи действия умножения составляются все целые числа. Вот почему простыми числами стали интересоваться еще в древности. Издавна бросалось в глаза нерегулярность распределения простых чисел среди всех натуральных чисел. Было замечено, что по мере продвижения от малого числа к большему в натуральном ряду простые числа встречаются все реже. Поэтому одним из первых вопросов был такой: существует ли последнее простое число, т.е. имеет ли ряд простых чисел конец? Около 300 лет до н.э. на этот вопрос дал отрицательный ответ знаменитый древнегреческий математик Евклид. Он доказал, что за каждым простым числом имеется еще большее простое число, т.е. существует бесчисленное множество простых чисел.

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

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

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

 (нахождение наибольшего общего делителя)

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

Предположим для определенности, что  а≥ в. Разделим  а на в с остатком:

Теперь имеется две возможности:

1) . Тогда ясно, что .

2) . Тогда нужно воспользоваться следующим замечательным соотношением:  (а,в ) =(в,r)вытекающим из того, что каждый общий делитель  а и  в делит r  и каждый общий делитель  в и  r делит  а (это видно из определения деления с остатком), так что множество общих делителей  а и  в совпадает с множеством общих делителей  в и r, в частности, совпадают наибольшие общие делители. Имеем: а≥ в > r.
Теперь вместо  (а,в) надо находить  (в, r). Деля  в на  r и обозначая остаток через r1, мы получаем:  
Если , то . Если же , то надо делить  r на  r1 и так далее, пока не получится остаток, равный 0. В конце концов это произойдет, поскольку остатки все время уменьшаются. Последний отличный от нуля остаток и будет равен . Окончательно запишем весь процесс так:
 

  Тогда .

      Применим описанный способ отыскания НОД к числам 437 и 713. Деля 713 на 437, получаем в остатке 276. Значит, теперь надо найти наибольший общий делитель для чисел 437 и 276. Делим 437 на 276 и получаем в остатке 161. Теперь делим 276 на 161 и т.д. В конце концов, получаем числа 46 и 23, причем деление 46 на 23 выполняется нацело. Это значит, что наибольшим делителем пары чисел (23,46) является 23, а тогда таков же НОД заданных чисел 713 и 437.

      Пример 1.

    С помощью алгоритма Евклида найти НОД(13 172,261)

    Разделим число 13 172 на 261

                           13172  261

                             1305   50

                                122

    Делим в согласии с алгоритмом Евклида число 261 на остаток от деления (число 122)

             361 : 122=2(остаток 17)

    Делим число 122 на остаток (число 17)

                           122 : 17=7 (остаток 3)

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

                           17 : 3=5(ост. 2)

                           3 : 2=1 (ост.1)

                           1 : 1 = 1 (ост. 0)

    предпоследний остаток был равен единице. Следовательно, единица и есть НОД(13172,216)=1

 Пример 2.

   Найдем НОД чисел 21588 и 5546

   Разделим 21588 на 5546:                    

                          21588    5546

                           16638   3

                             4950  

   Делим в согласии с алгоритмом Евклида число 5546 на остаток от деления (число 4950)                          

                           5546 : 4950=1 (ост. 596)                  

  Делим число 4950 на остаток (число 596)

                          4950 : 596=8 (ост. 182)

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

                           596 : 182=3 (ост. 50)

                           182 : 50=3 (ост.32)

                           50 : 32=1 (ост. 18)

                           32 : 18=1 (ост.14)

                           18 : 14=1 (ост. 4)

                           14 : 4=3 (ост. 2)

                            4 : 2= 2 (ост. 0)

   Предпоследний остаток был равен двум. Следовательно, двойка и есть НОД(21588,5546)=2.

   Пример 3.

Найдем НОД чисел 15456 и 14041.

15456 = 14041∙1 +1415

14041 = 1415 ∙ 9 + 1306

                                                    1415 = 1306 ∙1 +109

                                                    1306 = 109 ∙ 11 +107

                                                    109 = 107 ∙ 1 +2

                                                    107 = 2 ∙ 53 + 1

                                                    2 = 1∙ 2

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

    Чтобы получить этим способом последовательного деления наибольший общий  делитель трех, четырех и большего числа данных чисел, находят сначала НОД первых двух, потом НОД полученного числа и третьего из данных чисел, затем НОД полученного числа и четвертого из данных чисел и т.д., пока не переберут все данные числа. Например, чтобы найти наибольший общий делитель чисел 748, 561, 493, находят сначала НОД (748, 561) = 187, затем НОД (187, 493) = 17. Это последнее число и есть искомое.

Заключение

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

Найти НОД (4847, 4181).

Разложение данных чисел на простые множители является делом нелегким, так как ни одно из чисел 2, 3, 4, 5, 6, 9, для которых устанавливаются в школе признаки делимости, не является делителем данных чисел. Алгоритм же Евклида легко и быстро приводит к результату: НОД (4847, 4181) = 37.(Проверьте!)

Другой пример: сократить дробь . Решение. Выполним деление с остатком. Разделим 833 на 714:

833. 714

714     1

119

Здесь делимое а = 833, делитель в = 714 и остаток  r  = 119.

НОД (833,714) = НОД (714, 119). Теперь разделим 714 на 119:

714. 119

           714      6

  0

Таким образом, НОД (833 и 714) = 119. Тогда   =  = ! что может быть проще?!

«Математика – царица всех наук. Ее возлюбленный – истина, ее наряд – простота и ясность. Дворец этой владычицы окружен тернистыми зарослями, и, чтобы достичь его, каждому приходится продираться сквозь чащу. Случайный путник не обнаружит во дворце ничего привлекательного. Красота его открывается лишь разуму, любящему истину, закаленному в борьбе с трудностями, свидетельствующему о незаурядности и непреодолимой склонности человека к необычайно запутанным, но неиссякаемым и возвышенным наслаждениям ума, свойственным самой природе людей» (Снядецкий Ян)

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

1. Глейзер Г.И. История математики в школе V – VIII классы. –М.                         Просвещение.
2. Савин А.П., Станцо В.В., Котова А.Ю. Я познаю мир: Детская энциклопедия: Математика. – М.: АСТ.
3. Худадатова С.С. Математика в ребусах, кроссвордах, чайнвордах, криптограммах, 6 класс. – М.: Школьная пресса.
4. http://www.college.ru /mathematics /courses / planimetry /content /scientist / eukleides.html