A matematikai tudományok időtlen emlékműve, a matematika, pontosabban a geometria atyjának számító görög matematikus, Eukleidész i.e. 300 körül megírt Elemek című matematikakönyve valószínűleg a legsikeresebb műveinek gyűjteménye.
A 13 könyvből (fejezetből) álló Elemek a síkbeli geometria (háromszögek, párhuzamos egyenesek, Pitagorasz-tétel igazolása, a kör tulajdonságai stb.), a térbeli geometria (testek, gömb stb.) és az aritmetika (prímszámok, oszthatóság, legnagyobb közös osztó, számok tulajdonságai stb.) lencséjén keresztül próbálta összegezni a matematika alapjait és elveit.
Bár maga Eukleidész közvetlenül nem járult hozzá a matematikát tanuló fiatalok körében ma is alapvető fontosságú maradékos osztás kifejlesztésében – a maradékos osztás módszere már jóval Eukleidész előtt is ismert volt –, ez a matematikai művelet Eukleidész geometriai és aritmetikai alapelvei alapján lehetővé tette az egész számok maradékos osztásának algoritmikus módszerének kialakítását. Ez az euklideszi algoritmus vagy euklideszi osztás, amellyel meghatározható két szám legnagyobb közös osztója (angol rövidítéssel: GCD, greatest common divisor).
Eukleidész i.e. 3–2. század között élt, a tudomány, filozófia és művészetek virágkorát élő és a Földközi-tenger medencéjében jelentős hatalmi és kulturális központnak számító ókori Görögország idején. Tudományos művei az egész korabeli ismert világban elterjedtek, és az őt követő civilizációk, többek közt az ókori Róma is átvette őket. A 15. század közepétől a nyomtatás elterjedésével az Elemek volt a Biblia után a második legszélesebb körben nyomtatott mű.
Eukleidész munkái a reneszánsztól kezdve napjainkig olyan tudósokat inspiráltak, mint Kopernikusz, Galilei, Kepler, Spinoza, Newton és B. Russel.
Az euklideszi algoritmus definíciója és alapelvei
Az Euklideszi algoritmussal ismételt maradékos osztásokon (és kivonásokon) alapulva meghatározható két egész szám legnagyobb közös osztója. Az ismételt maradékos osztásokat addig kell végezni, amíg el nem érünk egy olyan pontig, amikor a maradék 0 lesz. Ekkor a maradék 0-hoz tartozó osztó lesz a két eredeti szám legnagyobb közös osztója.
Az olyan témakörök, mint a legkisebb közös többszörös, a maradékos osztás és a legnagyobb közös osztó kiszámítása már az általános iskola alsó tagozatos tananyag megkerülhetetlen része, de tanulmányaid további részében is alapvető fontosságú marad, függetlenül attól, hogy emelt szintű matek érettségire készülsz-e vagy sem.
Amikor egy egész szám nem osztható egy másik egész számmal, akkor maradék képződik. Ezt nevezik maradékos osztásnak, amely lényegében két pozitív egész (természetes) szám közötti műveletre utal, pontosabban egy pozitív egész szám (ami nem 0) elosztására egy másik egész számmal, amelynek eredménye a hányados és a maradék.
Az euklideszi osztáskor tehát egy nem nulla természetes szám (≠ 0) elosztásáról van szó először pozitív egész számokkal, majd minden egész számmal, vagyis negatív egész számokkal is.
Mint már említettük, a maradékos osztással a diákok már az alsó tagozatos matekórák során megismerkednek, például olyan, a mindennapi életből vett példák segítségével, mint hogy hogyan osztható szét egy szelet torta öt embernek, hogyan osztható szét 47 üveggolyó négy ember között stb.
Az általános iskolás tanulmányok ezen szakaszában tehát kulcsfontosságú az aritmetikai (számtan) ismeretek, vagyis az alapműveletek (összeadás, kivonás, szorzás, osztás) és azok alapvető szabályainak (pl. páros és páratlan számok) fejből való megtanulása és tökéletes elsajátítása.
A maradékos osztás technikája lehetővé teszi, hogy számológép használata nélkül is meghatározhasd egy szám összes osztóját. Ehhez annyit kell tenned, hogy megnézed, hogy egy adott szám milyen gyakran fordul elő egy attól nagyobb számban, például hányszor van meg a 4 a 30-ban vagy a 7 a 75-ben.
Kis természetes számok esetében mindez még nem okoz különösen nagy kihívást, de ha fejben próbálod kiszámolni, hogy a 4357-ben hányszor van meg a 28, akkor el kell sajátítanod a maradékos osztás alapvető technikáját, különösen a későbbiekben a valós számok megjelenésével, amikor a tizedes számok és a törtek osztásáról tanulsz. Ha további fejtörést okoz, kérd egy matektanár segítségét.
Eljött az ideje, hogy konkrét példával is szemléltessük az euklideszi osztást, vagyis a maradék képződését abban az esetben, amikor két egész szám nem osztható: hogyan osztható el egyenlően 53 üveggolyó 5 ember közt?
Ha darabonként mindegyiküknek 1-1 üveggolyót adunk, akkor 47 üveggolyó marad. Ezt az eljárást addig kell ismételni, amíg nem tudunk többé mindenkinek egyenlően üveggolyót adni. Ekkor az utolsó elosztásnál észrevesszük, hogy mindenki 10 golyóval rendelkezik, és még 3 elosztatlan üveggolyó maradt, amit már csak úgy lehetne szétosztani, hogy 2 ember nem kap belőle.
Mivel minden ember 10 üveggolyóval rendelkezik, ezért a 10 az osztás hányadosa (q), a 3 pedig a maradék (r). Az egész számok a és b-vel való jelölésével (53 = a, 5 = b) a maradékos osztást a következőképp írhatjuk fel:
- a = q x b + r, vagyis 53 = 10 x 5 + 3, miután ellenőriztük, hogy 0 < r < b, vagyis 0 < 3 < 5.
Hogyan kell megoldani az euklideszi osztást?
Az euklideszi algoritmusban használt ismételt kivonás és osztás módszerével leegyszerűsíthető egy első látásra bonyolult műveletet.
Kétszámjegyű osztó
Vegyük például a következő műveletet: 273/17. Derítsd ki, hogy a 17-es szám hányszor van meg a 273-ban. Az eredmény megtalálása a következő módon történik:
- lépés: Először írjuk fel az osztást úgy, hogy egy oszlop bal oldalára az osztandó (273), a jobb oldalára pedig az osztó (17) kerül:
273 | 17 =
- lépés: Vegyük a 273 első számjegyét. Láthatjuk, hogy a 2 kisebb, mint 17, ezért az osztandó első két számjegyét kell néznünk, vagyis meg kell határoznunk, hogy hányszor van meg a 17 a 27-ben. A 27-ben egyszer van meg a 17; az 1-est az egyenlőségjel után írjuk. Ezután visszaszorzunk: 1 × 17 = 17. A 17-et a 27 alá írjuk, majd kivonjuk belőle, így marad 10:
273 | 17 = 1
--------------
-17
=10
- lépés: Ezt követően a maradék 10 után lehozzuk az osztandó következő számjegyét, vagyis a 3-at, így 103-at kapunk, amelyet megint 17-tel osztunk:
273 | 17 = 1
--------------
-17
=10
--------------
103
103-ban hatszor van meg a 17; a 6-ost az eredményhez írjuk, majd ismét visszaszorzunk és kivonunk:
273 | 17 = 16
--------------
-17
=10
--------------
103
-102
--------------
=1
Az eredmény tehát 273 : 17 = 16 × 17 + 1, amely az imént már említett módon a = q × b + r-ként is felírható. A 273 és 17 egész számú hányadosa tehát 16, a maradék pedig 1.
Az euklideszi osztás akkor és csak akkor jó, ha a maradék kisebb, mint az osztó (0 < r < b), ellenkező esetben azt jelenti, hogy még mindig lehet osztani.
Fontos megjegyezni, hogy ha a b-vel való osztása során a maradék nulla, például a 20/4 esetében, akkor azt mondjuk, hogy:
- a osztható b-vel
- a a b többszöröse
- b az a osztója
Mivel tehát 20/4 = 5, ezért mondhatjuk, hogy 20 osztható 4-gyel, továbbá mivel 4 × 5 = 20, ezért 20 a 4 többszöröse, és a 4 a 20 osztója.
Az agy effajta megtornáztatása valójában lehetővé teszik a lehetőségek körének kiszélesítését, ahelyett, hogy minden számmal végzett művelethez szorzásra és osztásra lenne szükség. Ezek az oszthatósági szabályok, amelyekkel tényleges osztás nélkül is meghatározhatjuk, hogy egy adott szám osztható-e egy másikkal, és amelyek a moduláris aritmetikában bármilyen valós szám esetén alkalmazhatók az egész számokra vonatkozó kongruencia relációnak köszönhetően.
Magán matektanártól ne habozz segítséget kérni, ha úgy érzed nem megy a számolás.
A felső tagozatos matekórák során találkozhatunk néhány olyan szabállyal, amelyek segítségével gyorsan kideríthető, hogy egy szám egy másik szám osztója-e.
Egy egész szám osztható:
- 2-vel, ha a szám utolsó számjegye 0 vagy páros szám (2, 4, 6, 8).
- 4-gyel, ha az utolsó két számjegy által alkotott kétjegyű szám is osztható 4-gyel.
- 5-tel, ha a szám utolsó számjegye 0 vagy 5.
- 3-mal, ha a szám számjegyeinek összege maga is osztható 3-mal.
- 9-cel, ha a szám számjegyeinek összege maga is osztható 9-cel.
- 10-zel, ha a szám utolsó számjegye 0.
Hogyan találjuk meg egy szám legnagyobb közös osztóját?
Két vagy több pozitív egész szám legnagyobb közös osztója az a szám, amelyikkel mindegyiket eloszthatjuk maradék nélkül, és bármely másik ilyen közös osztónál nagyobb. A legnagyobb közös osztó az aritmetika egyik alapelve, amely lehetővé teszi a két vagy több pozitív számot egyszerre osztó legnagyobb pozitív egész szám meghatározását. Jelöléséhez a számokat zárójelbe, egymástól pontosvesszővel elválasztva írjuk.
Ha például azt akarod megtudni, hogy mennyi a 20 és a 36 legnagyobb közös osztója, akkor készíts egy listát a 20 és a 36 minden osztópárjáról növekvő sorrendben, majd keresd ki a legnagyobb közös osztót:
- A 20 osztópárjai: 1, 2, 4, 5, 10, 20,
- A 36 osztópárjai: 1, 2, 3, 4, 6, 9, 12, 18, 36,
- vagyis (20; 36) = 4.
Több pozitív egész szám, például a 36, 48 és 60 esetében a közös osztók az 1, 2, 3, 4, 6 és 12, vagyis (36; 48; 60) = 12.
Mindez jól működik kisebb számok esetén, de nagyobb számokkal túl hosszadalmas folyamat lenne. Íme két másik módszer, nevezetesen az euklideszi algoritmus (ismételt kivonás és maradékos osztás) és a prímtényezős felbontás. Vegyük például 116 és a 78 legnagyobb közös osztójának megtalálását:
- Euklideszi algoritmus: Az euklideszi algoritmus esetében a lényeg az, hogy lépésről lépésre elosztjuk a nagyobb számot a kisebbel, majd az eredményt újra és újra a megkapott maradékkal helyettesítjük, más szóval az osztandó számot ismételten csökkentjük az osztóval való osztás eredményéből származó maradékkal ahányszor csak tudjuk, amíg el nem érjük a nullát. A nullát elérő maradék lesz a keresett legnagyobb közös osztó:
- 116 = 78 × 1 + 38, 78 = 38 × 2 + 2, 38 = 19 × 2 + 0, vagyis (116; 78) = 2.
- Prímtényezős felbontás: két szám legnagyobb közös osztóját a számokat prímtényezőkre (prímszámok szorzatára) bontásával és a számokban szereplő közös prímek összeszorzásával kapjuk meg:
- 116 = 2 × 2 × 29, 78 = 2 × 3 × 13, vagyis (116; 78) = 2.
A maradékos osztás különböző módszerei
A maradékos osztás megoldására más technikák is léteznek, ezeket nevezzük számítási algoritmusoknak, amelyek számos hasonlóan hatékony matematikai feladattal karöltve elősegítik az egész számok felbontását. A művelet elvégzésére lényegében olyan, az euklideszi osztás sajátosságain alapuló különböző technikákat alkalmazunk, amelyek megkönnyítik az egyenlet megoldását.
Ezek a technikák alatt az egész számokon végzett alapvető műveletek (kivonás, összeadás, összehasonlítás stb.) használatát értjük. Az euklideszi osztással kiszámolt hányadosból a maradék is természetesen levezethető. A hányados és a maradék lényegében a következő három módszerre számítható ki: a naiv módszerrel, a bináris módszerrel és a decimális módszerrel.
Matek korrepetálásra érdemes járni, ha gondokat okoznak a számok.
Naiv módszer
Az euklideszi osztást illetően a maga Eukleidész által leírt naiv módszer lényege, hogy addig végzünk ismétlő kivonásokat, amíg csak a művelet lehetséges. Bár számos különböző módszer létezik, ez a folyamatosan csökkenő számolási sorozat az, amelyik a legjobban bevált. Lényege az osztandó (a) ismételt csökkentése az osztóval (b) való osztás eredményéből származó maradékkal, amíg el nem érjük a nullát.
Bináris módszer
A bináris módszer az ókori Egyiptomban használt osztási technikából származó fogalom és módszer, amely a középkori Európában fejlődött ki. A módszer elve nagyon egyszerű, hiszen az egyiptomi szorzás fordított felépítésén alapszik. Tulajdonképpen csak annyit kell tennünk, hogy kitöltünk egy táblázatot, amely a 2 hatványait és azok b-vel való szorzatát mutatja.
Online matematika tanárok segítségét kérd, ha gyorstalpalóra van szükséged.
Az ötlet az, hogy megtaláljuk a legnagyobb többszöröst, pontosan azelőtt megállva, hogy átlépnénk az a értékét a második oszlopban. A megfelelő cellák hozzáadásával az 1. oszlophoz megkapjuk az osztás hányadosát. A megfelelő hányados megtalálásához a naiv módszerrel ellentétben itt nem kell végigjárni 0-tól minden egész számot, hanem egy sokkal inkább dichotomikus módon fogunk kutatni a hátralévő lehetséges hányadosok véges listájában.
Tízes módszer
Bizonyos civilizációkban, főként azok, amelyet átvették a tízes számrendszert, a tízes módszert használták. Ez a módszer az általános iskolában tanított hosszú osztás alapja. Kínában már nagyon korán megértették és alkalmazták ezt a módszert, ami lényegében egy egyszerű osztás, ahol a számítások a legmagasabb értékeknél kezdődnek.
Ez a kínai technikaegy háromsoros algoritmusban teljesedett ki:
- egy sor, ahol fokozatosan felépül a hányados
- egy sor, ahová az osztandó kerül és amely a számítás előrehaladtával alakul
- egy sor, ahová az osztó kerül
Ha már kijártad az általános iskolát, akkor ez a fajta euklideszi osztás ismerős lehet számodra, hiszen ez a mindannyiunk által ismert két merőleges egyenes mintáját követi. Nemes egyszerűséggel úgy kezdünk neki a feladatnak, hogy az osztót balra helyezzük, és kiszámoljuk az egészet anélkül, hogy a jobb oldali számokra figyelnénk.
Az első sorba a hányados kerül, a maradék pedig az osztandóra vonatkozó számokat helyettesíti. A számítás újra és újra megismétlődik, amíg be nem fejeződik. Mindebből jól látható a dolog euklideszi jellege, de alapvetően ez a módszer jobban megfelel az elvárásainknak és annak, amit egy matematikai számításról tudunk.
Az euklideszi osztás megítélése
A kollektív tudatban az euklideszi osztás – és általában a matematika – már-már valódi hírnévhez hasonló imázzsal rendelkezik. Ez a kép azonban gyakran téves és elfogult, amely nagyban hozzájárul ahhoz, hogy kultúránknak ezt a részét megközelíthetetlennek és nem épp vonzónak tartjuk. Végül is, ki társított valaha is pozitív, jóindulatú értékeket egy matematikai egyenlethez?! El kell ismernünk, nem sokan.
Az euklideszi osztás rossz megítélése
Az euklideszi osztásra általánosan egy furcsa és homályos matematikai koncepcióként tekintenek, amely senkit sem motivál túlságosan, és amely gyakran a teljes érthetetlenség kifejezőeszközeként jelenik meg. Az euklideszi osztás azonban se nem több, se nem kevesebb, mint egy alapvető osztási technika, amely a mindennapi életünkben is nagyon hasznos lehet,
és nem csak azért, hogy valami bonyolult dolog összehasonlításaként ezt hozzuk fel példának, hogy még érthetetlenebbé és bonyolultabbá tegyük az adott helyzetet, hogy összezavarjunk valakit vagy túlkomplikáljunk valamit. Az euklideszi osztást egyszerűen muszáj elsajátítani, amellyel párhuzamosan a róla alkotott közhelyek is elhalványulnak.
Az euklideszi osztás, avagy egy matematikai alapelv elsajátítása
Az euklideszi osztás egy olyan alapelv, amelyet valóban rendszeresen használunk a mindennapjaink során, még ha nem is vagyunk tudatában. Mindez elég ahhoz, hogy bárki újra átlapozza az iskolai tankönyveket, hogy megértse a legegyszerűbb helyzeteket is, és könnyen megoldást találjon az adott problémára.
Amellett, hogy hasznos, az euklideszi osztás izgalmas és motiváló is lehet, akár úgy döntesz, hogy magad csinálod, akár csak kíváncsi vagy a működésére. Sok más matematikai számításhoz hasonlóan valószínűleg ez az egyik legnagyobb erőssége, hogy az ember képes elmerülni a játékban, és valóban érdeklődni iránta, ahogy a figyelme rá összpontosul, míg az átlagemberek számára csak egy homályos, kevésbé vonzó fogalom marad.
Ha szeretnél mélyebben elmerülni a matematika világában, a linkekre kattintva megtudhatod, mi az affin függvény, mi az algebra jelentése és mi a logaritmus fogalma.
Tetszett ez a cikk? Értékeld!
Loading...