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ť $u=na$ a $v=ma$, kde a je najväčšie takéto číslo. Potom zrejme

$u-qv=na-qma=(n-mq)a,\,$

č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

$u=u-qv+qv=lb+qkb=(l+qk)b,\,$

č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 $u\geq v$, potom je aj najväčším spoločným deliteľom čísel v a $u{\text{ mod }}v$.

Euklidov algoritmus možno opísať nasledovne:

Vstup: prirodzené čísla u, v, $u\geq v$.

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

Procedúra:

1. Ak v = 0, vráť na výstup hodnotu u, inak pokračuj krokom 2.
2. Zavolaj procedúru Euklidovho algoritmu pre vstup $v,u{\text{ mod }}v$.

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 (po anglicky).
• Euklidov algoritmus - cut-the-knot (po anglicky).
• Euklidov algoritmus

Pozri aj

• Rozšírený Euklidov algoritmus