алгоритм, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в 'Началах' Евклида . Для случая положительных чисел а и b, причём a ³ b, этот способ состоит в следующем. Деление с остатком числа а на число b всегда приводит к результату а nb + b 1,где частное n - целое положительное число, а остаток b 1 - либо 0, либо положительное число, меньшее b (0 £ b 1 < b ) . Будем производить последовательное деление:
где все n i - положительные целые числа и 0 £ b 1 < b i-1до тех пор, пока не получится остаток, равный нулю. Этот последний остаток b k+1 можно не писать, так что ряд равенств (*) закончится так:
b k-2 n k-1 + b k,
b k-1 n k b k.
Последний положительный остаток b к в этом процессе и является наибольшим общим делителем чисел а и b. Е. а. служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины ) Е. а. оказывается бесконечным.