II. kerületi állami főreáliskola, Budapest, 1913
Dr. Kresznerics Károly: Az egész számok elmélete
r ennélfogva a = a"(8D), 6 = 6"(SD), tehát 8 D közös osztója tz-nak és 6-nek s így feltevésünk szerint oZ) osztója D-nek, ami csak úgy lehetséges, hogy 8=1, vagyis a', b’ relatív prímszámok. Ámde akkor egy előbbi tétel alapján D legnagyobb közös osztója ö-nak és 6-nek. Miután a legnagyobb közös osztónak valamennyi osztója az adott számpárnak valamennyi közös osztója, ezért eredeti feladatunkat, két szám valamennyi közös osztójának meghatározását, visszavezettük egy szám, t. i. a legnagyobb közös osztó minden osztójának meghatározására. Az a, b számpár legnagyobb közös osztóját a következő módon jelöljük: (a, b). Példa. (9, 21) = 3. Keressük a legnagyobb közös osztó egyszerűbb kiszámítási módját. Két esetet különböztetünk meg: 1. a osztható 6-vel, ekkor (a, b) — b; (o, b) = b. 2. a rrem osztható 6-ve 1, ekkor föltehetjük, hogy a > b. A nagyobb számot*), a-1 elosztjuk a kisebbel, 6-vel, a maradék mv amely 6-nél kisebb; ezután 6-t elosztjuk mx-gyei és ha m1 nincsen meg maradék nélkül 6-ben, nyerünk valami m., maradékot, amely mx-nél kisebb. Ha ezt az eljárást folytatjuk, a maradékok mindig kisebbednek és mivel a 6-nél kisebb pozitív számok sora mindig véges, bizonyos (legfeljebb 6) számú osztás után zérus maradékhoz kell jutnunk. A legutolsó osztó a legnagyobb közös osztó. Az eljárást a következő egyenlőségekkel fejezhetjük ki: 19 a — b K + Példa. 540 = 462. 1 _L [ 78 b-= mt 6á + m.> 462 = 78 . 5 "T 72 m1 = mo ^3 + mA 78 = 72 . 1 I ~T 6 nu = ^3' + mi 72 = 6. 12 i 0 mr- 2 --mr-1 K + in,. *) ugyanarra az eredményre jutunk, ha a kisebb számot elosztjuk a nagyobbal, csakhogy akkor egy fölösleges osztást kell végeznünk 2*
