Legnagyobb közös osztó (LNKO) kiszámítása

A legnagyobb közös osztó (röviden LNKO, jelölése általában (a; b)) az a legnagyobb pozitív egész szám, amely mindegyik megadott számot maradék nélkül osztja. A 84 és a 36 közös osztói például 1, 2, 3, 4, 6 és 12, közülük a legnagyobb a 12, tehát (84; 36) = 12.

Az LNKO-ra a matematikában és a hétköznapokban is szükség van:

• törtek egyszerűsítése: a 36/84 tört az LNKO-val (12) osztva 3/7,
• elosztási feladatok: mekkora egyforma csomagokba lehet maradék nélkül szétosztani két különböző mennyiséget,
• burkolás, darabolás: mekkora a legnagyobb négyzetlap, amivel egy téglalap hézag és vágás nélkül lefedhető.

Minden a böngésződben történik, a beírt adat nem kerül fel szerverre.

Bontsd fel a számokat prímtényezőkre, majd vedd a közös prímtényezőket a legkisebb előforduló kitevőn, és szorozd össze őket.

Kidolgozott példa: (84; 36)

1. 84 = 2 × 2 × 3 × 7 = 2² × 3 × 7
2. 36 = 2 × 2 × 3 × 3 = 2² × 3²
3. Közös prímtényezők: a 2 (legkisebb kitevő: 2) és a 3 (legkisebb kitevő: 1). A 7 csak a 84-ben szerepel, ezért kimarad.
4. LNKO = 2² × 3 = 4 × 3 = 12

Három szám: (48; 180; 120)

Közös tényezők: 2 (legkisebb kitevő 2) és 3 (legkisebb kitevő 1). Az 5 hiányzik a 48-ból. LNKO = 2² × 3 = 12.

Ez a módszer kisebb számoknál áttekinthető, és iskolai feladatokban gyakran ezt várják.

Nagyobb számoknál a prímtényezős felbontás nehézkes. Az euklideszi algoritmus gyorsabb: a nagyobb számot elosztod a kisebbel, majd a kisebbet a maradékkal, és ezt addig ismétled, amíg a maradék 0 nem lesz. Az utolsó nem nulla maradék az LNKO.

Kidolgozott példa: (84; 36)

1. 84 = 2 × 36 + 12
2. 36 = 3 × 12 + 0
3. Az utolsó nem nulla maradék: 12.

Nagyobb számokkal: (1071; 462)

1. 1071 = 2 × 462 + 147
2. 462 = 3 × 147 + 21
3. 147 = 7 × 21 + 0
4. LNKO = 21.

Kettőnél több számnál lépésenként haladj: (48; 180; 120) = ((48; 180); 120) = (12; 120) = 12.

Néhány összefüggés, amely gyorsítja a számolást:

• LNKO × LKKT = a × b két pozitív egész számra. Például 12 × 252 = 84 × 36 = 3024, így ha az egyiket ismered, a másik egy osztással megvan.
• Relatív prímek: ha két szám LNKO-ja 1, relatív prímek, például 8 és 15. Ilyenkor a törtük (8/15) már nem egyszerűsíthető.
• Ha az egyik szám osztja a másikat, az LNKO a kisebb szám: (12; 48) = 12.
• (a; 0) = a, mert minden szám osztja a nullát.

Szöveges feladat: egy 84 cm × 36 cm-es falfelületet egyforma, minél nagyobb négyzet alakú csempével szeretnél vágás nélkül lefedni. A csempe oldala a két méret LNKO-ja: 12 cm. Ekkor 7 × 3 = 21 csempe kell.

Másik példa: 48 almát és 180 diót szeretnél egyforma csomagokba osztani úgy, hogy minden csomagban ugyanannyi alma és ugyanannyi dió legyen, és ne maradjon semmi. A legtöbb csomag száma 12, mindegyikben 4 alma és 15 dió.

1. LNKO és LKKT összekeverése. Az LNKO a legnagyobb közös osztó, sosem nagyobb a legkisebb számnál. Az LKKT a legkisebb közös többszörös, sosem kisebb a legnagyobb számnál.
2. Nem közös tényező bevétele. Prímtényezős felbontásnál csak azt a prímet szabad figyelembe venni, amely minden számban szerepel.
3. Nagyobb kitevő választása. Az LNKO-nál a legkisebb kitevő kell; a legnagyobb az LKKT-nál használatos.
4. Hiányos felbontás. Ellenőrizd, hogy minden tényező valóban prím: a 9 nem prím, hanem 3².
5. Ellenőrzés elmaradása. Az eredményt egyszerű osztással ellenőrizd: 84 / 12 = 7 és 36 / 12 = 3, mindkettő egész.

A legnagyobb közös osztó minden olyan feladatban előkerül, ahol egy arányt a legegyszerűbb alakjára kell hozni.

Képarány kiszámítása. Egy kijelző felbontása 1920 × 1080 képpont. Milyen a képaránya?

1. (1920; 1080) = 120.
2. 1920 / 120 = 16 és 1080 / 120 = 9.
3. A képarány 16:9.

Ugyanígy 1280 × 1024 esetén az LNKO 256, a képarány 5:4. A 2560 × 1440 felbontás LNKO-ja 160, ez is 16:9.

Keverési arány. Ha egy recepthez 750 g lisztet és 250 g cukrot írnak, (750; 250) = 250, így az arány 3:1. Ebből már bármilyen mennyiségre könnyű átszámolni.

Törtek egyszerűsítése egy lépésben. A 84/36 tört számlálóját és nevezőjét az LNKO-val (12) elosztva rögtön a végső alakot kapod: 7/3. Ha kisebb közös osztóval egyszerűsítesz, több lépés kell.

Miért működik az euklideszi algoritmus? Ha egy szám osztja az a-t és a b-t, akkor osztja a különbségüket és a maradékos osztás maradékát is. Ezért (a; b) = (b; maradék), és a számok minden lépésben kisebbek lesznek, amíg a maradék el nem fogy. Ezért gyors az algoritmus nagyon nagy számok esetén is.