Najveći zajednički djelitelj (GCF)

Najveći zajednički djelitelj (GCF)

Najveći zajednički djelitelj

Najveći zajednički djelitelj (GCF) je najveći broj kojim se mogu podijeliti dva ili više brojeva. Ovo, bez ostavljanja tragova.

To jest, najveći zajednički djelitelj ili GCF je najveća brojka kojom se skup brojeva može podijeliti, što rezultira cijelim brojem.

Djelitelj se formalno može definirati kao onaj broj koji je u drugom sadržan točno 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, promatramo koji su djelitelji svakog od njih:

  • Dijelci od 35 → 35,7,5,1
  • Djelitelji 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 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:

  • Razlaganje na proste faktore: brojevi se rastavljaju na proste brojeve. Zatim, za izračunavanje GCF-a, uzimamo uobičajene 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 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 : Dijeljenjem a s b dobivamo kvocijent 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 s 216 i 156.

216/156 = 1 s ostatkom od 60

sada dijelimo 156/60 = 2 s ostatkom 36

Ponovo podijelimo 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 bude 0, a posljednji djelitelj će biti GCF.

  • Na temelju najmanjeg zajedničkog višekratnika : brojevi se množe, a rezultat se dijeli s njihovim najmanjim zajedničkim višekratnikom (LCM).
Mcd 1

Moramo zapamtiti da je najmanji zajednički višekratnik (LCM) najmanji lik koji zadovoljava uvjet da je višekratnik svih elemenata skupa brojeva.

Odnosno, vraćajući se na isti primjer, možemo rastaviti 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 spomenuti da ova metoda radi samo za dva broja.

maksimalno (matematika)

  • Zakon velikih brojeva
  • Numerički skupovi
  • Zajednički troškovi