Jednou z efektívnych metód, ktorou hľadáme najväčší spoločný deliteľ dvoch prirodzených čísel, je Euklidov algoritmus. Je založený na nasledujúcom poznatku.
|
Nech prirodzené číslo d je deliteľom prirodzených čísel a a b, a > b
. Potom d je aj deliteľom čísla a - b
.
|
|
Nech prirodzené číslo d je deliteľom prirodzených čísel a a b, a > b
. Potom d je aj deliteľom čísla c
, ktoré je zvyškom po delení čísla b číslom a
.
|
O platnosti tohto poznatku sa poľahky presvedčíme.
Ak d je deliteľom a, potom existuje také prirodzené číslo k, že a = d ∙ k. Podobne, ak d je deliteľom b, potom existuje také prirodzené číslo l, že b = d ∙ l.
Potom a - b = d ∙ k - d ∙ l = d (k - l), a teda d je deliteľom čísla a - b.
Ak a - b je menšie ako b, potom je zvyškom po delení čísla a číslom b, a teda d je deliteľom čísla c. Ak a - b nie je menšie ako b, potom podľa prvej časti tvrdenia d je aj deliteľom čísla a - 2b. Takto by sme mohli pokračovať, až kým dostaneme, že d je deliteľom čísla c.