Najväčší spoločný deliteľ

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

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

Algoritmus hľadania NSD

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 = 2²x 5² , 36 = 2x2x3x3 = 2²x3²
Aspoň raz sa vyskytuje len 2, a to 2-krát. Preto NSD (100,36) = 4

Pozri aj

• Najmenší spoločný násobok