Rozšírený Euklidov algoritmus

Tento článok alebo jeho časť si vyžaduje úpravu, aby zodpovedal vyššiemu štandardu kvality. Prosím, pozrite si stránky pomocníka, odporúčanie pre encyklopedický štýl a článok vhodne upravte.

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.

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 ${\displaystyle i}$ je iterácia, ${\displaystyle c_{0}=m=196}$, ${\displaystyle d_{0}=n=34}$, ${\displaystyle p_{i}$ je celočíselný podiel ${\displaystyle c_{i}/d_{i}$, ${\displaystyle z_{i}$ je zvyšok po delení ${\displaystyle c_{i}/d_{i}$, čiže platí ${\displaystyle c_{i}=d_{i}p_{i}+z_{i}$, resp:

${\displaystyle z_{i}=c_{i}-d_{i}p_{i}\qquad (1)}$

a pre každé ${\displaystyle i=1,2,3,...}$ je

${\displaystyle {\begin{array}{lcll}c_{i}&=&d_{i-1}&\qquad (2)\\d_{i}&=&z_{i-1}&\qquad (3)\end{array}$

Úlohou Rozšíreného Euklidovho algoritmu je nájsť dvojicu celých čísel ${\displaystyle a}$ a ${\displaystyle b}$, spĺňajúcu rovnosť ${\displaystyle 2=196a+34b}$.

V uvedenom príklade platí:

${\displaystyle {\begin{array}{lcll}2&=&26-8\cdot 3&\qquad (4)\\8&=&34-26\cdot 1&\qquad (5)\\26&=&196-34\cdot 5&\qquad (6)\end{array}$

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

${\displaystyle 2=34\cdot (-3)+26\cdot 4\qquad (7)}$

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

${\displaystyle 2=196\cdot 4+34\cdot (-23)\qquad (8)}$

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

Nech ${\displaystyle k}$ je iterácia v Euklidovom algoritme, v ktorej bol nájdený najväčší spoločný deliteľ dvoch kladných celých čísel ${\displaystyle d=NSD(m,n)=d_{k}$, čiže pre ktoré platí ${\displaystyle z_{k}=0}$. Spätným dosadením vyjadríme najväčší spoločný deliteľ ${\displaystyle d}$ ako lineárnu kombináciu ${\displaystyle c_{i}$ a ${\displaystyle d_{i}$ postupne pre každé ${\displaystyle i=k,k-1,...,0}$, t.j:

${\displaystyle d=c_{i}u_{i}+d_{i}v_{i}\qquad (9)}$

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

${\displaystyle d=d_{i-1}u_{i}+z_{i-1}v_{i}\qquad (10)}$

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

${\displaystyle {\begin{alignedat}{2}d&=d_{i-1}u_{i}+(c_{i-1}-d_{i-1}p_{i-1})v_{i}\\&=c_{i-1}v_{i}+d_{i-1}(u_{i}-p_{i-1}v_{i})\qquad (11)\end{alignedat}$

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

${\displaystyle {\begin{array}{lcll}u_{i-1}&=&v_{i}&\qquad (12)\\v_{i-1}&=&u_{i}-p_{i-1}v_{i}&\qquad (13)\end{array}$

Tiež platí:

${\displaystyle d=d_{k}=c_{k}\cdot 0+d_{k}\cdot 1}$

preto:

${\displaystyle {\begin{array}{lcll}u_{k}&=&0&\qquad (14)\\v_{k}&=&1&\qquad (15)\end{array}$

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 ${\displaystyle u_{i}$ a ${\displaystyle v_{i}$ je potrebné mať k dispozícii aj všetky hodnoty ${\displaystyle p_{i}$.

Nech ${\displaystyle k}$ je iterácia v Euklidovom algoritme, v ktorej bol nájdený najväčší spoločný deliteľ dvoch kladných celých čísel ${\displaystyle d=NSD(m,n)=d_{k}$, čiže pre ktoré platí ${\displaystyle z_{k}=0}$. Pre každé ${\displaystyle i=0,1,2,...,k-1}$ vyjadrime ${\displaystyle z_{i}$ ako lineárnu kombináciu čísel ${\displaystyle m}$ a ${\displaystyle n}$, t.j. hľadáme dvojicu celých čísel ${\displaystyle a_{i}$ a ${\displaystyle b_{i}$, pre ktoré platí ${\displaystyle z_{i}=ma_{i}+nb_{i}\qquad (16)}$

• Pre ${\displaystyle i=0}$ z rovnosti (1) vyplýva:

${\displaystyle {\begin{array}{lclr}z_{0}&=&c_{0}-d_{0}p_{0}\\&=&m-np_{0}&\qquad (17)\end{array}$

preto

${\displaystyle {\begin{array}{lclr}a_{0}&=&1&\qquad (18)\\b_{0}&=&-p_{0}&\qquad (19)\end{array}$

• Pre ${\displaystyle i=1}$ z (1) vyplýva:

${\displaystyle {\begin{array}{lclr}z_{1}&=&c_{1}-d_{1}p_{1}&\qquad (20)\end{array}$

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

${\displaystyle {\begin{array}{lclcl}c_{1}&=&d_{0}&=&n\\d_{1}&=&z_{0}\end{array}$

Preto

${\displaystyle {\begin{array}{lcl}z_{1}&=&n-z_{0}p_{1}\end{array}$

Po dosadení za ${\displaystyle z_{0}$ zo (17) dostaneme:

${\displaystyle {\begin{array}{lclr}z_{1}&=&n-mp_{1}+np_{0}p_{1}\\&=&-mp_{1}+n(1+p_{0}p_{1})&\qquad (21)\end{array}$

A teda

${\displaystyle {\begin{array}{lclr}a_{1}&=&-p_{1}&\qquad (22)\\b_{1}&=&1+p_{0}p_{1}&\qquad (23)\end{array}$

• Pre ľubovoľné ${\displaystyle i>1}$ je podľa (2) a (3):

${\displaystyle {\begin{array}{lclcl}c_{i}&=&d_{i-1}&=&z_{i-2}\\d_{i}&=&z_{i-1}\end{array}$

Dosadením do (1) dostávame:

${\displaystyle {\begin{array}{lclcl}z_{i}&=&c_{i}-d_{i}p_{i}&=&z_{i-2}-z_{i-1}p_{i}\end{array}$

Ak poznáme (16) pre ${\displaystyle i-1}$ a ${\displaystyle i-2}$, dostávame:

${\displaystyle {\begin{array}{lcl}z_{i}&=&ma_{i-2}+nb_{i-2}-(ma_{i-1}+nb_{i-1})p_{i}\\&=&m(a_{i-2}-a_{i-1}p_{i})+n(b_{i-2}-b_{i-1}p_{i})\end{array}$

Preto pre ľubovoľné ${\displaystyle i>1}$ je:

${\displaystyle {\begin{array}{lclr}a_{i}&=&a_{i-2}-a_{i-1}p_{i}&\qquad (24)\\b_{i}&=&b_{i-2}-b_{i-1}p_{i}&\qquad (25)\end{array}$

• Ak sa nasledujúcim spôsobom zadefinujú hodnoty ${\displaystyle z_{i}$, ${\displaystyle a_{i}$ a ${\displaystyle b_{i}$ aj pre ${\displaystyle i=-1}$ a ${\displaystyle i=-2}$:

${\displaystyle {\begin{array}{lcllcllcl}z_{-2}&=&m,&a_{-2}&=&1,&b_{-2}&=&0\\z_{-1}&=&n,&a_{-1}&=&0,&b_{-1}&=&1\end{array}$

bude rovnosť (16) platiť aj pre ne a vzťahy (24), (25) je možné použiť aj na zistenie ${\displaystyle a_{0},a_{1},b_{0},b_{1}$.

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 ${\displaystyle a_{i},b_{i}$.

• KNUTH, Donald. Umění programování. 1. vyd. Zväzok 1. Základní algoritmy. Brno : Computer Press, 2008. ISBN 978-80-251-2025-5. Kapitola 1. Základní principy.

• Wikiknihy ponúkajú texty a príručky na tému Rozšírený Euklidov algoritmus