Najväčší spoločný deliteľ

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

\operatorname{NSD}(a, b) = \max \{ n \in \mathbb{N} : n \mid a \wedge n \mid b \}

Vlastnosti[upraviť | upraviť zdroj]

Výpočet[upraviť | upraviť zdroj]

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 \prod_i p_i^{e_i} je prvočíselný rozklad čísla a a \prod_i p_i^{f_i} prvočíselný rozklad čísla b. Potom

\operatorname{NSD}(a, b) = \prod_i p_i^{\min {(e_i, f_i)}}.

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.

Pozri aj[upraviť | upraviť zdroj]

Zdroj[upraviť | upraviť zdroj]

Tento článok je čiastočný alebo úplný preklad článku Největší společný dělitel na českej Wikipédii.