Legnagyobb közös osztó
Két egész szám legnagyobb közös osztója az a szám, amely maradék nélkül osztja mindkét számot, és nincs nála nagyobb másik szám, amely szintén maradék nélkül osztaná mindkét számot.
Példaként vegyük a 24 és a 32 számot. Mi a legnagyobb közös osztójuk? Először is olyan számot keresünk, amely mindkét számot osztja.
- Például a 12 osztja a 24-et, de nem osztja a 32-t, mert 32 / 12 eredménye 2,666…, ami nem egész szám. A 12 tehát nem lehet a 24 és a 32 legnagyobb közös osztója.
- Mit szólsz a 4-hez? Az mindkét számot osztja, 24 / 4 egyenlő 6-tal, 32 / 4 pedig 8-cal. A 4 tehát az első jelöltünk. Létezik nála nagyobb szám, amely mindkét számot osztja?
- A 8 osztja a 24-et is, a 32-t is, és egyúttal nagyobb, mint a 4.
- Nincs más, 8-nál nagyobb szám, amely mindkét számot osztaná. A 8 tehát a 24 és a 32 legnagyobb közös osztója.
Az euklideszi algoritmus a legnagyobb közös osztó megkeresésére
Van egy viszonylag egyszerű módszer arra, hogy két szám legnagyobb közös osztóját megtaláljuk, az euklideszi algoritmus. Induljunk ki két számból, x-ből és y-ból, amelyekre a legnagyobb közös osztót keressük. Példaként próbáljuk ki az x = 50 és y = 35 számokon. Ezután így haladunk:
- Elvégezzük az x / y osztást, és megjegyezzük a maradékot. Ezt a maradékot z-vel jelöljük. A példánkban ez az 50 / 35 osztás, amelynek maradéka z = 15.
- Most felcseréljük a változókat: az x változóba eltároljuk y értékét, az y változóba pedig z értékét. Az x eredeti értékét eldobjuk. E lépés után x = 35 és y = 15.
- Most megnézzük, hogy y egyenlő-e nullával. Ha igen, a legnagyobb közös osztó az x szám. Mivel y nem egyenlő nullával, folytatjuk, és az egész eljárást megismételjük az első ponttól.
- Újra elvégezzük az x / y osztást, vagyis a 35 / 15 osztást, amelynek maradéka z = 5.
- Elvégezzük a változók felcserélését, így x = 15 és y = 5. Mivel y nem egyenlő nullával, folytatjuk.
- Elvégezzük az x / y osztást, vagyis a 15 / 5 osztást. A maradék z = 0.
- Felcseréljük a változókat, így x = 5 és y = 0.
- Ekkor y = 0, és az algoritmusunk véget ér. A legnagyobb közös osztó az x = 5 szám.
Fontos, hogy a számok sorrendje nem számít. Ha a példa számait felcserélnénk, az x = 35 és y = 50 párt kapnánk. Az eljárás ugyanaz lenne:
- Elvégezzük az x / y osztást, vagyis a 35 / 50 osztást, amelynek maradéka z = 35.
- Felcseréljük a változókat: x = 50 és y = 35.
- Látjuk, hogy e lépés után csak felcseréltük az x és y változók tartalmát egymás között…
Számológép
Ez a számológép kiszámítja a legnagyobb közös osztót.
