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

Евклида алгоритм – это способ нахождения наибольшего общего делителя.

Был предложен сначала в геометрической форме для нахождения наибольшей общей меры двух отрезков, или,вообще, двух геометрических величин.

Если отрезки a и b равны, то любой из них может быть принят за отрезок с₀. Если отрезки не равны, то пусть а обозначает больший отрезок, а b – меньший. В таком случае откладывают вдоль по отрезку а отрезок b столько раз, сколько он уложится. Если при этом не получается никакого остатка, то отрезок b и является наибольшей общей мерой (сам в себе он укладывается один раз). Если остается некоторый остаточный отрезок b₁, то он откладывается вдоль отрезка b столько раз, сколько он уложится. Если при этом не получается остатка, то b₁ и есть наибольшая общая мера с₀. В случае, когда вновь получается остаточный отрезок b₂, он откладывается вдоль отрезка b₁ и т.д. Если отрезки а и b соизмеримы, то процесс неизменно кончится на каком-либо шаге с номером k тем, что отрезок b_k уложится целое число раз в отрезке b_k-1. Отрезок b_k и есть в этом случае общая наибольшая мера отрезков а и b.Если отрезки а и b несоизмеримы, то алгоритм Евклида может оказаться бесконечным.

Тот же алгоритм применяется для нахождения наибольшего общего делителя двух целых чисел или наибольшего общего делителя двух многочленов.

Пусть а и b– два положительных целых числа, причем а>=b. Деление с остатком числа a на число b всегда приводит к результату a=nb+b₁, где (неполное) частное n является положительным целым числом, а остаток b₁ - либо 0, либо положительное целое число, меньшее b.

Находится ряд равенств:

(где n_i - положительные целые числа и 0 <= b_i < b_i-1), заканчивающийся, когда получается равный нулю остаток b_k+1. Последний положительный остаток b_k и является наибольшим общим делителем чисел а и b.

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