II. kerületi állami főreáliskola, Budapest, 1913
Dr. Kresznerics Károly: Az egész számok elmélete
22 Teljes indukció: föltesszük, hogy mi-1 = a + b ß^ mi = ű at- + ^ fiákkor /W/+1. = trii-i - tn-i hi+1 = a (ai„1 — a; A/+1) -f- b (ßi-* - ßt- A/+1) = = a at+i+ ^ ß<+iA tétel tehát általánosságban, minden maradékra, így a legnagyobb közös osztóra is érvényes. Az ß a —|— ^ ß = i/ egyenlőség adja az ax-\- by = cl disphantosi (határozatlan) egyenlet egy megoldását. Példa. Határozzuk meg 19a: + 7j' = 3 egyenletnek egy egész számú megoldását. 19 = 7.3 — 2 2 = 7.3 — 19 7 = 2.3 + 1 1=7 — 2.3 = 7 — 3 (7.3 — 19) 1 = 19.3 + 7 (—8) 3 = 19.9 + 7 (—24) s így egy megoldás: x — 9, y —— 24. Kettőnél több szám legnagyobb közös osztóját későbben fogjuk meghatározni. 4. A viszonylagos törzsszámokróí. Hogy két szám viszonylagos törzsszám-e vagy sem, még nagy számok esetében is, aránylag egyszerű számítással, az euklidesi algoritmussal döntjük el. A következőkben a viszonylagos törzsszámokról néhány tételt bizonyítunk be. 1. Két egymásra következő egész szám relatív prímszám, mert ha a két szám osztható volna valamely harmadikkal, akkor a különbségük, vagyis 1 is osztható volna vele. 2. Különböző abszolút prímszámok egyszersmind, relatív prímszámok. 3. Főtétel: a legnagyobb közös osztó meghatározásánál a szorzatból a másik számhoz relatív prímtényezőket elhagyhatjuk. Vagyis ha (a, c) = 1, akkor (a b, c) = (b, c).
