Največji skupni delitelj (GCF) je največje število, s katerim lahko delimo dve ali več števil. To brez ostankov.
To pomeni, da je največji skupni delilec ali GCF najvišja številka, s katero je mogoče deliti množico števil, kar ima za posledico celo število.
Delitelj lahko formalno definiramo kot tisto število, ki je v drugem natančno znesek n-krat.
Upoštevati je treba, da številke, na katere se izračuna GCF, ne smejo biti enake ničli.
Za boljšo razlago si poglejmo primer. Recimo, da jih imamo 35 in 15. Tako opazujemo, kaj so delitelji vsakega:
- Delitelji 35 → 35,7,5,1
- Delitelji 15 → 15,5,3,1
Zato je največji skupni faktor 35 in 15 5.
Omeniti velja, da če so skupni delilniki dveh števil le 1 in -1, jih imenujemo "med seboj".
Metode za izračun največjega skupnega delitelja
Za izračun največjega skupnega delitelja lahko ločimo naslednje tri metode:
- Razgradnja glavnega faktorja: Števila so razstavljena na prosta števila. Nato za izračun GCF vzamemo skupna števila, povišana na najnižjo moč. Denimo, da imamo na primer 216 in 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)
Zato bi bil največji skupni delilec med obema številkama: (2 2) * 3 = 12
Zdaj predpostavimo, da imamo tri elemente: 315, 441 in 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Potem, ko jih razčlenimo in vzamemo vsak delitelj z najmanjšo močjo, bi bil rezultat:
GCF = (3 2) * 7 = 63
- Evklidov algoritem: Pri delitvi do Vstopi b, dobimo količnik c in a r. Torej, največji skupni delitelj do Y. b je enako kot b Y. r. To glede na naslednje: a = bc + r. Da bi ga bolje razumeli, uporabimo to metodo na primeru, ki je bil prej prikazan z 216 in 156.
216/156 = 1 s preostankom 60
zdaj delimo 156/60 = 2 s preostankom 36
Ponovno delimo 60/36 = 1 s preostankom 24
Še enkrat delimo 36/24 = 1 s preostankom 12
In na koncu delimo 24/12 = 2 s preostankom 0
Zato je največji skupni delilec 12. Kot vidimo, moramo deliti, dokler ostanek ni 0 in bo zadnji delilec GCF.
- Na podlagi najmanj pogostega večkratnika: Števila se pomnožijo in rezultat se deli z najmanjšim skupnim večkratnikom (LCM).
Ne smemo pozabiti, da je najmanj skupni večkratnik (LCM) najmanjša številka, ki izpolnjuje pogoj, da je večkratnik vseh elementov nabora števil.
Se pravi, če se vrnemo k istemu primeru, lahko razgradimo na naslednji način:
216 = (3 3) * (2 3) in 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Najmanj pogost večkratnik bi bil: (3 3) * (2 3) * 13 * 17 * 7 = 334.152
Torej: GCD = 216 * 156 / 2.808 = 12
Omeniti velja, da ta metoda deluje le za dve številki.