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
{\displaystyle i}
c
0
=
m
=
196
{\displaystyle c_{0}=m=196}
d
0
=
n
=
34
{\displaystyle d_{0}=n=34}
p
i
{\displaystyle p_{i}}
c
i
/
d
i
{\displaystyle c_{i}/d_{i}}
z
i
{\displaystyle z_{i}}
c
i
/
d
i
{\displaystyle c_{i}/d_{i}}
c
i
=
d
i
p
i
+
z
i
{\displaystyle c_{i}=d_{i}p_{i}+z_{i}}
z
i
=
c
i
−
d
i
p
i
(
1
)
{\displaystyle z_{i}=c_{i}-d_{i}p_{i}\qquad (1)}
a pre každé
i
=
1
,
2
,
3
,
.
.
.
{\displaystyle i=1,2,3,...}
c
i
=
d
i
−
1
(
2
)
d
i
=
z
i
−
1
(
3
)
{\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
a
{\displaystyle a}
b
{\displaystyle b}
2
=
196
a
+
34
b
{\displaystyle 2=196a+34b}
Nájdenie Bézoutovej rovnosti spätným dosadzovaním
upraviť
V uvedenom príklade platí:
2
=
26
−
8
⋅
3
(
4
)
8
=
34
−
26
⋅
1
(
5
)
26
=
196
−
34
⋅
5
(
6
)
{\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:
2
=
34
⋅
(
−
3
)
+
26
⋅
4
(
7
)
{\displaystyle 2=34\cdot (-3)+26\cdot 4\qquad (7)}
a dosadením ľavej strany rovnosti (6) do rovnosti (7) dostaneme výsledok:
2
=
196
⋅
4
+
34
⋅
(
−
23
)
(
8
)
{\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
k
{\displaystyle k}
d
=
N
S
D
(
m
,
n
)
=
d
k
{\displaystyle d=NSD(m,n)=d_{k}}
z
k
=
0
{\displaystyle z_{k}=0}
d
{\displaystyle d}
c
i
{\displaystyle c_{i}}
d
i
{\displaystyle d_{i}}
i
=
k
,
k
−
1
,
.
.
.
,
0
{\displaystyle i=k,k-1,...,0}
d
=
c
i
u
i
+
d
i
v
i
(
9
)
{\displaystyle 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
(
10
)
{\displaystyle d=d_{i-1}u_{i}+z_{i-1}v_{i}\qquad (10)}
a dosadením (1) do (10):
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
)
(
11
)
{\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:
u
i
−
1
=
v
i
(
12
)
v
i
−
1
=
u
i
−
p
i
−
1
v
i
(
13
)
{\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í:
d
=
d
k
=
c
k
⋅
0
+
d
k
⋅
1
{\displaystyle d=d_{k}=c_{k}\cdot 0+d_{k}\cdot 1}
preto:
u
k
=
0
(
14
)
v
k
=
1
(
15
)
{\displaystyle {\begin{array}{lcll}u_{k}&=&0&\qquad (14)\\v_{k}&=&1&\qquad (15)\end{array}}}
Formálny zápis
upraviť
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
{\displaystyle u_{i}}
v
i
{\displaystyle v_{i}}
p
i
{\displaystyle p_{i}}
Použitie na konkrétnom príklade
upraviť
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ť
Nech
k
{\displaystyle k}
d
=
N
S
D
(
m
,
n
)
=
d
k
{\displaystyle d=NSD(m,n)=d_{k}}
z
k
=
0
{\displaystyle z_{k}=0}
i
=
0
,
1
,
2
,
.
.
.
,
k
−
1
{\displaystyle i=0,1,2,...,k-1}
z
i
{\displaystyle z_{i}}
m
{\displaystyle m}
n
{\displaystyle n}
a
i
{\displaystyle a_{i}}
b
i
{\displaystyle b_{i}}
z
i
=
m
a
i
+
n
b
i
(
16
)
{\displaystyle z_{i}=ma_{i}+nb_{i}\qquad (16)}
Pre
i
=
0
{\displaystyle i=0}
z
0
=
c
0
−
d
0
p
0
=
m
−
n
p
0
(
17
)
{\displaystyle {\begin{array}{lclr}z_{0}&=&c_{0}-d_{0}p_{0}\\&=&m-np_{0}&\qquad (17)\end{array}}}
preto
a
0
=
1
(
18
)
b
0
=
−
p
0
(
19
)
{\displaystyle {\begin{array}{lclr}a_{0}&=&1&\qquad (18)\\b_{0}&=&-p_{0}&\qquad (19)\end{array}}}
Pre
i
=
1
{\displaystyle i=1}
z
1
=
c
1
−
d
1
p
1
(
20
)
{\displaystyle {\begin{array}{lclr}z_{1}&=&c_{1}-d_{1}p_{1}&\qquad (20)\end{array}}}
a podľa (2) a (3):
c
1
=
d
0
=
n
d
1
=
z
0
{\displaystyle {\begin{array}{lclcl}c_{1}&=&d_{0}&=&n\\d_{1}&=&z_{0}\end{array}}}
Preto
z
1
=
n
−
z
0
p
1
{\displaystyle {\begin{array}{lcl}z_{1}&=&n-z_{0}p_{1}\end{array}}}
Po dosadení za
z
0
{\displaystyle z_{0}}
z
1
=
n
−
m
p
1
+
n
p
0
p
1
=
−
m
p
1
+
n
(
1
+
p
0
p
1
)
(
21
)
{\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
a
1
=
−
p
1
(
22
)
b
1
=
1
+
p
0
p
1
(
23
)
{\displaystyle {\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
{\displaystyle i>1}
c
i
=
d
i
−
1
=
z
i
−
2
d
i
=
z
i
−
1
{\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:
z
i
=
c
i
−
d
i
p
i
=
z
i
−
2
−
z
i
−
1
p
i
{\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
i
−
1
{\displaystyle i-1}
i
−
2
{\displaystyle i-2}
z
i
=
m
a
i
−
2
+
n
b
i
−
2
−
(
m
a
i
−
1
+
n
b
i
−
1
)
p
i
=
m
(
a
i
−
2
−
a
i
−
1
p
i
)
+
n
(
b
i
−
2
−
b
i
−
1
p
i
)
{\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é
i
>
1
{\displaystyle i>1}
a
i
=
a
i
−
2
−
a
i
−
1
p
i
(
24
)
b
i
=
b
i
−
2
−
b
i
−
1
p
i
(
25
)
{\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
z
i
{\displaystyle z_{i}}
a
i
{\displaystyle a_{i}}
b
i
{\displaystyle b_{i}}
i
=
−
1
{\displaystyle i=-1}
i
=
−
2
{\displaystyle i=-2}
z
−
2
=
m
,
a
−
2
=
1
,
b
−
2
=
0
z
−
1
=
n
,
a
−
1
=
0
,
b
−
1
=
1
{\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
a
0
,
a
1
,
b
0
,
b
1
{\displaystyle a_{0},a_{1},b_{0},b_{1}}
Formálny zápis
upraviť
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
{\displaystyle a_{i},b_{i}}
Použitie na konkrétnom príklade
upraviť
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
Wikiknihy ponúkajú texty a príručky na tému Rozšírený Euklidov algoritmus