ЕВКЛИДА АЛГОРИТМ

ЕВКЛИДА АЛГОРИТМ — метод для нахождения наибольшего общего делителя для целых чисел, а также двух многочленов от одного переменного. Первоначально был изложен в «Началах» Евклида (см.) в геометрической форме как способ нахождения общей меры двух отрезков. Евклида алгоритм для нахождения наибольшего общего делителя как в кольце целых чисел, так и в кольце многочленов от одного переменного является частным случаем некоего общего алгоритма в евклидовых кольцах.   Евклида алгоритм для целых чисел состоит в следующем. Пусть а и b целые числа, причем а ≥ b. Тогда разделим с остатком а на b — получим неполное частное q1 и остаток r1, такой, что 0≤r1<b. Затем разделим с остатком b на r1 — получим неполное частное q2 и остаток r2 (0 ≤ r21). Затем разделим с остатком r1 на r2 и т. д. Получим цепочку равенств

532в которой через конечное число шагов получается очередной остаток, равный нулю (r n+1=0), так как последовательность остатков является убывающей последовательностью неотрицательных целых чисел:

533и, значит, должна через конечное число шагов закончиться нулем. Тогда наибольший общий делитель чисел а и b равен последнему отличному от нуля остатку rn в схеме последовательного деления (*).
Пример. Найти наибольший общий делитель чисел 1981 и 378. Выполняем последовательное деление:

Пример. Найти наибольший общий делитель чисел 1981 и 378. Выполняем последовательное деление:

534Последний отличный от 0 остаток 7 и есть наибольший общий делитель чисел 1981 и 378.
Евклида алгоритм  для нахождения наибольшего общего делителя двух многочленов f(х) и g(х) также состоит в последовательном делении с остатком f(х) на затем g(х) на первый остаток r1(х), затем r1(х) на второй остаток r2(х) а т. д.:

535Так как степени остатков, являющихся натуральными числами, убывают, то через конечное число шагов приходим к остатку, равному нулю. Последний отличный от нуля остаток rn (х) и является наибольшим общим делителем многочленов f(x) и g(x).
Аналогично определяется Евклида алгоритм для отрезка.