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.

Két szám relatív prím, ha a legnagyobb közös osztójuk az 1. Ha véges sok a₁, a₂, … a_n elemre, (a_i, a_j) = 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:

${\displaystyle {48 \over 80}={3\cdot 16 \over 5\cdot 16}={3 \over 5}.}$

Véges sok elem legnagyobb közös osztóját így értelmezzük: (a₁, a₂, … a_n) = ((a₁, a₂, … a_n-1), a_n) (n≥2)

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:

${\displaystyle \operatorname {lnko} (a,b)\cdot \operatorname {lkkt} (a,b)=|a\cdot b|}$

Például:

${\displaystyle {\begin{aligned}\operatorname {lnko} (21,6)\cdot \operatorname {lkkt} (21,6)=|21\cdot 6|\\42\cdot 3=|21\cdot 6|\\126=126~~~~~\\\end{aligned}}}$

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ó 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·2³ és 560 = 7·5·2⁴. 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·2³ = 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):

${\displaystyle \operatorname {lnko} (a,b)={\frac {|a\cdot b|}{\operatorname {lkkt} (a,b)}}.}$

• 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

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.

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.

• kitüntetett közös osztó
• Legkisebb közös többszörö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ó.

• 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.

• Alice és Bob - 17. rész: Alice és Bob ókori haverja
• Alice és Bob - 19. rész: Alice és Bob ideáljai
• Alice és Bob - 21. rész: Alice és Bob titkosít