Najväčší spoločný deliteľ (GCF) je najväčšie číslo, ktorým možno rozdeliť dve alebo viac čísel. To bez zanechania zvyškov.
To znamená, že najväčší spoločný deliteľ alebo GCF je najvyššia hodnota, ktorou je možné množinu čísel vydeliť, výsledkom čoho je celé číslo.
Deliteľ sa dá formálne definovať ako to číslo, ktoré je obsiahnuté v inom presne n-krát.
Je potrebné poznamenať, že čísla, na ktorých sa počíta GCF, musia byť nenulové.
Aby sme to lepšie vysvetlili, pozrime sa na príklad. Predpokladajme, že máme 35 a 15. Teda sledujeme, aké sú delitele každého z nich:
- Delitelia 35 → 35,7,5,1
- Delitelia 15 → 15,5,3,1
Preto najväčší spoločný faktor 35 a 15 je 5.
Za zmienku stojí, že ak sú spoločným deliteľom dvoch čísel iba 1 a -1, hovorí sa im „prime to each other“.
Metódy výpočtu najväčšieho spoločného deliteľa
Na výpočet najväčšieho spoločného deliteľa môžeme rozlíšiť nasledujúce tri metódy:
- Prime factor rozklad: Čísla sa rozkladajú na prvočísla. Potom na výpočet GCF vezmeme bežné čísla zdvihnuté na najnižší výkon. Predpokladajme napríklad, že máme 216 a 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Preto by najväčší spoločný deliteľ medzi oboma číslami bol: (2 2) * 3 = 12
Teraz predpokladajme, že máme tri prvky: 315, 441 a 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Potom, keď ich rozdelíte a vezmeme každého deliteľa s najmenšou mocou, bude výsledok:
GCF = (3 2) * 7 = 63
- Euklidov algoritmus: Pri delení do Vstúpte b, získa sa kvocient c a a r. Takže najväčší spoločný deliteľ do Y. b je to isté ako b Y. r. Toto vzhľadom na toto: a = bc + r. Aby sme tomu lepšie porozumeli, použijeme túto metódu na príklad uvedený vyššie s 216 a 156.
216/156 = 1 so zvyškom 60
teraz rozdelíme 156/60 = 2 na zvyšok 36
Opäť rozdelíme 60/36 = 1 so zvyškom 24
Opäť rozdelíme 36/24 = 1 na zvyšok 12
A nakoniec rozdelíme 24/12 = 2 na zvyšok 0
Preto je najväčší spoločný deliteľ 12. Ako vidíme, musíme deliť, kým zvyšok nebude 0 a posledným deliteľom bude GCF.
- Na základe najmenšieho spoločného násobku: Čísla sa vynásobia a výsledok sa vydelí ich najmenej spoločným násobkom (LCM).
Musíme si uvedomiť, že najmenší spoločný násobok (LCM) je najmenší údaj, ktorý spĺňa podmienku bytia násobkom všetkých prvkov množiny čísel.
To znamená, že sa vrátime k rovnakému príkladu, môžeme to rozložiť nasledovne:
216 = (3 3) * (2 3) a 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Najmenší spoločný násobok by bol: (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Takže: GCD = 216 * 156 / 2,808 = 12
Stojí za zmienku, že táto metóda funguje iba pre dve čísla.