Rozšířený Eukleidův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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
  1. Je-li b = 0, položte d:=a, α:=1, β:=0 a skončete
  2. Položte α2:= 1, α1:= 0, β2:= 0, β1:= 1
  3. Dokud b > 0 dělejte následující
    1. Spočtěte q a r tak, že a = q·b + r, 0 ≤ r < b
    2. Položte a:= b, b:= r
    3. Položte α2:= α1, α1:= α2 - q*α1, β2:= β1, β1:= β2 - q*β1

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

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

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

Související články[editovat | editovat zdroj]