Išplėstinis Euklido algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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[taisyti | redaguoti kodą]

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_1q_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}

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[taisyti | redaguoti kodą]

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) + (4632) × 7 = 32 × (-10) + 46 × 7.