A legnagyobb közös osztó (GCF) az a legnagyobb szám, amellyel két vagy több szám felosztható. Ez anélkül, hogy maradék maradna.
Vagyis a legnagyobb közös osztó vagy a GCF az a legmagasabb szám, amellyel egy számkészletet fel lehet osztani, ami egész számot eredményez.
Az osztó formálisan meghatározható az a szám, amely egy másikban n-szer pontosan annyit tartalmaz.
Meg kell jegyezni, hogy azoknak a számoknak, amelyekre a GCF-et kiszámítják, nem nullának kell lenniük.
Hogy jobban megmagyarázzuk, nézzünk meg egy példát. Tegyük fel, hogy 35 és 15 van. Tehát megfigyeljük, hogy melyek az egyes osztók:
- Osztók 35-ből → 35,7,5,1
- 15-ös osztó → 15,5,3,1
Ezért a 35 és 15 legnagyobb közös tényező 5.
Érdemes megemlíteni, hogy ha két szám közös osztója csak 1 és -1, akkor "egymásnak prímnek" nevezzük őket.
Módszerek a legnagyobb közös osztó kiszámításához
A következő három módszert különböztethetjük meg a legnagyobb közös osztó kiszámításához:
- Az elsődleges tényező bomlása: A számokat prímszámokra bontjuk. Ezután a GCF kiszámításához a legkisebb teljesítményre emeljük a közös számokat. Tegyük fel például, hogy 216 és 156 van:
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)
Ezért a legnagyobb közös osztó mindkét szám között a következő lenne: (2 2) * 3 = 12
Tegyük fel, hogy három elemünk van: 315, 441 és 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Ezután, miután lebontottuk őket, és minden egyes osztót a legkisebb erővel vettünk fel, az eredmény a következő lett:
GCF = (3 2) * 7 = 63
- Euklidész algoritmusa: Osztáskor nak nek Bejön b, hányadost kapunk c és a r. Tehát, a legnagyobb közös osztója nak nek Y b ugyanaz mint b Y r. Ezt figyelembe véve a következőket: a = bc + r. Hogy jobban megértsük, alkalmazzuk ezt a módszert a korábban a 216-os és a 156-os példánál bemutatott példára.
216/156 = 1 maradék 60-mal
most 156/60 = 2-t osztunk a maradék 36-mal
Ismét felosztunk 60/36 = 1 maradék 24-gyel
Még egyszer elosztjuk a 36/24 = 1 értéket a maradék 12-vel
És végül 24/12 = 2-t osztunk 0 maradékkal
Ezért a legnagyobb közös osztó a 12. Amint láthatjuk, addig kell osztanunk, amíg a maradék 0, és az utolsó osztó a GCF lesz.
- A legkevésbé gyakori többszörös alapján: A számokat megszorozzuk, és az eredményt elosztjuk a legkevésbé közös többszörösükkel (LCM).
Emlékeznünk kell arra, hogy a legkevésbé gyakori többszörös (LCM) a legkisebb szám, amely teljesíti azt a feltételt, hogy a számkészlet összes elemének többszöröse legyen.
Vagyis ugyanarra a példára visszatérve a következőképpen bomolhatunk:
216 = (3 3) * (2 3) és 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
A legkevesebb közös többszörös a következő lenne: (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Tehát: GCD = 216 * 156 / 2,808 = 12
Érdemes megemlíteni, hogy ez a módszer csak két szám esetén működik.
