Mit jelent a legnagyobb közös osztó? Íme a válasz!
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ű.
A legnagyobb közös osztó kiszámolása
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.
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.
Forrás legnagyobb közös osztó
