Teraz prejdeme k Euklidovmu algoritmu.
|
Najväčší spoločný deliteľ prirodzených čísel a a b, a > b určíme takto:
|
|
1. Väčšie z čísel a a b nahradíme zvyškom po delení väčšieho čísla menším.
|
|
2. Ak menšie z čísel je nula, najväčším spoločným deliteľom je väčšie z čísel. Inak pokračujeme bodom 1.
|
Postup si vysvetlíme na príklade. Chceme nájsť najväčší spoločný deliteľ čísel 4 567 a 754.
Pretože 4 567 > 754, číslo 4 567 nahradíme zvyškom po delení čísla 4 567 číslom 754, teda číslom 43.
Pretože 754 > 43, číslo 754 nahradíme zvyškom po delení čísla 754 číslom 43, teda číslom 23.
Pretože 43 > 23, číslo 43 nahradíme zvyškom po delení čísla 43 číslom 23, teda číslom 20.
Pretože 23 > 20, číslo 23 nahradíme zvyškom po delení čísla 23 číslom 20, teda číslom 3.
Pretože 20 > 3, číslo 20 nahradíme zvyškom po delení čísla 20 číslom 3, teda číslom 2.
Pretože 3 > 2, číslo 3 nahradíme zvyškom po delení čísla 3 číslom 2, teda číslom 1.
Pretože 2 > 1, číslo 2 nahradíme zvyškom po delení čísla 2 číslom 1, teda číslom 0.
Zostali nám čísla 1 a 0. Pretože menšie z nich je nula, väčšie z nich je najväčším spoločným deliteľom čísel 4 567 a 754. Zároveň je aj najväčším spoločným deliteľom čísel 754 a 43, čísel 43 a 23, čísel 23 a 20, čísel 20 a 3, čísel 3 a 2 a čísel 2 a 1.
Teda: (4 567,754) = (754,43) = (43,23) = (23,20) = (20,3) = (3,2) = (2,1) = 1.