lub przepisując wszystkie równości w taki sposób, by w pierwszej z nich po prawej stronie występowała tylko suma pewnych wielokrotności liczb 174 i 18:
Należy zauważyć, że w pierwszej równości po prawej stronie występuje kombinacja liniowa liczb 174 i 18, podobnie jak w równaniu W następnych równościach po prawej stronie jest zawsze kombinacja liniowa liczb 174, 18 lub liczb, które wystąpiły po lewej stronie we wcześniejszych równościach.
Kluczowa dla rozszerzonego algorytmu Euklidesa staje się możliwość stopniowego zastępowania tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania równości:
np.
Pseudokod
funkcja NWD(a, b) x := 1 y := 0 r := 0 s := 1
dopóki b ≠ 0 c := a mod b # reszta z dzielenia a przez b q := a // b # część całkowita z dzielenia a przez b a := b b := c
r' := r s' := s r := x - q · r s := y - q · s x := r' y := s'
zwróć a, x, y
Niezmiennikami pętli są wielkości x · a0 + y · b0 = a oraz r · a0 + s · b0 = b, dzięki czemu NWD(a0, b0) = x · a0 + y · b0.
Zobacz też implementacje algorytmu Euklidesa największy wspólny dzielnik rozkład na czynniki
Przypisy