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	c_i	d_i	p_i	z_i
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	c_i	d_i	p_i	z_i	u_i	v_i
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	c_i	d_i	p_i	z_i	a_i	b_i
-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 ponúkajú texty a príručky na tému Rozšírený Euklidov algoritmus