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

ЕВКЛИДА АЛГОРИТМ — способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов (и вообще, двух элементов евклидова кольца) или общей меры двух отрезков. Описан в геометрич. форме в «Началах» Евклида (3 в. до н. э.).

Для случая положительных целых чисел a≥b этот способ состоит в следующем. Деление с остатком числа а на число b всегда приводит к результату a=nb+b₁, где частное n — целое положительное число, а остаток b₁ либо 0, либо положительное число, меньшее b, 0≤b₁<b. Производится последовательное деление:

(*)

где все n_i — положительные целые числа и 0≤b_i <b_i+1, до тех пор, пока не получится остаток, равный 0. Ряд равенств (*) закончится так:

Последний положительный остаток b_k в этом процессе и является наибольшим общим делителем чисел а и b.

Е. а. для многочленов или отрезков аналогичны Е. а. для целых чисел. В случае несоизмеримых отрезков применение Е. а. приводит к бесконечному процессу.

БСЭ-З.

Источники:

1. Математическая энциклопедия: Гл. ред. И. М. Виноградов, т. 2 Д - Коо.-М.: «Советская Энциклопедия», 1979.-1104 стб., ил.