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

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

Vlastnosti

• Určenie najväčšieho spoločného deliteľa je matematická operácia, ktorá je
  • idempotentná,

  $\mathrm{NSD}(a,a)=a$

  • asociatívna

  $\mathrm{NSD}(\mathrm{NSD}(a,b),c)=\mathrm{NSD}(a,(\mathrm{NSD}(b,c))$

  • a komutatívna.

  $\mathrm{NSD}(a,b)=\mathrm{NSD}(b,a)$

• 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:

  $\mathrm{NSD}(a,b)\mathrm{nsn}(a,b)=ab$

• $\mathrm{NSD}(a,b)=\mathrm{NSD}(a,b-a)$ (pre $b>a$). Túto vlastnosť využíva Euklidov algoritmus:

  Označme $D_1$ množinu spoločných deliteľov čísel $a,b$ a $D_2$ množinu spoločných deliteľov čísel $a,b-a$. Uvedomíme si, že

  $d\mid a\wedge d\mid (b-a)\Rightarrow d\mid a\wedge d\mid b\Rightarrow \mathrm{NSD}(a,b-a)\in D_1$

  $d\mid a\wedge d\mid b\Rightarrow d\mid a\wedge d\mid (b-a)\Rightarrow \mathrm{NSD}(a,b)\in D_2$

  Ak by $\mathrm{NSD}(a,b)>\mathrm{NSD}(a,b-a)$, dostali by sme spor, pretože v množine $D_2$ by bol väčší prvok ako $\mathrm{NSD}(a,b-a)$. Podobný spor by sme dostali, ak by $\mathrm{NSD}(a,b)<\mathrm{NSD}(a,b-a)$. Preto $\mathrm{NSD}(a,b)=\mathrm{NSD}(a,b-a)$.

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

$\mathrm{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

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

Externé odkazy

• Najväčší spoločný deliteľ