Статья в Энциклопедическом Фонде

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

Евклида алгоритм - способ нахождения наибольшего общего делителя.
Был предложен сначала в геометрической форме для нахождения наибольшей общей меры двух отрезков, или, вообще, двух геометрических величин.
Если отрезки a и b равны, то любой из них может быть принят за отрезок с0. Если отрезки не равны, то пусть а обозначает больший отрезок, а b - меньший. В таком случае откладывают вдоль по отрезку а отрезок b столько раз, сколько он уложится. Если при этом не получается никакого остатка, то отрезок b и является наибольшей общей мерой (сам в себе он укладывается один раз). Если остается некоторый остаточный отрезок b1, то он откладывается вдоль отрезка b столько раз, сколько он уложится. Если при этом не получается остатка, то b1 и есть наибольшая общая мера с0. В случае, когда вновь получается остаточный отрезок b2, он откладывается вдоль отрезка b1 и т.д. Если отрезки а и b соизмеримы, то процесс неизменно кончится на каком-либо шаге с номером k тем, что отрезок bk уложится целое число раз в отрезке bk-1. Отрезок bk и есть в этом случае общая наибольшая мера отрезков а и b.Если отрезки а и b несоизмеримы, то алгоритм Евклида может оказаться бесконечным.
Тот же алгоритм применяется для нахождения наибольшего общего делителя двух целых чисел или наибольшего общего делителя двух многочленов.
Пусть а и b- два положительных целых числа, причем а>=b. Деление с остатком числа a на число b всегда приводит к результату a=nb+b1, где (неполное) частное n является положительным целым числом, а остаток b1 - либо 0, либо положительное целое число, меньшее b.
Находится ряд равенств:
(где ni - положительные целые числа и 0 <= bi < bi-1), заканчивающийся, когда получается равный нулю остаток bk+1. Последний положительный остаток bk и является наибольшим общим делителем чисел а и b.
Алгоритм Евклида служит не только для нахождения общего наибольшего делителя, но и для доказательства самого его существования.



Литература
1.Виноградов И.М. Основы теории чисел. - М.:Наука, 1981. - 176 с.
2.Воробьев Н.Н. Признаки делимости.- 3-е изд. - М.: Наука, 1980. - 96 с.
3.Колмогоров А.Н. Математика - наука и профессия. - М.:Наука, 1988. - 288 с.
Энциклопедический Фонд