Portál:Matematika/Odporúčaný článok/47 2011

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$.

Celý článok...