GCD & LCM számológép

A GCD, más néven a legnagyobb közös tényező (Greatest Common Factor, GCF) az a legnagyobb pozitív egész szám, amely mindkét számot maradék nélkül osztja. Például 12 és 18 GCD-je 6, mert 6 a legnagyobb szám, amely mindkettőt egyenletesen osztja.

Az LCM a legkisebb pozitív egész szám, amely mindkét számmal osztható. Például a 4 és a 6 LCM-je 12, mert a 12 a legkisebb szám, amely osztható 4-gyel és 6-mal.

Két pozitív egész számra a és b: GCD(a,b) × LCM(a,b) = a × b. Ez az összefüggés lehetővé teszi az LCM kiszámítását, ha ismerjük a GCD-t, vagy fordítva.

A GCD nélkülözhetetlen a törtek egyszerűsítéséhez (a számláló és a nevező osztása a GCD-vel), a diofantikus egyenletek megoldásához, valamint a kriptográfia és a számítástechnika különböző alkalmazásaihoz.

Egy tört egyszerűsítéséhez osszuk el a számlálót és a nevezőt a GCD-vel. Például a 24/36 egyszerűsítéséhez: keressük meg a GCD(24,36) = 12-t, majd osszuk el mindkettőt 12-vel, hogy megkapjuk a 2/3-ot. Így megkapjuk a törtet a legalacsonyabb értékben.

Az LCM az ismétlődő események szinkronizálásakor használatos. Ilyen például annak megállapítása, hogy mikor érkezik két busz egyszerre, a törtek összeadásához szükséges közös nevezők meghatározása, ismétlődő feladatok ütemezése, vagy annak megtervezése, hogy a különböző fogszámú fogaskerekek mikor igazodnak egymáshoz.

Minden számot bontsunk prímtényezőkre, majd szorozzuk meg a közös tényezőket a legkisebb hatványokkal. Például 48 = 2^4 × 3 és 18 = 2 × 3^2. A közös tényezők 2^1 és 3^1, tehát GCD = 2 × 3 = 6.

Minden számot bontsunk prímtényezőkre, majd szorozzuk meg az összes tényezőt a legnagyobb hatványokkal. A 12 = 2^2 × 3 és a 18 = 2 × 3^2 esetében vegyük a 2^2-t és a 3^2-t, így LCM = 4 × 9 = 36.

Az euklideszi algoritmus hatékonyan találja meg a GCD-t többszöri osztással és maradékok kivonásával. A GCD(48,18) esetében: Ha a maradék 0, akkor az utolsó osztó (6) a GCD.