II. kerületi állami főreáliskola, Budapest, 1913

Dr. Kresznerics Károly: Az egész számok elmélete

Nyilvánvaló, hogy a legnagyobb közös osztót úgy is határozhatjuk meg, hogy nem írjuk ki mindjárt valamennyi adott számból a közös törzstényezőket a legkisebb kitevővel, hanem előbb csak két számból, vagyis előbb megállapítjuk két szám legnagyobb közös osztóját; ezután ennek a legnagyobb közös osztó és a harmadik számét és így tovább, míg az adott számok mindegyikét számításba nem vettük. Az utolsó legnagyobb közös osztó az adott számok legnagyobb közös osztója, mert ez tartalmazza valamennyi adott szám közös törzstényezőit a legkisebb kitevővel.

Ezen gondolat alapján kiszámíthatjuk kettőnél több szám legnagyobb közös osztóját az euklidesi algoritmussal is.

Példa. Számítsuk ki 630, 136S és 11880 legnagyobb közös osztóját az euklidesi algoritmussal.

11880:630= 18 1368:90 = 15

5580 468

630:540 = 1 90:18 = 5

540 : 90 = 6

(11880, 630) = 90 (1368, 90) = 18

Ennélfogva (630, 1368, 11880) = 18.

Könnyen beláthatjuk, hogy a legnagyobb közös osztót n szám (av a.>,... an) esetében is az adott számokkal következőképen állíthatjuk elő:

d = üy + —j— a., a., -j- • • •_+ ttn <xn, ahol az a-k negatív vagy pozitív egész számok.

Ez eljárással az n ismeretlenű diophantosi egyenletet is megoldhatjuk.

Példa.

Mivel ezért s ebből

Tehát egy megoldás

2*4-4 y — 7 z = 6 (2, 4, 7) = 1

1 =2.3 + 4(— 3) —7(1)

6 = 2.18 + 4 (— 18) — 7 (— 6). x = 18, y = — 18, z = — 6.

Az egész számok törzstényezőkre felbontott alakjából fölírható a közös többszörösük. A közös többszörös az adott számok mindegyikével osztható. Valamely számmal egy másik szám csak akkor osztható, ha az utóbbi szám minden törzstényezője legalább is oly kitevővel fordul elő benne, mint az első számban. Ä közös többszörösnek az adott számok valamennyi törzstényezőjét (nemcsak a közöseket) kell tartalmaznia, még pedig mind3*