Najveći zajednički faktor (GCF)

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.