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.

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

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

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.

Odvodenie

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

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---