Rozšířený Eukleidův algoritmus

Rozšířený Eukleidův algoritmus je algoritmus, kterým lze nalézt Bézoutovu rovnost, neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací.

Příklad Vstup: Přirozená čísla a, b, kde a ≥ b ≥ 0 Výstup: d = NSD(a,b) a celá čísla α, β splňující podmínku d = α·a + β·b Je-li b = 0, položte d:=a, α:=1, β:=0 a skončete Položte i:= 0, α20:= 1, α10:= 0, β20:= 0, β10:= 1 Dokud b > 0 dělejte následující: i:= i+1 Spočtěte q a r tak, že a = q·b + r, 0 ≤ r < b Položte α2i:= α1i-1, α1i:= α2i-1 – q*α1i-1, β2i:= β1i-1, β1i:= β2i-1 – q*β1i-1 Položte a:= b, b:= r

Položte d:= a, α:= α2i, β:= β2i

NSD(427, 133) = α · 427 + β · 133

Výsledkem uvedeného příkladu je NSD(427, 133) = 7

Bezoutovu rovnost lze zapsat 7 = 5 · 427 + -16 · 133

i a b q r α2i α1i β2i β1i 0 427 133 1 0 0 1 1 133 28 3 28 0 1 1 -3 2 28 21 4 21 1 -4 -3 13 3 21 7 1 7 -4 5 13 -16 4 7 0 3 0 5 -19 -16 61

Související články Eukleidův algoritmus

Kategorie:Teorie čísel