Euklideszi algoritmus megállapítását csomópont

előző ◈ a következő

Euklideszi algoritmus - a módszert kell találni a legnagyobb közös osztó két szám.

Figyelembe vesszük azt a tényt, hogy ha az egyik egy pár egész egyenletesen elosztja a többi, a GCD egyenlő a kisebb őket. Megjegyzés ez lehet a következő: ha a / b (teljesen), majd a legnagyobb közös osztója (a; b) = b.

Figyelembe vesszük a második tény. Ha a szám nagyobb, mint egymást, a legnagyobb közös osztó egy legnagyobb közös osztó egy kisebb számot a pár, és a kisebb-nagyobb eltérések. Van írva, mint ez: ha egy

Igazoljuk, hogy GCD (a; b) = lnko (a, b - a) a következők lehetnek. Legyen b - a = c. Ha bármennyi osztja a és b, akkor ossza el egyenletesen, és c. Elvégre, ha a és b különböző, a térelválasztó helyezzük őket az egész, de eltérő számú alkalommal. És egy kivonásával a másik, az osztó kell elhelyezni, mint egész szám alkalommal kapott különbséget.

Ha egymás után csökkentik a és b, előbb-utóbb jön egy ilyen kisebb érték őket, ami egyenletesen osztja nagyobb. Minimális ebben a pár fog GCD kezdeti pár természetes számok. Ez az euklideszi algoritmus.

Vegyünk egy konkrét példát. Tegyük fel, hogy szeretné megtalálni a GCD (108, 72).

  1. 108 nem osztható 72. Így kapunk egy pár 72 és 108-72 = 36
  2. 72 osztható GCD 36. eszközzel (108, 72) = 36.

Találunk GCD (44, 60):

  1. 60 nem osztható 44. 60-44 = 16
  2. 44 nem osztható 16. 44-16 = 28
  3. 28 nem osztható 16. 28-16 = 12
  4. 16 nem osztható 12 16-12 = 4
  5. 12 osztható 4. Ezután GCD (44, 60) = 4

Kapcsolódó cikkek

előző ◈ a következő