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:

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

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

a pre každé $i=1,2,3,...$ je

${\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 $a$ a $b$, spĺňajúcu rovnosť $2=196a+34b$.

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

V uvedenom príklade platí:

${\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:

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

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

$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.

Odvodenie

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

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

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

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

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

${\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:

${\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í:

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

preto:

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

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

Použitie na konkrétnom príklade

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

Odvodenie

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

• Pre $i=0$ z rovnosti (1) vyplýva:

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

preto

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

• Pre $i=1$ z (1) vyplýva:

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

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

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

Preto

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

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

${\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

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

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

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

Dosadením do (1) dostávame:

${\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 $i-1$ a $i-2$, dostávame:

${\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é $i>1$ je:

${\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 $z_{i}$, $a_{i}$ a $b_{i}$ aj pre $i=-1$ a $i=-2$:

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

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

Použitie na konkrétnom príklade

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

• 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.

Iné projekty

Wikiknihy

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