Najveći zajednički djelitelj (GCF) najveći je broj kojim se mogu podijeliti dva ili više brojeva. Ovo, bez ostavljanja ostataka.
Odnosno, najveći zajednički djelitelj ili GCF najviša je brojka kojom se skup brojeva može podijeliti, što rezultira cijelim brojem.
Dijelitelj se može formalno definirati kao onaj broj koji je sadržan u drugom točno iznosu n puta.
Treba imati na umu da brojevi na kojima se izračunava GCF moraju biti nula.
Da bismo to bolje objasnili, pogledajmo primjer. Pretpostavimo da imamo 35 i 15. Dakle, promatramo koji su djelitelji svakog od njih:
- Dijelitelji 35 → 35,7,5,1
- Djelitelji 15 → 15,5,3,1
Stoga je najveći zajednički faktor 35 i 15 5.
Vrijedno je spomenuti da ako su zajednički djelitelji dvaju brojeva samo 1 i -1, oni se nazivaju "međusobno prosti".
Metode za izračunavanje najvećeg zajedničkog djelitelja
Možemo razlikovati sljedeće tri metode za izračunavanje najvećeg zajedničkog djelitelja:
- Razgradnja osnovnog faktora: Brojevi se rastavljaju na proste brojeve. Zatim, za izračun GCF-a, uzimamo zajedničke brojeve podignute na najmanju snagu. Na primjer, pretpostavimo da imamo 216 i 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)
Stoga bi najveći zajednički djelilac između oba broja bio: (2 2) * 3 = 12
Pretpostavimo sada da imamo tri elementa: 315, 441 i 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Tada bi, nakon njihovog razdvajanja, uzimajući svaki djelitelj s najmanjom snagom, rezultat bio:
GCF = (3 2) * 7 = 63
- Euklidov algoritam: Pri dijeljenju do Ući b, dobiva se količnik c i a r. Dakle, najveći zajednički djelitelj do Y b je isto što i b Y r. To, s obzirom na sljedeće: a = bc + r. Da bismo ga bolje razumjeli, primijenimo ovu metodu na prethodno prikazanom primjeru s 216 i 156.
216/156 = 1 s ostatkom od 60
sada dijelimo 156/60 = 2 s ostatkom 36
Podijelimo ponovno 60/36 = 1 s ostatkom 24
Još jednom dijelimo 36/24 = 1 s ostatkom 12
I na kraju dijelimo 24/12 = 2 s ostatkom 0
Stoga je najveći zajednički djelitelj 12. Kao što vidimo, moramo dijeliti dok ostatak ne postane 0, a posljednji djelitelj će biti GCF.
- Na temelju najmanje zajedničkog višestrukog: Brojevi se množe, a rezultat dijeli s najmanjim zajedničkim višekratnikom (LCM).
Moramo se sjetiti da je najmanji zajednički višekratnik (LCM) najmanji lik koji zadovoljava uvjet da je višestruk svih elemenata skupa brojeva.
Odnosno, vraćajući se na isti primjer, možemo se razložiti na sljedeći način:
216 = (3 3) * (2 3) i 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Najmanji zajednički višekratnik bio bi: (3 3) * (2 3) * 13 * 17 * 7 = 334.152
Dakle: GCD = 216 * 156 / 2,808 = 12
Vrijedno je spomenuti da ova metoda djeluje samo za dva broja.