Највећи заједнички делитељ (ГЦФ) је највећи број којим се могу поделити два или више бројева. Ово, без остављања остатака.
Односно, највећи заједнички делилац или ГЦФ је највиша цифра којом се скуп бројева може поделити, што резултира целим бројем.
Делитељ се може формално дефинисати као онај број који је садржан у другом тачно износу н пута.
Треба напоменути да бројеви на којима се израчунава ГЦФ морају бити различити од нуле.
Да бисмо то боље објаснили, погледајмо пример. Претпоставимо да имамо 35 и 15. Дакле, посматрамо шта су дељеници сваког од њих:
- Делиоци од 35 → 35,7,5,1
- Делиоци 15 → 15,5,3,1
Према томе, највећи заједнички фактор од 35 и 15 је 5.
Вреди напоменути да ако су заједнички делитељи два броја само 1 и -1, они се називају „међусобно прости“.
Методе за израчунавање највећег заједничког делитеља
Можемо разликовати следеће три методе за израчунавање највећег заједничког делитеља:
- Декомпозиција основног фактора: Бројеви се растављају на просте бројеве. Затим, за израчунавање ГЦФ, узимамо заједничке бројеве подигнуте на најнижу снагу. На пример, претпоставимо да имамо 216 и 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)
Према томе, највећи заједнички делилац између оба броја био би: (2 2) * 3 = 12
Сада претпоставимо да имамо три елемента: 315, 441 и 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Тада би, након њиховог раздвајања, узимајући сваки делилац са најмањом снагом, резултат био:
ГЦФ = (3 2) * 7 = 63
- Еуклидов алгоритам: При дељењу до Уђите б, добија се количник ц и а р. Дакле, највећи заједнички делилац до И. б исто је као б И. р. Ово, с обзиром на следеће: а = бц + р. Да бисмо га боље разумели, применимо ову методу на примеру приказаном претходно са 216 и 156.
216/156 = 1 са остатком од 60
сада делимо 156/60 = 2 са остатком 36
Поново делимо 60/36 = 1 са остатком 24
Још једном делимо 36/24 = 1 са остатком 12
И на крају делимо 24/12 = 2 са остатком 0
Према томе, највећи заједнички делилац је 12. Као што видимо, морамо делити док остатак није 0 и последњи делилац ће бити ГЦФ.
- На основу најмање заједничког вишеструког: Бројеви се множе и резултат се дели њиховим најмањим заједничким вишекратником (ЛЦМ).
Морамо запамтити да је најмањи заједнички вишекратник (ЛЦМ) најмања фигура која задовољава услов да је вишеструка вредност свих елемената скупа бројева.
Односно, враћајући се на исти пример, можемо се разложити на следећи начин:
216 = (3 3) * (2 3) и 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Најмањи заједнички вишекратник био би: (3 3) * (2 3) * 13 * 17 * 7 = 334.152
Дакле: ГЦД = 216 * 156 / 2.808 = 12
Вреди напоменути да овај метод делује само за два броја.