5. Najväčší spoločný deliteľ

5.1. 1. Metóda - využitie množín deliteľov

Metóda 1: Využitie množiny deliteľov

Zadanie: Nájdite najväčšieho spoločného deliteľa čísel  75 a 252 .

Majme čísla  75 a 252 a priraďme im množiny D(75), D(252) všetkých ich deliteľov. Zapíšeme tieto množiny vymenovaním prvkov aj ich prienikmi a znázorníme ich (obrázok).
D(75)={1,3,5,15,25,75}
D(252)={1,2,3,4,6,7,9,12,14,18,21,28,36,42,63,84,126,252}
D(75)∩D(252)={1,3}

Pretože spoločné delitele čísel sú spoločné prvky množín ich deliteľov, najväčší spoločný deliteľ je najväčší prvok prieniku množín deliteľov. To platí pre dve i väčší počet čísel.
NSD(75,252)=3
Metóda využitie množiny deliteľov sa opiera o definíciu najväčšieho spoločného deliteľa. Táto metóda je však zdĺhavá a prácna. Hodí sa len pre malé prirodzené čísla.

\( .\)