II. kerületi állami főreáliskola, Budapest, 1913
Dr. Kresznerics Károly: Az egész számok elmélete
20 Ennek az eljárásnak valamikor végződnie kell, mert az egymásután föllépő maradékok a pozitív egész számok fogyó sorát alkotják, amely mindig véges. Legkedvezőtlenebb esetben, ha a maradékok mindig csak eggyel fogynak, 6 számú lépés után zérus maradékhoz jutunk. Tegyük föl, hogy my-rX=o (példánkban mx = ó), ekkor mr= mr /?,-+! -j- o. Azt állítjuk, hogy ö-nak és b-nek legnagyobb közös osztója mr (példánkban 6). Legyen c közös osztója ß-nak és b-nek, akkor az első egyenlőség alapján a b . = - K ml c c ' c ’ ahol ^-és^ egész számok, tehát ^ is egész szám. Vagyis az osztandó és osztó minden közös osztója, egyúttal az osztónak és maradéknak is közös osztója. Másrészt, ha d közös osztója b és /7zrnek, akkor az a d b_h d"1 + d egyenlőségből következik, hogy is egész szám, vagyis d közös osztója fl-nak és 6-nek is. Mivel a, b és b, mx közös osztóinak sora megegyezik, ezért legnagyobb közös osztójuk is ugyanaz. Tehát az osztandó és osztó legnagyobb közös osztója ugyanaz> mint az osztó és maradéké. így két szám legnagyobb közös osztójának meghatározását két kisebb szám legnagyobb közös osztójának kikeresésére vezettük vissza. Az előbb bebizonyított tétel alapján (a, b) — (6, mj) = {mx, m,) =. . . = {mr-lt mr) — (mn o) = mr, tehát my legnagyobb közös osztója ß-nak és 6-nek. Ezt az eljárást, amellyel a legnagyobb közös osztót kiszámítjuk^
