Začneme nalezením největšího společného dělitele čísel 527 a 341 pomocí standardního euklidovského algoritmu jako rozcvičku:
Standardní algoritmus je stručný a jednoduchý a poslouží jako malý pěkný návod pro implementaci rozšířeného algoritmu.
Pro rozšířený euklidovský algoritmus vezmeme třetí rovnici (modře), od obou stran odečteme 155(1) a provedeme malé přeskupení, abychom získali ekvivalentní rovnici, kde je 31 izolováno.
Dále nahradíme 155 číslem 341-186(1), které najdeme vyřešením druhé rovnice pro 155, čímž získáme následující:
Nyní to vyčistíme. Dbejte na to, abyste přes závorku rozdělili záporné znaménko a 186 + 186 nahradili 186-2.
Jak si můžete všimnout, jednoduše postupujeme zpětně standardním algoritmem. Tento postup budeme muset provést ještě jednou, abychom získali rovnici zahrnující 527 a 341, což je nakonec naším cílem.
Pro tento účel nahraďte číslo 186 číslem 527 – 341(1), které pochází z první rovnice, když řešíme číslo 186.
Rovnici opět zjednodušíme tak, že rozdělíme 2 a spojíme do skupin 527 a 341.
Nyní jsme vyjádřili 31 jako lineární kombinaci 527 a 341. To znamená, že jsme vyjádřili 31 jako lineární kombinaci. Pěkně husté, co?“
Navíc číslo na opačné straně lineární kombinace je největším společným dělitelem. V tomto případě je tedy 31 největším společným dělitelem čísel 527 a 341.
Rozšířený euklidovský algoritmus je užitečný, protože dává Bezoutovu identitu a také zvýrazňuje gcd.
Díky za přečtení!