ЕВКЛИ́ДА АЛГОРИ́ТМ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
ЕВКЛИ́ДА АЛГОРИ́ТМ, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрич. форме Евклидом. Для случая положительных целых чисел $a$ и $b$ таких, что $a⩾b$, Е. а. состоит в следующем. Деление с остатком числа $a$ на число $b$ приводит к результату $a=nb+b_1$, где частное $n$ является целым положительным числом, а остаток $b_1$ – либо нуль, либо целое положительное число, меньшее $b, 0\leqslant b_1 \lt b$. Производится последовательное деление: $$\left. \begin{array}{l} a=nb+b_1.\\ b=n_1b_1+b_2,\\ b_1=n_2b_2+b_3,\\.............. \end{array} \right\} \tag{*}$$где все $n_i$ – положительные целые числа и $0\leqslant b_i \lt b_{i–1}, i⩾2$, до тех пор пока при некотором натуральном $k$ не получится остаток $b_{k+1}=0$. Остаток $b_{k+1}$ можно не писать, поэтому ряд равенств $(*)$ закончится так: $$b_{k-2}=n_{k-1}b_{k-1}+b_k,\\ b_{k-1}=n_kb_k.$$
Последний положительный остаток $b_k$ в этом процессе является наибольшим общим делителем чисел $a$ и $b$. В случае многочленов или отрезков поступают сходным образом. Для несоизмеримых отрезков, т. е. отрезков, отношение длин которых иррационально, Е. а. приводит к бесконечному процессу.