Legnagyobb közös osztó
A legnagyobb közös osztó a matematikában véges sok szám olyan közös osztója (azaz olyan szám, amely a véges sok szám mindegyikét osztja), amely bármely más közös osztónál nagyobb.
Két (nem egyszerre nulla) egész szám közös osztói közül a lehetséges legnagyobb nem nulla pozitív egész, amely mindkét egész számot (maradék nélkül) osztja.
A definíció másképp is megfogalmazható: két szám legnagyobb közös osztója a két szám ama közös osztója, amely minden közös osztónak többszöröse. Ez a definíció előjeltől eltekintve egyértelmű.
Az a,b számok ln. k. o.-jának szokásos jelölése a magyar szakirodalomban (a, b) vagy lnko(a, b); az angol irodalomban gcd(a, b).[1]
Például: lnko(12, 18) = 6, lnko(10, 5) = 5, lnko(-21, 9) = 3.
További fogalmak
szerkesztésKét szám relatív prím, ha a legnagyobb közös osztójuk az 1. Ha véges sok a1, a2, … an elemre, (ai, aj) = 1, (i ≠ j), akkor ezek az elemek páronként relatív prímek. A legnagyobb közös osztó megkeresése hasznos lehet törteknél egyszerűsítéskor.
Például lnko(48, 80) = 16, így:
Véges sok elem legnagyobb közös osztóját így értelmezzük: (a1, a2, … an) = ((a1, a2, … an-1), an) (n≥2)
Kapcsolata a legkisebb közös többszörössel
szerkesztésKét szám legnagyobb közös osztójának (lnko) és legkisebb közös többszörösének (lkkt) szorzata előjeltől eltekintve egyenlő a két szám szorzatával:
Például:
Ez az állítás könnyen belátható törzstényezőkre bontással és a prímtényezők összegyűjtésével.
A legnagyobb közös osztó kiszámolása
szerkesztésA legnagyobb közös osztó megkereséséhez meg kell határozni az adott két szám prímtényezőit, azaz a számokat fel kell bontani prímszámok szorzatára. Egy másik példa alapján az lnko(120, 560) kiszámolásánál felírandó, hogy 120 = 5·3·23 és 560 = 7·5·24. Ekkor venni kell a közös prímtényezőket, (mint ahogy a nevében is van), mégpedig a két kanonikus felbontásban szereplő hatvány közül a kisebbiken, és az így kapott prímhatványok szorzata lesz az ln. k. o. Itt most 5·23 = 40, így lnko(120, 560) = 40. Ez a számolási módszer csak a relatíve kis egészeknél működik (egy szám prímosztóit számológép, táblázat vagy specifikus prímtesztek ismerete, segítsége nélkül ugyanis számításigényes feladat megtalálni), általánosságban a legnagyobb közös osztó megkeresése nagy számoknál ilyen módszerrel sok időt vesz igénybe.
Ennél egy sokkal hatásosabb módszer, az euklideszi algoritmus, ami a hétköznapi maradékos osztás algoritmusát használja fel.
Legegyszerűbben két szám legnagyobb közös osztóját úgy kapjuk meg, ha kivonjuk a kettő szám közül a nagyobbikból a kisebbet, mert a különbségnek is azonos az összes közös osztója. Így viszont csökkenő sorozatot kapunk, ami a két szám egyenlőségéhez, vagyis a legnagyobb közös osztóhoz tarthat csak. Ezt az ismételt összeadást nyilván egy maradékos osztással is elvégezhetjük, ekkor a sok kivonást elkerülendő a nagyobb számot osztjuk a kisebbel s helyére az osztás maradékát tesszük.
Elegánsabban fogalmazva a módszer a következő: elosztjuk a-t b-vel (a nagyobb számot a kisebbel - ha a két szám egyenlő, akkor ln. k. o.-juk a=b), majd az osztási maradékkal b-t, és így tovább, akkor az utolsó nem nulla maradék maga az lnko lesz.[2]
Példa:
lnko(84, 18) = ?
- Ekkor elosztjuk 84-et 18-cal
- a hányados 4, a maradék 12
- elosztjuk 18-at 12-vel
- a hányados 1, a maradék 6
- elosztjuk 12-t 6-tal
- a hányados 2, a maradék 0,
azaz itt megállt az algoritmus, nincs következő lépés, mivel 0-val nem lehet osztani. Tehát az utolsó nem nulla maradék a 6,
azaz lnko(84, 18) = 6.
Ha a és b közül egyik se nulla, akkor felhasználva a legkisebb közös többszörösüket, ami jelölésben az lkkt(a, b):
Tulajdonságai
szerkesztés- Az a és b számok bármely közös osztója osztója az lnko(a, b)-nek is.
- lnko(a, b) = lnko(b, a)
- lnko(a, a) = a
- c·lnko(a, b) = lnko(c·a, c·b) (tetszőleges c számra)
- lnko(a, b) = lnko(a+bc, b)
- lnko(a, b) = a, akkor és csak akkor, ha a|b, azaz a osztója b-nek
- ha lnko(a, b) = 1 és lnko(a, c) = 1, akkor lnko(a, b·c) = 1
- ha a|b·c és lnko(a, b) = 1, akkor a|c
Absztrakt algebra
szerkesztésGyűrűk
szerkesztésAz egész számok gyűrűjében egy adott a számmal osztható számok ideált alkotnak, mivel két ilyen összege szintén osztható a-val, és egy ilyen számot egész számmal szorozva szintén a-val osztható számot kapunk. Több számra is vehető az adott számokat tartalmazó legkisebb ideál, így tekinthető az a, b egész számok által generált ideál. Az euklideszi algoritmussal kiszámítható, hogy ez az ideál egyetlen számmal is generálható, és ez a szám az adott a és b számok legnagyobb közös osztója.
Ez az eljárás általánosabban is alkalmazható gyűrűkben, azonban nem minden gyűrűben lesz a két vagy több elemmel generált ideál egy elemmel generálható, csak az ún. főideálgyűrűkben. Ezek az ideálok a két vagy több elem legnagyobb közös osztójának általánosításai lesznek.
Hálók
szerkesztésAz egész számok részben rendezhetők az oszthatóságra. Ebben a rendezésben az a egész szám nagyobb lesz a b egész számnál, ha a osztható b-vel. Ez a rendezett halmaz hálóvá válik a legnagyobb közös osztó, mint metszet, és a legkisebb közös többszörös, mint egyesítés műveletére.
Hivatkozások
szerkesztésLásd még
szerkesztésJegyzetek
szerkesztés- ↑ Greatest common divisor.
- ↑ Ez lényegében a szorzás kivonásra való disztributivitásának a következménye: ha q osztója a-nak és b-nek, azaz közös osztó (a=pq és b=p'q), akkor a disztributivitás miatt a különbségüknek is ( a-b=pq-p'q=q(p-p') ); így ha képezzük az a-b, a-2b, a-3b, ... a-nb különbségeket, ahol n a legnagyobb szám, ahányszor még ki lehet vonni a-ból b-t (ekkor a-nb épp az osztási maradék), mindnek osztója lesz az a és b minden közös osztója. Ha a maradék 0, akkor készen vagyunk, hiszen ekkor b osztója volt a-nak és így (a,b)=b. Ellenkező esetben ismételjük meg az eljárást b-vel és a maradékkal, mígnem nulla maradékot kapunk (a maradékok pozitívak és egyre csökkennek, így előbb utóbb 0-t kell kapnunk). Az utolsó nem nulla maradék biztosan osztója lesz az előző maradéknak (hiszen maradék nélkül, vagyis nulla maradékkal van meg benne, mivelhogy az utolsó maradék nulla), s könnyen belátható (lényegében teljes indukcióval), hogy ekkor minden más, a fenti eljárásban szereplő maradéknak is. Vagyis az utolsó nem nulla maradék - legyen d - egy közös osztó. Legyen x tetszőleges közös osztója a-nak és b-nek. Ekkor a fent mondott disztributivitási elv miatt minden fenti osztási maradéknak is osztója (hiszen ezek előállnak x v.mely többszörösei különbségeiként), vagyis osztója az utolsó nem nulla maradéknak is. Tehát ha x közös osztó, akkor osztja d-t (d kitüntetett közös osztója a- és b-nek), vagyis d nagyobb vagy egyenlő nála, s így d a legnagyobb közös osztó.
Források
szerkesztés- Kleine Enzyklopädie Mathematik. Leipzig: VEB Verlag Enzyklopädie. 1970. 28. oldal.
- Matematikai kisenciklopédia. Szerk. Lukács Ernőné és Tarján Rezsőné. Budapest: Gondolat. 1968. 144-147. oldal.
- Freud Róbert – Gyarmati Edit: Számelmélet. Egyetemi jegyzet.