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

Алгори́тм Евкли́да, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом. Для случая положительных целых чисел ${\displaystyle a}$ и ${\displaystyle b}$ таких, что ${\displaystyle a\geqslant b}$, алгоритм Евклида состоит в следующем. Деление с остатком числа ${\displaystyle a}$ на число ${\displaystyle b}$ приводит к результату ${\displaystyle a=nb+b_{1}}$, где частное ${\displaystyle n}$ является целым положительным числом, а остаток ${\displaystyle b_{1}}$ – либо нуль, либо целое положительное число, меньшее ${\displaystyle b,0\leqslant b_{1}<b}$. Производится последовательное деление:

${\displaystyle \left.{\begin{array}{l}a=nb+b_{1}.\\b=n_{1}b_{1}+b_{2},\\b_{1}=n_{2}b_{2}+b_{3},\\..............\end{array}}\right\}}$ (*)

где все ${\displaystyle n_{i}}$ – положительные целые числа и ${\displaystyle 0\leqslant b_{i}<b_{i-1},i\geqslant 2}$, до тех пор пока при некотором натуральном ${\displaystyle k}$ не получится остаток ${\displaystyle b_{k+1}=0}$. Остаток ${\displaystyle b_{k+1}}$ можно не писать, поэтому ряд равенств ${\displaystyle (*)}$ закончится так:

${\displaystyle {\begin{aligned}b_{k-2}=n_{k-1}b_{k-1}+b_{k},\\b_{k-1}=n_{k}b_{k}\end{aligned}}}$.

Последний положительный остаток ${\displaystyle b_{k}}$ в этом процессе является наибольшим общим делителем чисел ${\displaystyle a}$ и ${\displaystyle b}$. В случае многочленов или отрезков поступают сходным образом. Для несоизмеримых отрезков, т. е. отрезков, отношение длин которых иррационально, алгоритм Евклида приводит к бесконечному процессу.