Közös osztó

Hogyha a, b, c, ... t egész számok, akkor minden egész számot, mely az összeseknek osztója, e számok K.-jának nevezzük. E K.-k felkeresésénél a feladat általánosságának megszorítása nélkül feltételezhetjük, hogy a számok, melyeknek K.-i meghatározandók, mind pozitivok, valamint a K.-k közül is csak a pozitivoknak meghatározására szorítkozhatunk.

Hogyha a kétszám a és b közül a és b-nek többszöröse, akkor K.-ik nem mások mint b-nek osztói, melyek közt a legnagyobb b. Midőn azonban a két szám közül, melynek K.-i meghatározandók, az egyik nem többszöröse a másiknak, a K.-k nem adódnak ki oly közvetlenül. Ily esetekben a gyakorlati számításokban legkönnyebben keresztülvihető és az elméleti tárgyalás szempontjából is legfontosabb módszer az, mely a legnagyobb K. felkeresésére szolgáló algoritmus neve alatt ismeretes. E módszer mindjárt a két adott szám legnagyobb K.-jára vezet, melynek leglényegesebb tulajdonsága az, hogy minden osztója a két szám K.-ja és viszont a két szám minden K.-ja által osztható. A legnagyobb K. felkeresése után tehát a két szám össze K.-inak felkeresését a legnagyobb K. osztóinak felkeresésére vezettük vissza. Maga az említett módszer megköveteli, hogy az adott két szám közül, mely ismét a és b legyen, a nagyobbat - tételezzük fel, hogy az a - elosszuk a kisebbik által. Megjegyzendő, hogy itt osztás alatt nem a szorzás megfordításából származó műveletet értjük, mely mostani feltételünk mellett, hogy a nem többszöröse b-nek, törtszámu hányadosra vezetne, hanem azt az eljárást, melynek segítségével megállapíthatjuk, hogy melyik az a legnagyobb egész szám q, mely b-vel megszorozva az a-nál nem nagyobb szorzatot ad eredményül és melyik az a pozitiv r szám, melyet esetleg még bq-hoz hozzá kell adnunk, hogy a-t kapjuk eredményül. Az elemi számtan kifejezésmódjával élve keressük, hogy hányszor van benne a b az a-ban és hogy mennyi az osztási maradék. A részletes vizsgálat mutatja, hogy a és b minden K.-ja egyszersmind b és r K.-ja és viszont b és r minden K.-ja a-nak és b-nek is K.-ja. Az eredeti feladatot tehát, mely a és b K.-inak meghatározását kivánja, emez első lépés után visszavezettük arra, mely b és r K.-inak felkeresését megköveteli. Ez annyiban egyszerübb feladat az eredetinél, mert r mint osztási maradék minden esetre kisebb az osztónál, b-nál és igy az eredeti számpár a, b helyébe két kisebb számból álló számpár b, r lép. Hogyha már mostan r osztója a b-nek, az lesz a b és r és igy egyszersmind a és b legnagyobb K.-ja. Ellenkező esetben ugyanazzal az eljárással, mellyel az a, b számpárról tértünk át a b, r számpárra, erről áttérhetünk egy r, r1 számpárra. Ezt az eljárást mindaddig kel folytatnunk, mig olyan rn-1, rn számpárhoz nem jutunk, melyben a kisebbik szám rn osztója a másiknak. Ez az rn szám lesz az összes megelőző számpárokhoz tartozó számoknak, valamint az adott a és b számoknak is legnagyobb K.-ja.

Hogyha három egész szám, a, b, c legnagyobb K.-ját kell keresnünk, először keressük az első két szám legnagyobb K.-ját, azután pedig meghatározuk ennek és a harmadik számnak legnagyobb K.-ját. Ez lesz majd a három szám legnagyobb K.-ja, melynek osztói ugy mint két adott szám esetében szolgáltatják az adott számoknak összes K.-it. Egész hasonló módon nyerhetjük akárhány egész szám legnagyobb K.-ját.

A racionális egész függvények elméletében, mely az oszthatóság kérdésének szempontjából egészen analog a közönséges egész számok oszthatóságára vonatkozó elmélettel, két v. több racionális egész függvény legnagyobb K.-ját ugyanannak az algoritmusnak segítségével állíthatjuk elő, mint két vagy több egész szám legnagyobb K.-ját.

Forrás: Pallas Nagylexikon