II. kerületi állami főreáliskola, Budapest, 1913
Dr. Kresznerics Károly: Az egész számok elmélete
\ 21 már Eüklides ismerte s ezért nevezzük euklidesi-, vagy a legnagyobb közös osztó algoritmusának.*) Példa. Határozzuk meg 924 és 234 legnagyobb közös osztóját. A gyakorlati számításban mindenkor a maradék elé írjuk a volt osztót osztandónak. 924 : 234 = 3 234 : 222 = 1 222: 12 = 18 102 . 12:6 = 2 Tehát (924, 234) = 6. A legnagyobb közös osztó kiszámítására az a = b h-\- m ■egyenlőség helyett az a = b (h -f- 1) — (b — m) egyenlőséget is használhatjuk; ez előnyösebb, ha b — m <gm vagyis 2 m y> b. Ekkor a — (b — m) negatív maradékot abszolút értékre nézve legkisebb maradék-nak nevezzük. Ha a legnagyobb közös osztó algoritmusát ezzel az abszolút értékre nézve kisebb maradékkal végezzük, gyorsabban jutunk célhoz. Példa. 32:12 = 2 32.: 12 = 3 12:8 = 1 12: — 4 = — 3 8:4 = 2 Tétel: Ha a,b legnagyobb közös osztója d, akkor mindig találunk két (pozitív vagy negatív) egész számot a-t és ß-t úgy, hogy a ct-\- b $ —d. Bizonyítás. Az euklidesi algoritmus egyenlőségei alapján mx = a — bhx = a .1 -f- b (— hj) = a -|- b m± = b — mxh.,=b — lu [a <xx -f- b ßi) = a (— <xx h.,) -j- b (1 — ßx h.j) = = a otg—I— b ßä. *) Algoritmusnak nevezünk minden ismétlődő számolási eljárást, amellyel minden konkrét esetben az eredményt kiszámíthatjuk, de az eredményt nem kaphatjuk meg matematikai kifejezés alakjában.
