Išplėstinis Euklido algoritmas

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

Algoritmas 

Nemažindami bendrumo tarkime, kad  Tuomet  užsirašo kaip

, kur dalybos liekana tenkina . Analogiškai

, kur 

, kur 

…

, kur 

Iš  seka, kad kažkada gausime dalybos liekaną lygią 0. Tuomet paskutinioji nenulinė liekana  ir bus didžiausias bendrasis daliklis.

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

Pavyzdys 

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

Algoritmai
Skaičių teorija