Išplėstinis Euklido algoritmas

Išplėstinis Euklido algoritmas – Euklido algoritmo tęsinys, skirtas rasti dviejų natūraliųjų skaičių ${\displaystyle a\,}$,${\displaystyle b\,}$ didžiausią bendrą daliklį, bei rasti sveikuosius ${\displaystyle x\,}$, ${\displaystyle y\,}$, tenkinančius ${\displaystyle ax+by=dbd(a,b).\,}$

Algoritmas

Nemažindami bendrumo tarkime, kad ${\displaystyle a>b}$ Tuomet ${\displaystyle a}$ užsirašo kaip

${\displaystyle a=bq+r}$, kur dalybos liekana tenkina ${\displaystyle 0<r<b}$. Analogiškai

${\displaystyle b=rq_{1}+r_{1}}$, kur ${\displaystyle 0<r_{1}<r}$

${\displaystyle r=r_{1}q_{2}+r_{2}}$, kur ${\displaystyle 0<r_{2}<r_{1}}$

…

${\displaystyle r_{k}=r_{k+1}q_{k+2}+r_{k+2}}$, kur ${\displaystyle 0<r_{k+2}<r_{k+1}}$

${\displaystyle r_{k+1}=r_{k+2}q_{k+3}}$

Iš ${\displaystyle r>r_{1}>...>r_{k+2}}$ seka, kad kažkada gausime dalybos liekaną lygią 0. Tuomet paskutinioji nenulinė liekana ${\displaystyle r_{k+2}}$ ir bus didžiausias bendrasis daliklis.

Iš prieš paskutinės lygybės galime išreikšti ${\displaystyle r_{k+2}}$ per ${\displaystyle r_{k+1}}$ ir ${\displaystyle r_{k}}$. Iš dar ankstesnės galima išreikšti ${\displaystyle r_{k+1}}$ per ${\displaystyle r_{k}}$ ir ${\displaystyle r_{k-1}}$. Įstatę į pirmąją išraišką gausime ${\displaystyle r_{k+2}}$ išraišką per ${\displaystyle r_{k}}$ ir ${\displaystyle r_{k-1}}$. Taip toliau vis tęsdami gausime ${\displaystyle r_{k+2}}$ išraišką per a, b, t. y. rasime x, y, tenkinančius ax + by = dbd(a, b)

Pavyzdys

Imkime ${\displaystyle a}$ = 46, ${\displaystyle b}$ = 32. Nuosekliai atlikdami veiksmus gauname:

46 = 32 × 1 + 14;

32 = 14 × 2 + 4;

14 = 4 × 3 + 2;

4 = 2 × 2;

Gavome, kad dbd(46,32) = 2.

2 = 14 + 4 × (-3) = 14 + (32 + 14× (-2)) × (-3) = 32 × (-3) + 14 × 7 = 32 × (-3) + (46 – 32) × 7 = 32 × (-10) + 46 × 7.

Šaltiniai

1. „21-110: The extended Euclidean algorithm“. math.cmu.edu. Nuoroda tikrinta 2024-02-03.