Išplėstinis Euklido algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Išplėstinis Euklido algoritmas yra Euklido algoritmo tęsinys, skirtas rasti dviejų natūraliųjų skaičių , didžiausią bendrą daliklį, bei rasti sveikuosius , , tenkinančius

[taisyti] 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₁ + r₁, kur 0 < r₁ < r

r = r₁q₂ + r₂, kur 0 < r₂ < r₁

...

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₁ > ... > 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)

[taisyti] 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.