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

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

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

Обозначив исходные числа через а и b, положительные остатки, получающиеся в результате делений, через r₁, r₂, ..., r_n, а неполные частные через q₁, q₂, ..., q_n+1 можно записать алгоритм Евклида в виде цепочки равенств:

a = bq₁+r₁,

b = r₁q₂ + r₂,

...........................................

r_n-2 = r_n-1q_n + r_n,

r_n-1 = r_nq_n+1.

Приведем пример. Пусть а = 777, b = 629. Тогда 777 = 629•1 + 148, 629= 148•4 + 37, 148 = 37•4. Последний ненулевой остаток 37 и есть наибольший общий делитель чисел 777 и 629.

Для нахождения наибольшей общей меры двух отрезков поступают аналогично. Операцию деления с остатком заменяют ее геометрическим аналогом: меньший отрезок откладывают на большем столько раз, сколько возможно; оставшуюся часть большего отрезка (принимаемую за «остаток от деления») откладывают на меньшем отрезке и т.д. Если отрезки а и b соизмеримы, то последний ненулевой остаток даст наибольшую общую меру этих отрезков. В случае несоизмеримых отрезков получаемая последовательность ненулевых остатков будет бесконечной.

Рассмотрим пример. Возьмем в качестве исходных отрезков стороны АВ и АС равнобедренного треугольника ABC, у которого Â = Ĉ = 72°, В = 36°. В качестве первого остатка мы получим отрезок AD (CD-биссектриса угла С), и, как легко видеть, последовательность ненулевых остатков будет бесконечной. Значит, отрезки АВ и АС несоизмеримы.

Алгоритм Евклида известен издавна. Ему уже более 2 тыс. лет. Этот алгоритм сформулирован в «Началах» Евклида, где из него выводятся свойства простых чисел, наименьшего общего кратного и т.д. Как способ нахождения наибольшей общей меры двух отрезков алгоритм Евклида (иногда называемый методом попеременного вычитания) был известен еще пифагорейцам. К середине XVI в. алгоритм Евклида был распространен на многочлены от одного переменного. В дальнейшем удалось определить алгоритм Евклида и для некоторых других алгебраических объектов.

Алгоритм Евклида имеет много применений. Равенства, определяющие его, дают возможность представить наибольший общий делитель d чисел а и b в виде d = ах + by (х; у-целые числа), а это позволяет находить решения диофантовых уравнений 1-й степени с двумя неизвестными. Алгоритм Евклида является средством для представления рационального числа в виде цепной дроби (см. Календарь). Он часто используется в программах для электронных вычислительных машин.