Najveći zajednički djelitelj (GCF) je najveći broj kojim se dva ili više brojeva mogu podijeliti. Ovo, bez ostavljanja tragova.
To jest, najveći zajednički djelitelj ili GCF je najveća cifra kojom se skup brojeva može podijeliti, što rezultira cijelim brojem.
Delitelj se formalno može definisati kao onaj broj koji je sadržan u drugom tačno iznosu n puta.
Treba napomenuti da brojevi na kojima se izračunava GCF moraju biti različiti od nule.
Da bismo to bolje objasnili, pogledajmo primjer. Pretpostavimo da imamo 35 i 15. Dakle, posmatramo koji su delioci svakog od njih:
- Delitelji od 35 → 35,7,5,1
- Delitelji od 15 → 15,5,3,1
Stoga je najveći zajednički faktor 35 i 15 5.
Vrijedi spomenuti da ako su zajednički djelitelji dva broja samo 1 i -1, oni se nazivaju "prosti jedan prema drugom".
Metode za izračunavanje najvećeg zajedničkog djelitelja
Možemo razlikovati sljedeće tri metode za izračunavanje najvećeg zajedničkog djelitelja:
- Dekompozicija na proste faktore: brojevi se rastavljaju na proste brojeve. Zatim, da bismo izračunali GCF, uzimamo uobičajene brojeve podignute na najmanji stepen. 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 djelitelj 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
Zatim, nakon što ih razdvojimo, uzimajući svaki djelitelj s najnižom potencijom, rezultat bi bio:
GCF = (3 ^ 2) * 7 = 63
- Euklidov algoritam : Deljenjem a sa b dobijamo količnik c i r . Dakle, najveći zajednički djelitelj a i b je isti kao onaj za b i r . Ovo, s obzirom na sljedeće: a = bc + r . Da bismo to bolje razumjeli, primijenimo ovu metodu na prethodno prikazani primjer sa 216 i 156.
216/156 = 1 sa ostatkom od 60
sada dijelimo 156/60 = 2 sa ostatkom 36
Ponovo dijelimo 60/36 = 1 sa ostatkom 24
Još jednom dijelimo 36/24 = 1 sa ostatkom 12
I na kraju dijelimo 24/12 = 2 sa ostatkom 0
Dakle, najveći zajednički djelitelj je 12. Kao što vidimo, moramo dijeliti dok ostatak ne bude 0, a posljednji djelitelj će biti GCF.
- Na osnovu najmanjeg zajedničkog višekratnika : brojevi se množe, a rezultat se dijeli njihovim najmanjim zajedničkim višekratnikom (LCM).
Moramo zapamtiti da je najmanji zajednički umnožak (LCM) najmanja figura koja zadovoljava uslov da je višekratnik svih elemenata skupa brojeva.
Odnosno, vraćajući se na isti primjer, možemo 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 bi bio: (3 ^ 3) * (2 ^ 3) * 13 * 17 * 7 = 334,152
Dakle: GCD = 216 * 156 / 2,808 = 12
Vrijedi napomenuti da ova metoda radi samo za dva broja.
maksimum (matematika)