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:
icidipizi019634526134261822683238240
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 

icidipiziuivi0196345264-231342618-342268321-33824001

 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 

icidipiziaibi-219610-134010196345261-51342618-162268324-2338240

 Zdroj 


 Iné projekty 

Kategória:Teória čísel
Kategória:Algoritmy
Euklidov algoritmus, rozšírený