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

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

. Для слу­чая по­ло­жи­тель­ных це­лых чи­сел $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$. В слу­чае мно­го­чле­нов или от­рез­ков по­сту­па­ют сход­ным об­ра­зом. Для не­со­из­ме­ри­мых от­рез­ков, т. е. от­рез­ков, от­но­ше­ние длин ко­то­рых ир­ра­цио­наль­но, Е. а. при­во­дит к бес­ко­неч­но­му про­цес­су.