Euklidov algoritmus

Euklidov algoritmus je v teórii čísel algoritmus na určenie najväčšieho spoločného deliteľa dvoch prirodzených čísel. Je pomenovaný podľa starogréckeho matematika Euklida, ktorý ho opísal v siedmej a desiatej knihe svojich Základov.

Algoritmus 

Euklidov algoritmus využíva nasledujúcu skutočnosť: ak a je najväčším spoločným deliteľom (označovaný aj NSD(u,v) alebo GCD(u,v)) čísel u,v, potom je aj najväčším spoločným deliteľom čísel v,u-qv pre ľubovoľné q. Tvrdenie možno dokázať nasledujúcim spôsobom. Keďže je a najväčší spoločný deliteľ čísel u,v, musí platiť  a , kde a je najväčšie takéto číslo. Potom zrejme

čo znamená, že a je spoločným deliteľom čísel v,u-qv pre ľubovoľné q. Zostáva dokázať, že žiadny väčší spoločný deliteľ neexistuje. Sporom. Nech b > a je spoločný deliteľ v,u-qv. Potom platí v = kb a u-qv = lb. Z toho ale

čo znamená že b je spoločným deliteľom u,v, a keďže b > a, nemôže byť a najväčším spoločným deliteľom u,v, čo je spor s predpokladom.

Špeciálnym prípadom práve dokázaného tvrdenia je tvrdenie: ak a je najväčším spoločným deliteľom u,v, kde , potom je aj najväčším spoločným deliteľom čísel v a .

Euklidov algoritmus možno opísať nasledovne:

Vstup: prirodzené čísla u, v, .

Výstup: Najväčší spoločný deliteľ čísel u,v.

Procedúra:
 Ak v = 0, vráť na výstup hodnotu u, inak pokračuj krokom 2.
 Zavolaj procedúru Euklidovho algoritmu pre vstup .

Podľa dokázaného tvrdenia nevráti Euklidov algoritmus nikdy zlú hodnotu. Navyše, pri každom rekurzívnom volaní sa zmenší hodnota aspoň jedného vstupu, pričom obe zotrvávajú nezáporné. To znamená, že Euklidov algoritmus sa na každom vstupe zastaví, pričom jeho výstupom je naozaj najväčší spoločný deliteľ čísel u,v.

Pseudokód 

Pseudokód pre rekurzívnu implementáciu Euklidovho algoritmu môže byť nasledovný:

 function gcd(u, v)
     if v = 0
        return u
     else
        return gcd(v, u mod v).

Pre iteratívnu verziu možno napísať nasledujúci pseudokód

 function gcd(u, v)
     while v ≠ 0
        t := v
        v := u mod v
        u := t
     return u.

Externé odkazy 

 Euklidov algoritmus - Wolfram MathWorld .
 Euklidov algoritmus - cut-the-knot .
 Euklidov algoritmus

Pozri aj 

 Rozšírený Euklidov algoritmus

Teória čísel
Algoritmy