Išplėstinis Euklido algoritmas

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

Algoritmas

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

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

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

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

…

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

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

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

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

Pavyzdys

Imkime $a$ = 46, $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.