Tartalom

• Lépések
• 1 /2 -es módszer: Elosztó algoritmus
• 2. módszer 2 -ből: Primer tényezők
• Tippek

A legnagyobb egész osztó (GCD) két egész számból a legnagyobb egész szám, amely megosztja ezeket a számokat. Például a 20 és 16 gcd értéke 4 (mind a 16, mind a 20 nagy osztókkal rendelkezik, de nem gyakoriak - például 8 a 16 osztója, de nem a 20 osztója). Van egy egyszerű és szisztematikus módszer a GCD megtalálására, az úgynevezett "Euklidész algoritmusa". Ez a cikk megmutatja, hogyan lehet megtalálni két egész szám legnagyobb közös osztóját.

Lépések

1 /2 -es módszer: Elosztó algoritmus

1. 1 Hagyjon ki minden mínusz jelet.
2. 2 Ismerje meg a terminológiát: ha 32 -t 5 -tel osztjuk,
   • 32 - osztalék
   • 5 - osztó
   • 6 - privát
   • 2 - maradék
3. 3 Határozza meg a számok közül a nagyobbat. Osztható lesz, és a kisebb szám lesz az osztó.
4. 4 Írja le a következő algoritmust: (osztalék) = (osztó) * (hányados) + (maradék)
5. 5 Tegyen egy nagyobb számot az osztalék helyére, és egy kisebb számot az osztó helyére.
6. 6 Keresse meg, hányszor osztja el a nagyobb számot a kisebbel, és írja az eredményt a hányados helyett.
7. 7 Keresse meg a maradékot, és írja be a megfelelő helyre az algoritmusban.
8. 8 Írja be újra az algoritmust, de (A) írja be az előző osztót új osztalékként, és (B) a korábbi maradékot új osztóként.
9. 9 Ismételje meg az előző lépést, amíg a maradék 0 nem lesz.
10. 10 Az utolsó osztó lesz a legnagyobb közös osztó (GCD).
11. 11 Például keressük a GCD -t 108 és 30 esetén:
12. 12 Figyeld meg, hogy az első sor 30 és 18 számai hogyan alkotják a második sort. Ezután 18 és 12 alkotják a harmadik sort, és 12 és 6 alkotják a negyedik sort. A 3, 1, 1 és 2 többszörösét nem használjuk. Azt jelzik, hogy az osztalék hányszor osztható az osztóval, és ezért minden sorra egyedi.

2. módszer 2 -ből: Primer tényezők

1. 1 Hagyjon ki minden mínusz jelet.
2. 2 Keresse meg a számok prímtényezőit. Mutassa be őket a képen látható módon.
   • Például 24 és 18 esetén:
     • 24-2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • Például 50 és 35 esetén:
     • 50-2 x 5 x 5
     • 35-5 x 7
3. 3 Keresse meg a közös elsődleges tényezőket.
   • Például 24 és 18 esetén:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Például 50 és 35 esetén:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Szorozzuk meg a közös prímtényezőket.
   • 24 és 18 esetén szorozzuk meg 2 és 3 és kap 6... A 6 a 24 és 18 legnagyobb közös nevezője.
   • Nincs mit szorozni 50 -re és 35 -re. 5 Az egyetlen közös elsődleges tényező, és ez a GCD.
5. 5 Készült!

Tippek

• Ennek egyik írási módja: osztalék> mod divider> = maradék; GCD (a, b) = b, ha a mod b = 0, és a gcd (a, b) = gcd (b, a mod b) különben.
• Példaként keressük a GCD-t (-77,91). Először is használja a 77 -et a -77 helyett: a GCD (-77.91) konvertál GCD -re (77.91). A 77 kevesebb, mint 91, ezért le kell cserélnünk őket, de fontoljuk meg, hogyan működik az algoritmus, ha nem. A 77 mod 91 számításakor 77 -et kapunk (77 = 91 x 0 + 77). Mivel ez nem nulla, figyelembe vesszük a helyzetet (b, a mod b), azaz GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 a maradék). Ez nem nulla, így a GCD (91,77) GCD (77,14) lesz. 77 mod 14 = 7. Ez nem nulla, így a GCD (77.14) GCD (14.7) lesz. 14 mod 7 = 0 (mivel 14/7 = 2 maradék nélkül). Válasz: GCD (-77,91) = 7.
• A leírt módszer nagyon hasznos a törtek egyszerűsítésére. A fenti példában: -77/91 = -11/13, mivel a 7 a -77 és 91 legnagyobb közös nevezője.
• Ha a és b egyenlő nullával, akkor bármely nem nulla szám osztója, tehát ebben az esetben nincs GCD (a matematikusok egyszerűen úgy vélik, hogy a 0 és 0 legnagyobb közös osztója 0).