Евклід АЛГОРИТМ
Евкліда Алгоритм - метод для знаходження найбільшого загального дільника двох цілих чисел, а також двох многочленів від одного змінного. Е.А. спочатку був викладений в «Засадах» Евкліда в геометричній формі як спосіб знаходження загальної міри двох відрізків. Е.А. для знаходження найбільшого загального дільника як в кільці цілих чисел, так і в кільці многочленів від одного змінного є окремим випадком якогось загального алгоритму в евклідових кільцях.
Е.А. для цілих чисел полягає в наступному. Нехай, причому. Розділимо із залишком на - отримаємо неповну частку і залишок, такий, що. Потім розділимо на - отримаємо неповну частку і залишок,. Тепер розділимо на і т. Д. Отримаємо ланцюжок рівностей:
в якій через кінцеве число кроків виходить черговий сальдо конечне нулю, так як послідовність залишків є спадною послідовністю невід'ємних цілих чисел:
і, отже, повинна через кінцеве число кроків закінчитися нулем. Тоді найбільший спільний дільник чисел і дорівнює останньому відмінному від нуля залишку в схемі послідовного розподілу (*).
Приклад. Знайти найбільший спільний дільник чисел 1981 і 378. Виконуємо послідовний розподіл:
Останній відмінний від 0 залишок 7 і є найбільший спільний дільник чисел 1981 і 378.
Е.А. для знаходження найбільшого загального дільника двох многочленів і також складається в послідовному розподілі із залишком на, потім на перший залишок, потім на другий залишок і т. д.
Так як ступеня залишків, які є натуральними числами, зменшуються, то через кінцеве число кроків приходимо до залишку, рівному нулю. Останній відмінний від нуля залишок і є найбільшим загальним дільником многочленів і.