Legnagyobb közös osztó

a legnagyobb olyan egész szám, amely két vagy több egész szám mindegyikének osztója

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 (ab) vagy lnko(ab); az angol irodalomban gcd(ab).[1]

Például: lnko(12, 18) = 6, lnko(10, 5) = 5, lnko(-21, 9) = 3.

További fogalmak szerkesztés

Ké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és

Ké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és

A 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és

Gyűrűk szerkesztés

Az 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és

Az 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és

Lásd még szerkesztés

Jegyzetek szerkesztés

  1. Greatest common divisor.
  2. 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.

További információk szerkesztés