Najväčší spoločný deliteľ

Najväčší spoločný deliteľ (značený NSD, D, príp. GCD z anglického greatest common divisor) dvoch celých čísel je najväčšie číslo také, že bezo zvyšku delí obe čísla, tzn. najväčšie číslo, ktorým sú obe čísla deliteľné. Napríklad najväčší spoločný deliteľ čísel 15 a 20 je 5 (číslo 5 delí obe čísla, žiadne väčšie číslo s touto vlastnosťou už neexistuje; napr. číslo 10 delí druhé číslo, ale nie prvé).

Všeobecnejšie je možné hovoriť o najväčšom spoločnom deliteli celej množiny čísel - tým je najväčšie číslo také, že bezo zvyšku delí všetky čísla v množine.

Definícia

Vlastnosti 
 Určenie najväčšieho spoločného deliteľa je matematická operácia, ktorá je
idempotentná, 
 
asociatívna 
 
a komutatívna.
 
 Súčin najväčšieho spoločného deliteľa a najmenšieho spoločného násobku dvoch čísel sa rovná súčinu týchto dvoch čísel:
 
  (pre ). Túto vlastnosť využíva Euklidov algoritmus:
 Označme  množinu spoločných deliteľov čísel  a  množinu spoločných deliteľov čísel . Uvedomíme si, že

Ak by , dostali by sme spor, pretože v množine  by bol väčší prvok ako . Podobný spor by sme dostali, ak by . Preto .

Výpočet 
Najväčšieho spoločného deliteľa dvoch čísel (a vďaka asociatívnosti i ľubovoľne mnohých) možno určiť prostredníctvom prvočíselného rozkladu oboch čísel, ako súčin prvočísel umocnený na najmenší z exponentov pri príslušnom prvočísle v rozkladoch:

Nech  je prvočíselný rozklad čísla  a  prvočíselný rozklad čísla .
Potom
.

Napríklad najväčšieho spoločného deliteľa čísel 136 a 204 možno nájsť tak, že zistíme, že 136=2³ × 17 a 204= 2² × 3 × 17. V rozkladoch sa vyskytujú prvočísla 2, 3 a 17 s exponentmi 3, 0, 1 pri menšom čísle a 2, 1, 1 pri väčšom čísle. Výsledný NSD je potom súčinom prvočísel vyskytujúcich sa v oboch rozkladoch umocnených na príslušné najmenšie exponenty, teda 2² × 17=68.

Tento výpočet je ľahko pochopiteľný, ale v praxi úplne nepoužiteľný s výnimkou veľmi malých čísel, pretože získanie rozkladu na prvočísla je extrémne náročná operácia.

Pre praktické výpočty slúžia výrazne rýchlejšie algoritmy, hlavne tzv. Euklidov algoritmus.

Referencie

Pozri aj 
 Najmenší spoločný násobok
 Nesúdeliteľné čísla
 Euklidov algoritmus

Externé odkazy 
 Najväčší spoločný deliteľ

Zdroj 

Teória čísel