A legnagyobb közös tényező, más néven a legnagyobb közös osztó és a legnagyobb közös tényező, a két vagy több egész számmal megosztott osztók közül a legnagyobbra vonatkozik..
A, b legnagyobb közös osztóját (a, b) jelöljük. Hasonlóképpen, a, b, c legnagyobb közös osztóját (a, b, c) jelöljük. A több egész szám legnagyobb közös osztóinak ugyanaz az előjele.
Sokféleképpen lehet megtalálni a legnagyobb közös osztót. A gyakori tényezők közé tartozik a prímtényezők száma, a rövid osztás, a gördülő fázisosztás és a több kivonás.
A legnagyobb közös osztónak megfelelő fogalom a legkisebb közös többszörös, és a, b legkisebb közös többszöröse [a, b].
Ha az a szám osztható b számmal, akkor a-t b többszörösének, b-t pedig a osztójának nevezzük..
Mind az osztók, mind a többszörösek egy egész szám viszonyát jelentik a másikhoz, és nem létezhetnek egyedül. Például csak azt mondhatjuk, hogy a 16 egy bizonyos szám többszöröse, a 2 pedig egy bizonyos szám osztója, de nem mondhatjuk külön azt, hogy 16 többszöröse és 2 osztója..
Két vagy több egész szám legnagyobb közös osztója (LNÖ), más néven legnagyobb közös tényezője (LNÖ), a legnagyobb pozitív szám, amely pontosan osztja mindegyiket (maradék nélkül).
Például a 18 és a 24 LNÖ-je 6, mert a 6 a legnagyobb szám, amely mindkettőt egyenletesen osztja.
Az LNÖ hasznos:
Törtek egyszerűsítése a legkisebb tagjaikra.
Tényezőkre bontás és matematikai egyenletek megoldása.
Arányok egyszerűsítése a legegyszerűbb formájukra.
Számelméleti problémák megoldása oszthatósággal vagy moduláris aritmetikával.
Közös minták keresése egész számokban, vagy ismétlődő struktúrákon alapuló algoritmusok optimalizálása.
Segít kiküszöbölni a redundanciát és hatékonyságot elérni matematikai és valós alkalmazásokban.
Két szám legnagyobb közös osztójának megtalálására többféle módszer létezik:
Tényezők felsorolása: Felsoroljuk mindkét szám összes osztóját, és keressük meg a legnagyobb közös osztójukat.
Prímtényezős felbontás: Bontsuk mindkét számot prímtényezőire, és szorozzuk meg a közös osztókat egyesek.
Euklideszi algoritmus: Ismételten vonjuk ki a kisebb számot a nagyobbból, vagy osszuk maradékokkal, amíg a maradék nulla nem lesz. Az utolsó nem nulla maradék a GCD.
Példa az euklideszi algoritmusra a GCD(a, b) esetén:
GCD(48, 18):
48 ÷ 18 = 2 maradék 12
18 ÷ 12 = 1 maradék 6
12 ÷ 6 = 2 maradék 0
→ GCD 6
Használjuk a GCD-t, ha:
Törtek vagy arányok egyszerű alakra redukálása.
Diofantosz-egyenletek megoldása (egész megoldású egyenletek).
Ciklusokat, forgatásokat vagy partíciókat tartalmazó algoritmusok optimalizálása.
Két szám relatív prímszám-e (azaz a legnagyobb közös osztójuk 1).
Elemek csoportokba osztása a lehető legnagyobb egyenlő mérettel (pl. valami egyenletes elosztása emberek vagy konténerek között).
A legnagyobb közös osztó alapvető fontosságú mind az alapvető aritmetikában, mind a fejlettebb számelméletben vagy algoritmustervezésben.
