Занятие кружка. Алгоритм Евклида.

Затеева Валентина Павловна  Учитель математики Саратовской области г. Энгельса МБОУ « СОШ № 15» Занятие кружка по теме : Алгоритм Евклида. Цель занятия: Образовательные: 6­7 классы. научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел Воспитательная: формирование  самостоятельности и ответственности при изучении нового  материала; Продолжить воспитывать у ребят: уважение друг к другу; умение слушать ответ  товарища. Продолжить формировать у учащихся: аккуратность пи работе с записями в  тетради; умение работать в коллективе; пунктуальность. Продолжить знакомство с вузовскими формами организации учебных занятий. Развивающая: развитие внимания и аналитического мышления. o o o o o o Оргмомент. Чтобы спорилось нужное дело, Чтобы в жизни не знать неудач, Мы в поход отправляемся смело В мир догадок и сложных задач. Не беда, что идти далеко Не боимся, что путь будет труден Достижения крупные людям Никогда не давались легко! Что такое НОД?  Наибольшим общим делителем двух чисел называется наибольшее число, на которое  делится каждое из этих чисел.  В 6 классе мы находили НОД чисел разложением этих чисел на простые множители. А  если простые множители тяжело подобрать. Для этих случаев существует алгоритм  Евклида. Примеры. НОД (87; 57)=3 87=3•29 и 57=3•19 Пусть требуется найти наибольший общий делитель чисел 1643 и 1457. 1643=31•53, а 1457 =31•47 Сколько множителей нужно перебрать, чтобы найти это простое число 31. Вот здесь нам поможет алгоритм Евклида. Алгоритм Евклида для целых чисел. Пусть   и   — целые числа, не равные одновременно нулю, и последовательность чисел определена тем, что каждое  предыдущего числа на предыдущее, а предпоследнее делится на последнее  нацело, то есть  — это остаток от деления пред  Тогда НОД(a,b), наибольший общий делитель  и  , равен  последовательности.   , последнему ненулевому члену этой Алгоритм Евклида нахождения наибольшего общего делителя (НОД)   двух натуральных чисел вычитанием. 1. Из большего числа вычитается меньшее. 2. Если получается 0, то числа равны друг другу и являются наибольшим  общим делителем. 3. Если результат вычитания не равен 0, то большее число заменяется на  результат вычитания 4. Переход к пункту 1. Например: Найти НОД(30; 18). 30 ­ 18 = 12; 18 ­ 12 = 6; 12 ­ 6 = 6; 6 – 6 = 0. НОД – это уменьшаемое или вычитаемое. НОД (30; 18) = 6. Приведенный метод вычисления не является оптимальным. Например, для  нахождения НОД(100; 2) следует выполнить 50 (!!) операций вычитания . Для  ускорения вычисления НОД операцию вычитания следует заменить операцией взятия остатка от деления. Алгоритм Евклида нахождения наибольшего общего делителя (НОД)   двух натуральных чисел делением. 1. Большее число делится на меньшее 2. Если делится без остатка, то меньшее число и есть наибольший общий  делитель. 3. Если есть остаток, то большее число заменяем на остаток от деления. 4. Продолжаем деление до тех пор, пока не получим в остатке нуль.  Последний неравный нулю остаток и есть НОД данных чисел. Например: Найти НОД (273;1014). Решение. Выполняем деление с остатком: По лемме: 1014=273*3+195 273=195*1+78 195=78*2+39 78=39*2 НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39 НОД(273;1014)=39 Для иллюстрации алгоритм Евклида будет использован, чтобы найти  НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462,  пока не получим разность меньше, чем 462. Мы должны дважды отнять 462,  (q0 = 2), оставаясь с остатком 147 1071 = 2 × 462 + 147. Затем от 462 отнимем кратное значение 147, пока не получим разность  меньше, чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с  остатком 21. 462 = 3 × 147 + 21. Затем от 147 отнимем кратное значение 21, пока не получим разность  меньше, чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без  остатка. 147 = 7 × 21 + 0. Таким образом последовательность a > b > R1 > R2 > R3 > R4 > … > Rn в данном конкретном случае будет выглядеть так: 1071 > 462 > 147 > 21 Так как последний остаток равен нулю, алгоритм заканчивается  числом 21 и НОД(1071, 462)=21. В табличной форме шаги были следующие Шаг  k Равенство Частное и остаток 0 1 2 1071 = q0 462 + r0 q0 = 2 и r0 = 147 462 = q1 147 + r1 q1 = 3 и r1 = 21 147 = q2 21 + r2 q2 = 7 и r2 = 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 Понятно, что найти НОД этих чисел посредством разложения на простые  множители было бы гораздо труднее. Числа взаимно простые. НОД=1.     Чтобы получить этим способом последовательного деления наибольший  общий  делитель трех, четырех и большего числа данных чисел, находят  сначала НОД первых двух, потом НОД полученного числа и третьего из  данных чисел, затем НОД полученного числа и четвертого из данных чисел и  т.д., пока не переберут все данные числа. Например, чтобы найти наибольший  общий делитель чисел 748, 561, 493, находят сначала НОД (748, 561) = 187,  затем НОД (187, 493) = 17. Это последнее число и есть искомое. Чтобы убедится в преимуществе приема последовательного деления над  приемами разложения на простые множители, когда имеем дело с большими  числами, рассмотрим следующий пример.  Найти НОД (4847, 4181). Разложение данных чисел на простые множители является делом  нелегким, так как ни одно из чисел 2, 3, 4, 5, 6, 9, для которых  устанавливаются в школе признаки делимости, не является делителем данных чисел. Алгоритм же Евклида легко и быстро приводит к результату: НОД  (4847, 4181) = 37.(Проверьте!) Другой пример: сократить дробь  остатком. Разделим 833 на 714: . Решение. Выполним деление с  714 833 833 714 714     1 119 Здесь делимое а = 833, делитель в = 714 и остаток  r  = 119. НОД (833,714) = НОД (714, 119). Теперь разделим 714 на 119: 714 119            714      6   0  Таким образом, НОД (833 и 714) = 119. Тогда    =   =  6 7 119 119  6  7 714 833 ! что может быть проще?! «Математика   –   царица   всех   наук.   Ее   возлюбленный   –   истина,   ее   наряд   – простота и ясность. Дворец этой владычицы окружен тернистыми зарослями, и,   чтобы   достичь   его,   каждому   приходится   продираться   сквозь   чащу. Случайный путник не обнаружит во дворце ничего привлекательного. Красота его   открывается   лишь   разуму,   любящему   истину,   закаленному   в   борьбе   с трудностями,   свидетельствующему   о   незаурядности   и   непреодолимой склонности   человека   к   необычайно   запутанным,   но   неиссякаемым   и возвышенным   наслаждениям   ума,   свойственным   самой   природе   людей» (Снядецкий Ян) Задания для самостоятельной работы: 1. Найти , используя алгоритм Евклида а) НОД (607; 477), б) ) НОД (343; 246), в) ) НОД (6494;6303) 2. Сократите дробь а)  3953 871  б)  6059 1241  в)  6821 2147  г)  10027 32671 Ответы:  1а) 1; 1б) 1; 1в) 191 2а) 59/13 ;б) 83/17 в) 359/113 г) 271/883 Список используемой литературы: 1. Виленкин Н.Я. и др. Математика, 6 класс: учебник для  общеобразовательных учреждений. – М.: Мнемозина, 2013.­ 288с. 2. 3. 4. 5. 6. Горбачев Н.В. Сборник олимпиадных задач по математике. М: МЦНМО,  2004 Далингер В.А. Задачи в целых числах. М: Москва. Илекса. 2013. Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Дополнительные главы к  школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным  изучением математики.­ М.:Просвещение,1996.­ 207 с. Пичурин Л.Ф. За страницами учебника алгебры­ Москва: Просвещение,  1990г. ­ Щетников А. И. Алгоритм Евклида и непрерывные дроби. ­ Новосибирск:  АНТ, 2003 г. Список используемых источников информации: 1. Википедия (свободная энциклопедия), http://ru.wikipedia.org 2. Сайт "Единая коллекция цифровых образовательных ресурсов". Приложение.  Из истории. Древнегреческие математики называли этот  алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».  Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется  уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII  книге для нахождения наибольшего общего делителя двух натуральных чисел  и в X книге для нахождения наибольшей общей меры двух однородных  величин. В обоих случаях дано геометрическое описание алгоритма, для  нахождения «общей меры» двух отрезков. Историками математики (Цейтен и др.) было выдвинуто предположение, что  именно с помощью алгоритма Евклида (процедуры последовательного  взаимного вычитания) в древнегреческой математике впервые было открыто  существование несоизмеримых величин (стороны и диагонали квадрата, или  стороны и диагонали правильного пятиугольника). Впрочем, это  предположение не имеет достаточных документальных подтверждений.  Алгоритм для поиска наибольшего общего делителя двух натуральных чисел  описан также в I книге древнекитайского трактата Математика в девяти  книгах. Ряд математиков средневекового Востока (Сабит ибн Курра, ал­Махани, Ибн  ал­Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида  теорию отношений, альтернативную теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими  авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном  вычитании второй величины в обеих парах на каждом шаге будут получаться  одни и те же неполные частные.