Алгоритм Евклида
Алгори́тм Евкли́да, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом. Для случая положительных целых чисел и таких, что , алгоритм Евклида состоит в следующем. Деление с остатком числа на число приводит к результату , где частное является целым положительным числом, а остаток – либо нуль, либо целое положительное число, меньшее . Производится последовательное деление: где все – положительные целые числа и , до тех пор пока при некотором натуральном не получится остаток . Остаток можно не писать, поэтому ряд равенств закончится так: Последний положительный остаток в этом процессе является наибольшим общим делителем чисел и . В случае многочленов или отрезков поступают сходным образом. Для несоизмеримых отрезков, т. е. отрезков, отношение длин которых иррационально, алгоритм Евклида приводит к бесконечному процессу.