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

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_ip_i + z_i,
resp:
::z_i = c_i - d_ip_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_iu_i + d_iv_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{alignat}{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{alignat}

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

## 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_0p_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_1p_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_0p_1
\end{array}

:Po dosadení za z_0 zo (17) dostaneme:
::\begin{array}{lclr}
z_1 & = & n - mp_1 + np_0p_1\\
& = & -mp_1+n(1+p_0p_1) & \qquad (21)
\end{array}

:A teda
::\begin{array}{lclr}
a_1 & = & -p_1 & \qquad (22)\\
b_1 & = & 1+p_0p_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_ip_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

## Zdroj
* 

## Iné projekty

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