Rozšírený Euklidov algoritmus

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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[upraviť | upraviť kód]

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:

i ci di pi zi
0 196 34 5 26
1 34 26 1 8
2 26 8 3 2
3 8 2 4 0

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[upraviť | upraviť kód]

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[upraviť | upraviť kód]

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[upraviť | upraviť kód]

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[upraviť | upraviť kód]

i ci di pi zi ui vi
0 196 34 5 26 4 -23
1 34 26 1 8 -3 4
2 26 8 3 2 1 -3
3 8 2 4 0 0 1

Rozšírený Euklidov algoritmus[upraviť | upraviť kód]

Odvodenie[upraviť | upraviť kód]

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[upraviť | upraviť kód]

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[upraviť | upraviť kód]

i ci di pi zi ai bi
-2 196 1 0
-1 34 0 1
0 196 34 5 26 1 -5
1 34 26 1 8 -1 6
2 26 8 3 2 4 -23
3 8 2 4 0

Zdroj[upraviť | upraviť kód]

Iné projekty[upraviť | upraviť kód]