Rozšírený Euklidov algoritmus

Rozšírený Euklidov algoritmus je algoritmus, ktorým je možné nájsť Bézoutovú rovnosť, čiže vyjadriť najväčší spoločný deliteľ (NSD) dvoch kladných celých čísel ich lineárnou kombináciou.

Príklad 
Nech sú dané dve kladné celé čísla m a n a nech d je ich najväčší spoločný deliteľ, t.j. d = NSD(m,n). Pomocou Euklidovho algoritmu je možné zistiť, že NSD(196,34) = 2:

kde  je iterácia, , ,  je celočíselný podiel ,  je zvyšok po delení , čiže platí ,
resp:

a pre každé  je

Úlohou Rozšíreného Euklidovho algoritmu je nájsť dvojicu celých čísel  a , spĺňajúcu rovnosť .

Nájdenie Bézoutovej rovnosti spätným dosadzovaním 

V uvedenom príklade platí:

Dosadením ľavej strany rovnosti (5) do rovnosti (4) dostaneme:

a dosadením ľavej strany rovnosti (6) do rovnosti (7) dostaneme výsledok:

t.j. jednu z možností, ako vyjadriť najväčší spoločný deliteľ dvoch čísel ich lineárnou kombináciou.

Odvodenie 

Nech  je iterácia v Euklidovom algoritme, v ktorej bol nájdený najväčší spoločný deliteľ dvoch kladných celých čísel , čiže pre ktoré platí .
Spätným dosadením vyjadríme najväčší spoločný deliteľ  ako lineárnu kombináciu  a  postupne pre každé , t.j:

Dosadením (2) a (3) do (9) dostaneme:

a dosadením (1) do (10):

Porovnaním (11) a (9) dostávame výsledok:

Tiež platí:

preto:

Formálny zápis 

1. [Inicializácia premenných.]  Priraďte i ← k, u ← 0, v ← 1.

2. [Ukončovacia podmienka.]  Ak i = 0 tak koniec, pričom NSD(m,n) = m·u + n·v

3. [Výpočet u a v.]  Priraďte u_new ← v, v_new ← u - p[i-1]·v.

4. [Ďalšia iterácia.]  Priraďte i ← i-1, u ← u_new, v ← v_new. Vráťte sa do bodu 2.

Poznámka: Výpočet prebieha opačným smerom než výpočet NSD a okrem naposledy vypočítanej dvojice hodnôt  a  je potrebné mať k dispozícii aj všetky hodnoty .

Použitie na konkrétnom príklade

Rozšírený Euklidov algoritmus

Odvodenie 

Nech  je iterácia v Euklidovom algoritme, v ktorej bol nájdený najväčší spoločný deliteľ dvoch kladných celých čísel , čiže pre ktoré platí . Pre každé  vyjadrime  ako lineárnu kombináciu čísel  a , t.j. hľadáme dvojicu celých čísel  a , pre ktoré platí  
 
 Pre  z rovnosti (1) vyplýva: 

preto

 
 Pre  z (1) vyplýva: 

a podľa (2) a (3):

Preto

Po dosadení za  zo (17) dostaneme:

A teda

 
 Pre ľubovoľné  je podľa (2) a (3):

Dosadením do (1) dostávame:

Ak poznáme (16) pre  a , dostávame:

Preto pre ľubovoľné  je:

 Ak sa nasledujúcim spôsobom zadefinujú hodnoty ,  a  aj pre  a :

bude rovnosť (16) platiť aj pre ne a vzťahy (24), (25) je možné použiť aj na zistenie .

Formálny zápis 

1. [Inicializácia premenných.]  Priraďte c ← m, d ← n, a_old ← 1, b_old ← 0, a ← 0, b ← 1.

2. [Výpočet podielu a zvyšku.]  Vypočítajte celočíselný podiel p a zvyšok z po delení c / d. 

3. [Ukončovacia podmienka.]  Ak z = 0 tak koniec, pričom NSD(m,n) = d = m·a + n·b

4. [Výpočet a a b.]  Priraďte a_new ← a_old - a·p, b_new ← b_old - b·p.

5. [Redukcia.]  Priraďte c ← d, d ← z, a_old ← a, a ← a_new, b_old ← b, b ← b_new. Vráťte sa do bodu 2.

Poznámka: Výpočet prebieha súčasne s výpočtom NSD pričom je potrebné mať k dispozícii aj dve posledné dvojice hodnôt .

Použitie na konkrétnom príklade

Zdroj

Iné projekty 

Teória čísel
Algoritmy