Najväčší spoločný deliteľ

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

Najväčší spoločný deliteľ dvoch prirodzených čísel m a n je najväčšie nenulové prirodzené číslo, ktoré je deliteľom oboch čísel m a n.

Definícia[upraviť | upraviť zdroj]

NSD(a, b) = max { n ∈ N: n | a a zároveň n | b }


Algoritmus hľadania NSD[upraviť | upraviť zdroj]

Najväčší spoločný deliteľ dvoch alebo viacerých čísel získame podobne ako najmenší spoločný násobok a to tak, že z prvočíselných rozkladov čísel vyberieme tie prvočísla, ktoré sa vyskytujú v každom rozklade aspoň raz, a to s najnižšou mocninou každého z prvočísel, ktorá sa v rozkladoch vyskytuje. Tieto mocniny prvočísel medzi sebou vynásobíme.

Napríklad 10 a 15:
10 = 2x5 , 15 = 3x5
Vidíme, že sa v týchto číslach opakuje len 5 (v oboch číslach len raz). Preto NSD(10,15) = 5

Napríklad 100 a 36:
100= 2x2x5x5 = 22x 52 , 36 = 2x2x3x3 = 22x32
Aspoň raz sa vyskytuje len 2, a to 2-krát. Preto NSD (100,36) = 4

Pozri aj[upraviť | upraviť zdroj]