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

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

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

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