1.1 Застосування алгоритму Евкліда
Як і будь-яка добротно виконана робота, алгоритм Евкліда дає набагато більше, ніж від нього очікувалося спочатку отримати. З його розгляду ясно, наприклад, що сукупність дільників а і b збігається із сукупністю дільників (a, b). Ще він дає практичний спосіб знаходження чисел u і v із Z (або, якщо завгодно, з теореми пункту 2) таких, що
r n = au + bv = (a, b).
Дійсно, з ланцюжка рівностей маємо:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...
(Йдемо по ланцюжку рівностей знизу вгору, висловлюючи з кожної наступної рівності залишок і підставляючи його в вираз, що вийшов до цього моменту)
Au + bv = (a, b).
Безсумнівно, описана Евклідом процедура визначення загальної міри двох величин стосовно числа (а загальна міра двох натуральних чисел, очевидно, є їх найбільший спільний дільник) була винайдена задовго до Евкліда. Так само знаходили НОД і древні китайські математики. І тільки те, що ця процедура стала відома в епоху Відродження саме з «Початок, дало їй назву алгоритм Евкліда»
Швидше за все, вона виникла з комерційної практики стародавніх купців, коли треба було порівнювати різні відносини цілих чисел. Як, наприклад, порівнювати відносини чисел 3703700 та 1234567 та чисел 22962965 та 7654321? Цілком природною була спроба дізнатися, скільки разів менша кількість вкладається в більшому. Легко перевірити, що 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно тепер, що відношення 3703700 до 1234567 менше, ніж відношення 229625
2,99999919 <= 3, 000000261,
Стародавні обчислювачі пояснювали довгою фразою.
Якби довелося порівняти ближчі відносини чисел, наприклад, і, то обчислення були б складнішими:
71755875 = 61735500 + 10020375;
61735500 = 6 · 10020375 + 1613250;
10020375 = 6 · 1613250 + 340875;
1613250 = 4 · 340875 + 249750;
340875 = 249750 + 91125;
249750 = 2 · 91125 + 67500;
91125 = 67500 + 23625;
67500 = 2 · 23625 + 20250;
23625 = 20250 + 3375;
20250 = 6 · 3375.
Алгоритм Евкліда тут дозволяє визначити НОД чисел 71755875 та 61735500, рівний 3375 та відповідає розкладу відношення 71755875 до 61735500 у ланцюговий дріб:
Алгоритм Евкліда виявляється еквівалентним сучасної процедури розкладання числа в ланцюгову дріб і більше, дозволяє «округлити» відносини чисел, тобто. замінювати дріб із великим знаменником на дуже близький до нього дріб із меншим знаменником. Справді, вираз
рівне дробу, в сучасній математиці називається «підходящим дробом» розкладання відношення б = в ланцюговий (або безперервний) дріб.
Ясно що
б=1+< 1 + и б=1 + > 1+ = ,
оскільки
Наведене порівняння було виконано в III ст. до н.е. Аристархом Самоським у трактаті «Про відстань і розміри Місяця та Сонця».
Зараз відомо, що відповідні дроби розкладання будь-якого (раціонального або ірраціонального) числа в ланцюговий дріб є найкращими раціональними наближеннями цього числа.
Алгоритми з багаточленами
Алгоритм Евкліда - метод знаходження найбільшого загального дільника двох цілих чисел, і навіть двох многочленов від одного змінного...
Одним із найдавніших математичних алгоритмів є алгоритм Евкліда для знаходження найбільшого загального дільника двох позитивних чисел. Ось його найпростіший вигляд. Нехай задані два цілих числа. Якщо вони рівні...
Аналіз алгоритму Евкліда в кільцях Евкліда
Перш ніж приступити до аналізу алгоритму Евкліда розглянемо числа Фібоначчі. Суть послідовності Фібоначчі в тому, що, починаючи з 1,1, наступне число виходить додаванням двох попередніх. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ……
Історія формування поняття "алгоритм". Найвідоміші алгоритми в історії математики
Алгоритм Евкліда є універсальним способом, що дозволяє обчислювати найбільший спільний дільник двох позитивних цілих чисел. Опис алгоритму знаходження НОД діленням: 1. Більше число ділимо на менше 2. Якщо ділиться без залишку.
Кільце цілих чисел Гауса
Ми користуємося звичайним для кілець визначенням найбільшого спільного дільника. НОДом двох гаусових чисел називається такий їхній спільний дільник, який ділиться на будь-який інший їхній спільний дільник. Як і в багатьох цілих чисел...
Математичні основи системи залишкових класів
Розглянемо приклад. Нехай р = 6. Тоді маємо шість класів розбиття множини цілих чисел за модулем 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; де через r позначено залишок від розподілу цілого числа на 6...
Методика вивчення багаточленів на факультативних заняттях у старших класах середньої загальноосвітньої школі
Нехай кільце багаточленів над. Визначення 1: Нехай і якщо існує многочлен, то залишок від розподілу дорівнює нулю, то називається дільником багаточлена і позначається: ()...
Основні етапи становлення та структура сучасної математики
У III столітті до нашої ери в Олександрії з'явилася книга Евкліда з тією ж назвою, у російському перекладі "Початки". Від латинської назви"Початок" стався термін "елементарна геометрія". Незважаючи на те...
На території якогось міста N розміщені заводи і магазини, в які поставляється продукція з цих заводів. В результаті розробки було визначено можливі траси для прокладання комунікацій та оцінено вартість їх створення для кожної траси.
Застосування методів дискретної математики економіки.
Фірмі, що займається перевезенням швидкопсувних товарів, необхідно доставити товар з Суйфеньхе в Хабаровськ, причому маршрутів, якими можна зробити доставку кілька. Відстань між Суйфеньхе та містом 2 складає 15 км.
Розвиток поняття "Простір" та неевклідова геометрія
Спеціальні методи інтегрування раціональних виразів
Нехай необхідно знайти НОД багаточленів та. Не обмежуючи спільності, будемо вважати, що ступінь не вищий за ступінь. Багаточлен представимо у вигляді: де - залишок від розподілу на. Тоді ступінь менший за ступінь дільника. Далі...
Теорія залишків
Теорія залишків
Визначення. Число d?Z, що ділить одночасно числа а, b, c, ..., k ??Z, називається загальним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k). Теорема. Якщо (a, b) = d...
Теорія залишків
Нехай потрібно вирішити лінійне діофантове рівняння: ax + by = c , де a , b , c ??Z ; a та b - не нулі. Спробуємо поміркувати, дивлячись на це рівняння. Нехай (a, b) = d. Тоді a = a 1 d; b = b 1 d і рівняння виглядає так: a 1 d x + b 1 d y y = c , тобто. d· (a 1 x + b 1 y) = c...
Алгоритм Евкліда
Найбільший спільний дільник
Розглянемо таку задачу: потрібно скласти програму визначення найбільшого загального дільника (НД) двох натуральних чисел.
Згадаймо математику. Найбільший спільний дільник двох натуральних чисел - це найбільше натуральне число, яке вони діляться націло. Наприклад, у чисел 12 та 18 є спільні дільники: 2, 3, 6. Найбільшим загальним дільником є число 6. Це записується так:
НОД(12, 18) = 6.
Позначимо вихідні дані як М u N. Постановка задачі виглядає так:
Дано:М, N
Знайти:НОД(М, N).
В даному випадку якоїсь додаткової математичної формалізації не потрібно. Сама постановка завдання має формальний математичний характер. Не існує формули для обчислення НОД(М, N) за значеннями М і N. Але досить давно, задовго до появи ЕОМ, був відомий алгоритмічний спосіб вирішення цього завдання. Називається він алгоритмом Евкліда .
Ідея алгоритму Евкліда
Ідея цього алгоритму заснована на тій властивості, що якщо M>N, то
НОД (М, N) = НОД (М - N, N).
Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці (модуля їхньої різниці) і меншого числа.
Легко довести цю властивість. Нехай До - спільний дільник М u N (M> N). Це означає, що М = mК, N = nК, де m, n – натуральні числа, причому m > n. Тоді М - N = К(m - n), звідки випливає, що К - дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками їхньої різниці М - N, у тому числі і найбільший спільний дільник.
Друга очевидна властивість:
НОД(М, М) = М.
Для "ручного" рахунку алгоритм Евкліда виглядає так:
1) якщо числа рівні, то взяти будь-яке з них як відповідь, інакше продовжити виконання алгоритму;
2) замінити більшу кількість різницею більшого та меншого з чисел;
3) повернутись до виконання п. 1.
Розглянемо цей алгоритм з прикладу М=32, N=24:
Структура алгоритму - цикл-поки що з вкладеним розгалуженням. Цикл повторюється, поки значення М та N не рівні один одному. У розгалуженні більше двох значень замінюється з їхньої різницю.
А тепер подивіться на таблицю трасування алгоритму для вихідних значень М = 32, N = 24.
| Крок | Операція | M | N | Умова |
| 1 | введення М | 32 | ||
| 2 | введення N | 24 | ||
| 3 | M ¹ N | 32 ¹ 24, так | ||
| 4 | M>N | 32>24, так | ||
| 5 | M:=M-N | 8 | ||
| 6 | M ¹ N | 8 ¹ 24, так | ||
| 7 | M>N | 8>24, ні | ||
| 8 | N:=N-M | 16 | ||
| 9 | M ¹ N | 8 ¹ 16, так | ||
| 10 | M>N | 8>16, ні | ||
| 11 | N:=N-M | 8 | ||
| 12 | M ¹ N | 8 ¹ 8, ні | ||
| 13 | висновок M | 8 | ||
| 14 | кінець |
У результаті вийшов правильний результат.
Програма на АЯ та на Паскалі
Запишемо алгоритм на АЯ та програму на Паскалі.
Запитання та завдання
1. Виконайте на комп'ютері програму Evklid. Протестуйте її на значеннях М = 32, N = 24; М=696, N=234.
2. Складіть програму знаходження найбільшого загального дільника трьох чисел, використовуючи таку формулу:
НОД(А, B, З) = НОД(НОД(А, У), З).
3. Складіть програму знаходження найменшого загального кратного (НОК) двох чисел, використовуючи формулу:
А × В = НОД (А, В) × НОК (А, В).
- Ознайомити із поняттям «алгоритм Евкліда».
- Навчити шукати найбільш спільні дільники різними математичними методами.
Хід уроку
Поняття Алгоритм Евкліда
Є одним з найдавніших математичних , який вже понад 2000 років.
Алгоритм Евкліда придуманий для знаходження найбільшого спільного дільникапари цілих чисел.
Найбільший спільний дільник
Найбільший спільний дільник(НОД) – це число, що ділить без залишку два числа і ділиться без залишку на будь-який інший дільник даних чисел.
Іншими словами, це саме велике число, на яку можна залишити розділити два числа, для яких шукається спільний дільник.
Алгоритм знаходження НОД поділом
Опис алгоритму знаходження найбільшого загального дільника поділом
Більше ділиться на менше
Якщо ділиться без залишку, то менше і є найбільший спільний дільник. Тепер потрібно вийти з циклу
Якщо є залишок, то більше замінюємо на залишок від розподілу
Перехід до пункту 1.
Приклад:
Знайти найбільший спільний дільник для 300 та 180.
300/180 = 1 (залишок 120)
180/120 = 1 (залишок 60)
120/60 = 2 (залишок 0).
Кінець:Найбільший спільний дільник – це 6.
В циклі"a" або "b" фіксується залишок від розподілу. Коли залишку немає (ми не знаємо в «а» він або «b,» тому перевіряємо обидва умови), то цикл завершується.
Наприкінці виводиться сума «a» і «b», тому що ми не знаємо, в якій змінній записано найбільший спільний дільник, а в одній з них у будь-якому разі 0, що не впливає на результат суми.
Алгоритм знаходження НОД відніманням
Опис алгоритму знаходження найбільшого загального дільника відніманням
З більшої кількості віднімається менше
Якщо виходить 0, то числа дорівнюють один одному і є найбільшим спільним дільником. Вихід із циклу
Якщо результат віднімання не дорівнює 0, то більше число замінюється на результат віднімання
Перехід до пункту 1.
Приклад:Знайти для чисел 300 та 180.
Кінець:Найбільш загальний дільник чисел 300 та 180 – 60.
Як спосіб знаходження найбільшої загальної міри двох відрізків (метод поперемінного віднімання) був відомий ще піфагорійцям.
При знаходженні найбільшої загальної міри двох відрізківнадходять такими самими способами, що й вище.
Операція поділу із залишком замінюється її геометричним аналогом: менший відрізоквідкладають на більший стільки разів, скільки можливо, а решту більшого відрізка (а це залишок розподілу) відкладають на меншому відрізку.
Якщо відрізки aі bсумірними, то останній не нульовий залишок дасть найбільшу загальну міру відрізків.
У разі їх несумірності отримана послідовність ненульових залишків буде нескінченною.
Приклад:
Як відрізки візьмемо бік AB і AC рівнобедреного трикутника ABC, у якого A = C = 72 °, B = 36 °.
Як перший залишок ми отримаємо відрізок AD (CD-бісектриса кута C), і, як легко бачити, послідовність і нульові залишки буде нескінченною.
Отже, відрізки AB і AC не можна порівняти.
Запитання
1. Що таке алгоритм Евкліда?
2. Що таке найбільший спільний дільник?
Список використаних джерел
1. Урок на тему: "Алгоритм Евкліда", Корчовий П. І., м. Луцьк
2. Щетников А. І. Алгоритм Евкліда та безперервні дроби. - Новосибірськ: АНТ, 2003
3. Коунтінхо С. Введення в теорію чисел. Алгоритм RSA, - М., 2001 р.
4. Кострикін А.І. Введення в алгебру, - М., 2000
Відредаговано та надіслано викладачем Київського національного університету ім. Тараса ШевченкаСоловйовим М. С.
Над уроком працювали
Корчовий П. І.
Соловйов М. З.
Поставити питання про сучасній освіті, висловити ідею або вирішити назрілу проблему Ви можете на Освітній форум
Широко поширеного в електронній комерції. Також алгоритм використовується при вирішенні лінійних діофантових рівнянь, при побудові безперервних дробів, в методі Штурму. Алгоритм Евкліда є основним інструментом для доказу теорем у сучасній теорії чисел, наприклад таких як теорема Лагранжа, о сумі чотирьох квадратів і основна теорема арифметики.
Енциклопедичний YouTube
1 / 5
✪ Математика. Натуральні цифри: Алгоритм Евкліда. Центр онлайн-навчання «Фоксфорд»
✪ Алгоритм Евкліда
✪ Алгоритм Евкліда, швидкий спосібзнайти НІД
✪ Математика 71. Найбільший спільний дільник. Алгоритм Евкліда - Академія цікавих наук
✪ 20 Цикл while Алгоритм Евкліда Python
Субтитри
Історія
Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «Взаємне віднімання». Цей алгоритм не був відкритий Евклідом, так як згадка про нього є вже в ТопікеАристотеля. У «Початках» Евкліда він описаний двічі – у VII книзі для знаходження найбільшого загального дільника двох натуральних чисел та у X книзі для знаходження найбільшої загальної міри двох однорідних величин. В обох випадках дано геометричний опис алгоритму для знаходження «загальної міри» двох відрізків.
Опис
Алгоритм Евкліда для цілих чисел
Нехай a (\displaystyle a)і b (\displaystyle b)- цілі числа, не рівні одночасно нулю, та послідовність чисел
a > b > r 1 > r 2 > r 3 > r 4 > … > rn (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))визначено тим, що кожне r k (\displaystyle r_(k))- це залишок від розподілу попереднього числа на попереднє, а передостаннє ділиться на останнє націло, тобто:
a = b q 0 + r 1 (displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2 (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots ) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots ) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)Тоді НОД( a, b), найбільший спільний дільник aі b, дорівнює r n, останньому ненульовому члену цієї послідовності.
Існуваннятаких r 1 , r 2 , ..., r n , тобто можливість поділу із залишком mна nдля будь-якого цілого mі цілого n≠ 0, доводиться індукцією за m.
Коректністьцього алгоритму випливає з наступних двох тверджень:
- Нехай a = b⋅q + rтоді НОД (a, b) = НОД (b, r).
Доказ
- НОД( r, 0) = rдля будь-якого ненульового r(оскільки 0 ділиться на будь-яке ціле число, крім нуля).
Геометричний алгоритм Евкліда
Нехай дані два відрізки довжини aі b. Віднімемо з більшого відрізка менший і замінимо більший відрізок отриманою різницею. Повторюємо цю операцію, доки відрізки не будуть рівні. Якщо це станеться, то вихідні відрізки співмірні, і останній отриманий відрізок є їх найбільшою загальною мірою. Якщо загального заходу немає, то процес нескінченний. У такому вигляді алгоритм описаний Евклідом і реалізується за допомогою циркуля та лінійки.
Приклад
Для ілюстрації алгоритм Евкліда буде використаний, щоб знайти НОД a= 1071 та b= 462. Для початку від 1071 віднімемо кратне значення 462, поки не отримаємо різницю менше, ніж 462. Ми повинні двічі відібрати 462, ( q 0 = 2), залишаючись із залишком 147:
1071 = 2×462+147.
Потім від 462 віднімемо кратне значення 147, поки не отримаємо різницю менше, ніж 147. Ми повинні тричі відібрати 147 ( q 1 = 3), залишаючись із залишком 21:
462 = 3×147 + 21.
Потім від 147 віднімемо кратне значення 21, поки не отримаємо різницю менше, ніж 21. Ми повинні сім разів відібрати 21 ( q 2 = 7), залишаючись без залишку:
147 = 7×21 + 0.
Таким чином, послідовність a > b > r 1 > r 2 > r 3 > … > r n у даному конкретному випадку виглядатиме так:
1071 > 462 > 147 > 21.
Оскільки останній залишок дорівнює нулю, алгоритм закінчується числом 21 і НОД(1071, 462) = 21.
У табличній формі кроки були такі:
Застосування
Розширений алгоритм Евкліда та співвідношення Безу
Формули для r i (\displaystyle r_(i))можуть бути переписані таким чином:
r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots ) НІД (a, b) = r n = a s + b t (displaystyle (a, b) = r_ (n) = as + bt)Тут sі tцілі. Це уявлення найбільшого, загального, дільника називається співвідношенням «Безу», а числа sі t- Коефіцієнтами? Безу. Співвідношення Безу є ключовим у доказі леми, Евкліда та основної теореми, арифметики.
Ланцюгові дроби
Алгоритм Евкліда досить тісно пов'язаний з ланцюговими дробами. Ставлення a/bдопускає подання у вигляді ланцюгового дробу:
a b = [q 0; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).При цьому ланцюговий дріб без останнього члена дорівнює відношенню коефіцієнтів Безу t/s, взятому зі знаком мінус:
[q 0; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).Послідовність рівностей, що задає алгоритм Евкліда, може бути переписана у формі:
ab = q 0 + r 0 bbr 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ rk − 2 rk − 1 = qk + rkrk − 1 ⋮ r N − 2 r N − 1 = q N (\displaystyle (\begin(aligned)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\end(aligned)))Останнє доданок у правій частині рівності завжди одно зворотного значеннялівої частини наступного рівняння. Тому перші два рівняння можуть бути об'єднані у формі:
ab = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac(a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1))(r_(0))))))Третя рівність може бути використана, щоб замінити знаменник виразу r 1 /r 0 , отримаємо:
ab = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac(a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\) cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))Останнє відношення залишків r k /r k−1 завжди може бути замінено з використанням наступної рівності у послідовності, і так до останнього рівняння. Результатом є ланцюговий дріб:
a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [q 0; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_) (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N)))))))))))Узагальнений алгоритм Евкліда для багаточленів
Алгоритм Евкліда та розширений алгоритм Евкліда природним чином узагальнюється на кільце. k[x] від однієї змінної над довільним полем k, Оскільки для таких багаточленів визначено операцію поділу із залишком. За виконання алгоритму Евкліда для многочленов аналогічно алгоритму Евкліда для цілих чисел виходить послідовність полиномиальных залишків (PRS) .
Приклад для кільця Z[x]
Нехай cont(f) за визначенням - НОД коефіцієнтів многочлена f(x) з Z[x] - змістбагаточлена. Приватне від розподілу f(x) на cont(f) називається примітивною частиноюбагаточлена f(x) і позначається primpart(f(x)). Ці визначення знадобляться для знаходження НОД двох багаточленів p 1 (x)і p 2 (x)у кільці Z[x]. Для многочленів над цілими числами вірно таке:
C o n t ((\displaystyle cont()НОДНОД ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)),cont(p_(2)(x))\),)
P r i m p a r t ((\displaystyle primpart()НІД ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=)НІД ( p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)
Таким чином, задача пошуку НОД двох довільних багаточленів зводиться до задачі пошуку НОД примітивних поліномів.
Нехай є два примітивні багаточлени p 1 (x) і p 2 (x) з Z[x], для яких виконується співвідношення між їхніми ступенями: deg(p 1 (x)) = m і deg(p 2 (x)) = n, m> n. Поділ многочленів із залишком передбачає точну ділимість старшого коефіцієнта поділеного на старший коефіцієнт дільника, у випадку розподіл із залишком виконати неможливо. Тому вводять алгоритм псевдодіління, який все ж таки дозволяє отримати псевдочастинний і псевдозалишок (prem), які самі по собі належать безлічі багаточленів над цілими числами.
Під псевдоділенням розумітимемо, що самому поділу передує множення полінома p 1 (x) (\displaystyle p_(1)(x))на (l c (p 2 (x))) m n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), тобто
L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg (r (x))< deg (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}
де q (x) (\displaystyle q(x))і r(x) (\displaystyle r(x))- відповідно псевдочастинний і псевдозалишок.
Отже, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), причому deg (p 1) = n 1 ≥ deg (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Тоді алгоритм Евкліда складається з наступних кроків:
1. Обчислення НОД змістів:
C:= (\displaystyle c:=)НІД ( c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).
2. Обчислення примітивних елементів:
P 1 '(x): = p r i m p a r t (p 1 (x)); (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)
P 2 '(x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)
3. Побудова послідовності поліноміальних залишків:
P 1 ′ (x) , (\displaystyle p_(1)"(x),)
P 2 ′ (x) , (\displaystyle p_(2)"(x),)
P 3 (x) := prem (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2) )"(x)),)
P 4 (x) := prem (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (x)),)
P 5 (x) := prem (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x )),)
. . . (\displaystyle...)
P h (x) := p r em (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)
Алгоритм Евкліда знаходження НОД (найбільшого спільного дільника)
Дано два цілих невід'ємних числа і . Потрібно знайти їх спільний дільник, тобто. найбільше, яке є дільником одночасно і , і . Англійською мовою "найбільший спільний дільник" пишеться "greatest common divisor", і поширеним його позначенням є:
(тут символом "" позначено подільність, тобто "" означає "ділить")
Коли воно з чисел дорівнює нулю, а інше на відміну від нуля, їх найбільшим спільним дільником, згідно з визначенням, буде це друге число. Коли обидва числа дорівнюють нулю, результат не визначений (підійде будь-яке нескінченно велике число), ми покладемо в цьому випадку найбільший спільний дільник рівним нулю. Тому можна говорити про таке правило: якщо одне з чисел дорівнює нулю, то їх найбільший спільний дільник дорівнює другому числу.
Алгоритм Евкліда, Розглянутий нижче, вирішує задачу знаходження найбільшого загального дільника двох чисел і за .
Цей алгоритм був вперше описаний у книзі Евкліда "Початку" (близько 300 р. до н.е.), хоча, цілком можливо, цей алгоритм має раннє походження.
Алгоритм
Сам алгоритм надзвичайно простий і описується такою формулою:
Реалізація
int gcd (int a, int b) ( if (b == 0 ) return a; else return gcd (b, a % b) ; )Використовуючи тернарний умовний оператор C++, алгоритм можна записати ще коротше:
int gcd (int a, int b) ( return b ? gcd (b, a % b) : a; )Нарешті, наведемо і нерекурсивну форму алгоритму:
int gcd (int a, int b) ( while (b) ( a % = b; swap (a, b) ; ) return a; )Доказ коректності
Спочатку зауважимо, що з кожної ітерації алгоритму Евкліда його другий аргумент суворо зменшується, отже, оскільки він неотрицательный, то алгоритм Евкліда завжди завершується.
Для докази коректностінам потрібно показати, що для будь-яких >.
Покажемо, що величина, що стоїть у лівій частині рівності, ділиться на справжню у правій, а стоїть у правій — ділиться на стоїть у лівій. Очевидно, це означатиме, що ліва та права частини збігаються, що й доведе коректність алгоритму Евкліда.
Позначимо 
. Тоді, за визначенням, та .
Але тоді звідси випливає:
Отже, згадуючи твердження, отримуємо систему:
Скористаємося наступним простим фактом: якщо якихось трьох чисел виконано: і , то виконується і: . У нашій ситуації отримуємо:
Або, підставляючи замість визначення як , отримуємо:
Тож ми провели половину доказу: показали, що ліва частина ділить праву. Друга половина доказу провадиться аналогічно.
Час роботи
Час роботи алгоритму оцінюється теореми Ламі, яка встановлює дивовижний зв'язок алгоритму Евкліда та послідовності Фібоначчі:
Якщо > для деякого , то алгоритм Евкліда виконає трохи більше рекурсивних викликів.
