Episode I

Alice és Bob

17. fejezet

Alice és Bob ókori haverja

Az előző fejezetben megismerkedtünk a legfontosabb számelméleti fogalmakkal: oszthatóság, egység, asszociált, felbonthatatlan és prímtulajdonságú elemek. Ezután ismertettük a számelmélet alaptételét, amely azt biztosítja egy integritástartományban, hogy annak minden – nemnulla és nem egység – elemét egyértelműen elő lehessen állítani felbonthatatlan elemek szorzataként. Megemlítettük, hogy ez nem minden integritástartományban teljesül. Végül megmutattuk, hogy ha viszont teljesül, akkor a felbonthatatlanok és a prímek fogalma szükségképpen egybe kell essen. Azt is megemlítettük ugyanakkor, hogy ez csupán szükséges, de nem elégséges feltétel az alaptétel teljesüléséhez.

De vajon milyen elégséges feltételt tudunk mutatni erre vonatkozóan? Az egész számok gyűrűje teljesíti-e ezt a kritériumot? Mit jelent a "legnagyobb közös osztó" fogalma és hogyan lehet villámgyorsan kiszámolni az úgynevezett euklidészi algoritmus segítségével? Mit tudunk mondani erről általános integritástartományokra? Mik azok az euklidészi gyűrűk és mi közük a számelmélet alaptételéhez? Ebben a fejezetben erről lesz szó...

Figyelem! Ez a fejezet erőteljesen épít az előző fejezetben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:

Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni az előző fejezetet, mivel gyakran hivatkozni fogunk rájuk.

A modern kriptográfiai eljárások szempontjából alapvető fontosságú, hogy az egész számok gyűrűjében teljesüljön a számelmélet alaptétele. Egyrészt ez teszi lehetővé, hogy minden egész szám egyértelműen előáll az úgynevezett "prímszámok" – amelyek tehát a $Z$ gyűrű felbonthatatlan elemei – szorzataként, és így a számelméleti kapcsolatot biztosítja a publikus és a titkos kulcsok között ezekben az eljárásokban. Másrészt a prímtényezős felbontás feladatának algoritmikus nehézsége biztosítja azt, hogy egy támadó számára beláthatatlanul sok ideig tartson kiszámítani a titkos kulcsot a hozzá tartozó publikus kulcsból. Ezért ebben a fejezetben alapvető célunk annak igazolása, hogy $Z$ gyűrűben valóban teljesül a számelmélet alaptétele.

Ennek keretében meg fogunk ismerkedni egy ókorból származó eljárással, az "euklidészi algoritmussal". Ennek segítségével két egész szám úgynevezett "legnagyobb közös osztóját" fogjuk tudni elképesztően hatékonyan kiszámítani. Ez az eljárás a továbbiakban is fontos lesz számunkra, mivel mind az RSA-ban, mind pedig a nagy prímszámok keresését lehetővé tévő úgynevezett "prímtesztelési eljárásokban" alapvető szerepet játszik. Ezután ezt az eljárást fogjuk általánosítani oly módon, hogy ne csak az egész számok gyűrűjén, hanem minden olyan integritástartományon működjön, amely bizonyos kritériumoknak eleget tesz. Ezeket "euklidészi gyűrűknek" fogjuk nevezni. Végül megmutatjuk, hogy minden euklidészi gyűrűben – és így speciálisan az egész számok gyűrűjében is – teljesül a számelmélet alaptétele.

17.1A legnagyobb közös osztó

Először is tisztázzuk, hogy mit értünk két egész szám "legnagyobb közös osztóján". Tegyük fel, hogy $a$ és $b$ valamilyen egész számok. Azt mondjuk, hogy a $c$ egész szám $a$ és $b$ "közös osztója", ha egyidejűleg teljesülnek a $c ∣ a$ és $c ∣ b$ oszthatóságok. Például a $18$ és $24$ közös osztói az $1$ , $2$ , $3$ és $6$ egész számok, valamint ezek ellentettjei. A "legnagyobb közös osztó" alatt értelemszerűen ezek közül a legnagyobbat, azaz a $6$ egész számot értjük. Általánosságban az $a$ és $b$ egész számok "legnagyobb közös osztóját" $(a, b)$ -vel szoktuk jelölni. Az iménti példában tehát $(18, 24) = 6$ .

A "legnagyobb közös osztó" definícióját a fentiek alapján tehát a következőképpen adjuk meg.

17.1. Definíció (Legnagyobb közös osztó):

Tegyük fel, hogy $a$ és $b$ tetszőleges egész számok a $Z$ gyűrűben. Az $a$ és $b$ legnagyobb közös osztója a $d$ egész szám, ha teljesül az alábbi két tulajdonság:

Teljesülnek a

d ∣ a

és

d ∣ b

oszthatóságok, azaz

d

közös osztó.

Tetszőleges

c

egész szám esetén ha fennállnak a

c ∣ a

és

c ∣ b

oszthatóságok, akkor

c \leq d

Azaz a legnagyobb közös osztónál nincs nagyobb közös osztó. Az $a$ és $b$ egész számok legnagyobb közös osztójának jelölése: $(a, b)$ .

♣

Megjegyzés:

A definícióból következik, hogy $a = b = 0$ esetén nem létezik az $(a, b)$ legnagyobb közös osztó, hiszen a 16.2. Tétel 3. pontja alapján a $0$ -nak minden egész szám osztója, így közöttük nincs legnagyobb.

♣

Kérdés, hogy az iménti megjegyzésben közölt eseten kívül vajon minden más esetben létezik-e a legnagyobb közös osztó. Ennek igazolásához először ismertetünk egy segédtételt.

17.2. Lemma:

Ha $a$ és $0 < b$ tetszőleges egész számok, akkor az $a ∣ b$ oszthatóságból következik, hogy $a \leq b$ . Azaz tetszőleges pozitív egész szám legalább akkora, mint bármely osztója.

♣

Bizonyítás:

Az biztos, hogy $a \neq = 0$ , hiszen máskülönben $b = 0$ lenne a 16.2. Tétel 4. pontja miatt. A rendezési reláció trichotómiájából, valamint $a \neq = 0$ -ból következően $a < 0$ vagy $a > 0$ közül pontosan az egyik teljesül. Az $a < 0$ esettel nem kell különösebben foglalkoznunk, hiszen ekkor $0 < b$ miatt nyilván következik $a \leq b$ a rendezési reláció tranzitivitása miatt.

Nézzük tehát a $0 < a$ esetet. A 16.1. Definíció alapján a $a ∣ b$ oszthatóság azt jelenti, hogy létezik olyan $k$ egész szám, amelyre teljesül az alábbi egyenlet:

ak = b

A 13.11. Definíció szerinti pozitív és negatív egész számok, valamint a $0$ a 13.10. Tétel értelmében lefedik a teljes $Z$ halmazt. Emiatt az egészek szorzásának 14.3. Definíciója alapján egy szorzat előjele az alábbiak szerint alakulhat a tényezők előjelének függvényében:

+ \cdot + + \cdot - - \cdot + - \cdot - = + = - = - = +

Mivel a fenti egyenletben $a$ is és $b$ is pozitív, ezért szükségképpen $k$ is pozitív kell legyen, azaz $0 < k$ . Továbbá az egyenlet a disztributivitási szabályok miatt átalakítható a következőképpen:

ak = a (1 + k - 1) = a + a (k - 1) = b

Itt az $a (k - 1)$ szorzatról elmondhatjuk, hogy pozitív, vagy pedig $0$ , hiszen $a$ ugye pozitív, $k - 1$ pedig pozitív vagy $0$ . Létezik tehát olyan nemnegatív egész szám, amelyet $a$ -hoz adva $b$ -t kapunk, nevezetesen az $a (k - 1)$ . Ez viszont a 15.18. Tételben szereplő $\leq$ reláció definíciója miatt épp azt jelenti, hogy $a \leq b$ .

∎

Ennek a segédtételnek a felhasználásával mostmár könnyen meg tudjuk mutatni, hogy a $Z$ gyűrűben mindig létezik $a$ és $b$ legnagyobb közös osztója, amennyiben legalább az egyikük nem $0$ .

17.3. Tétel:

Ha $a$ és $b$ tetszőleges egész szám, és közülük legalább az egyik nem $0$ , akkor létezik az $(a, b)$ legnagyobb közös osztó.

♣

Bizonyítás:

Először azt mutatjuk meg, hogy egy tetszőleges $n \neq = 0$ egész számnak mindig véges sok osztója van. Elegendő azt az esetet vizsgálni, amikor $n$ pozitív. Ha ugyanis $n$ negatív, akkor egyrészt a 15.9. Lemma 1. pontja miatt az ellentettje pozitív lenne, amely a 16.8. Tétel 1. pontja alapján $n$ asszociáltja lenne, azaz pontosan ugyanazok lennének az osztói, mint $n$ -nek.

Az általánosság megsértése nélkül feltehetjük tehát, hogy $0 < n$ . A 17.2. Lemma miatt ekkor $n$ egyetlen osztója sem lehet nagyobb $n$ -nél. Ebből következik, hogy $n$ -nek legfeljebb $n$ darab pozitív osztója lehet. A 16.2. Tétel 8. pontja miatt ekkor azonban ezek ellentettjei is osztók, amelyek a 15.9. Lemma 1. pontja alapján mind negatívak lennének.

Tekintve, hogy a pozitív és negatív egész számok a $0$ -val együtt lefedik a teljes $Z$ halmazt, valamint a 16.2. Tétel 4. pontja miatt $0 ∤ n$ , ezért $n$ -nek biztosan nincs ezeken kívül több osztója, így azok száma biztosan nem több $2 n$ -nél – azaz valóban véges. Ebből azonnal következik, hogy a tételben szereplő $a$ és $b$ egész számok közös osztóinak száma is legfeljebb $2 n$ , azaz szintén véges.

Igaz továbbá, hogy az $1$ minden egész számnak osztója, hiszen ő a $Z$ gyűrű egységeleme, és így a 16.3. Definíció utáni megjegyzés alapján egyúttal egység is. Az $a$ és $b$ közös osztóinak halmaza tehát – azonkívül, hogy véges – nem üres, így biztosan van az elemei között legnagyobb. A legnagyobb közös osztó tehát valóban létezik.

∎

A legnagyobb közös osztó definíciójával azonban van egy kis probléma. Nevezetesen: felhasználtuk hozzá az egész számok gyűrűjének rendezési relációját. Mi azonban szeretnénk ezt a fogalmat tetszőleges integritástartományokra kiterjeszteni. Ugyanakkor nem szeretnénk csak a definíció kedvéért megkövetelni valamiféle rendezési reláció létezését. Ráadásul a 15.4. szakaszban megemlítettük, hogy bizonyos gyűrűk egyáltalán nem, mások pedig akár végtelen sokféleképpen rendezhetők. Ez utóbbi esetben például nem is lenne egyértelmű, hogy melyik rendezés szerinti legnagyobb közös osztóról beszélünk.

17.2A kitüntetett közös osztó

A most következő definícióban általánosítani fogjuk a legnagyobb közös osztó fogalmát, amely így már tetszőleges integritástartományra átvihető lesz rendezési reláció nélkül is.

17.4. Definíció (Kitüntetett közös osztó):

Tegyük fel, hogy $a$ és $b$ egy valamilyen $R$ integritástartomány tetszőleges elemei. Az $a$ és $b$ elemek kitüntetett közös osztója a $d$ elem, ha teljesül az alábbi két tulajdonság:

Teljesülnek a

d ∣ a

és

d ∣ b

oszthatóságok, azaz

d

közös osztó.

Tetszőleges

c

elem esetén ha fennállnak a

c ∣ a

és

c ∣ b

oszthatóságok, akkor fennáll a

c ∣ d

oszthatóság is.

Azaz a kitüntetett közös osztó minden közös osztónak többszöröse. Az $a$ és $b$ elemek kitüntetett közös osztójának jelölése: $(a, b)$ .

♣

Felhívjuk a figyelmet, hogy a legnagyobb közös osztóval ellentétben kitüntetett közös osztóból létezhet több is. Például a 17.1. szakasz elején közölt példában szereplő $24$ és $18$ egész számoknak a $6$ -on kívül a $- 6$ is kitüntetett közös osztója. Szerencsére ez nem fog gondot okozni, mivel az alábbi tétel biztosít egyfajta "egyértelműséget" a kitüntetett közös osztóra.

17.5. Tétel (A kitüntetett közös osztó egyértelműsége):

Ha egy $R$ integritástartományban valamely $a$ és $b$ elemeknek létezik kitüntetett közös osztója, akkor az asszociáltságtól eltekintve egyértelmű.

Azaz egyrészt egy kitüntetett közös osztó bármely asszociáltja is kitüntetett közös osztó, másrészt pedig bármely két kitüntetett közös osztó szükségképpen egymás asszociáltja.

♣

Megjegyzés:

Emiatt a kitüntetett közös osztók közötti azonosságokat leíró kifejezésekben egyenlőségjel helyett általában a $\sim$ szimbólumot fogjuk használni a továbbiakban, ami a 16.6. Definíció szerinti asszociáltságot jelenti. Ezalól csak azok az esetek képeznek kivételt, amikor két kitüntetett közös osztóról kimondottan azt állítjuk, hogy ténylegesen is megegyeznek.

♣

Bizonyítás:

Egyrészt: Tegyük fel, hogy $d_{1}$ kitüntetett közös osztója $a$ -nak és $b$ -nek, valamint $d_{2}$ -re teljesül, hogy $d_{1} \sim d_{2}$ – azaz $d_{1}$ és $d_{2}$ egymás asszociáltjai. Azt kell megmutatni, hogy ekkor $d_{2}$ is kitüntetett közös osztója $a$ -nak és $b$ -nek. Az asszociáltság 16.6. Definíciója alapján $d_{2}$ -nek pontosan ugyanazok az osztói, mint $d_{1}$ -nek. Emiatt, mivel $d_{1}$ -nek osztója az összes közös osztó – hiszen kitüntetett –, ezért $d_{2}$ -nek is, és így ő is kitüntetett.

Másrészt: Most tegyük fel, hogy $d_{1}$ és $d_{2}$ is kitüntetett közös osztója $a$ -nak és $b$ -nek. Azt kell megmutatni, hogy ekkor $d_{1} \sim d_{2}$ – azaz $d_{1}$ és $d_{2}$ egymás asszociáltjai. Mivel $d_{1}$ közös osztó, ezért osztója $d_{2}$ -nek, hiszen $d_{2}$ ugye kitüntetett. Fordítva: mivel $d_{2}$ közös osztó, ezért osztója $d_{1}$ -nek, hiszen $d_{1}$ is kitüntetett. A két kitüntetett közös osztó tehát kölcsönösen osztói egymásnak, és így a 16.9. Tétel értelmében ők egymás asszociáltjai.

∎

A definícióból azonnal következnek az alábbi egyszerű állítások.

17.6. Tétel (A kitüntetett közös osztó tulajdonságai):

Tegyük fel, hogy $a$ és $b$ egy valamilyen $R$ integritástartomány tetszőleges elemei. Ekkor igazak az alábbiak:

(a, b) \sim (b, a)

(a, b) \sim a

akkor és csak akkor, ha

a ∣ b

(a, a) \sim a

(a, 0) \sim a

(0, 0) = 0

♣

Bizonyítás:

1. tulajdonság: Az $a$ és $b$ közös osztóinak halmaza nyilván nem változik, ha a pozíciójukat felcseréljük az $(a, b)$ kifejezésben, így a kitüntetett közös osztók halmaza sem.

2. tulajdonság: Tegyük fel, hogy $a ∣ b$ . Mivel $a ∣ a$ is teljesül a 16.2. Tétel 1. pontja miatt, így $a$ közös osztó. Továbbá ha tekintünk egy tetszőleges $c$ közös osztót, akkor nyilván teljesül a $c ∣ a$ oszthatóság, és így $a$ kitüntetett közös osztó. Visszafelé: $(a, b) \sim a$ azt jelenti, hogy $a$ kitüntetett közös osztó, és így közös osztó, azaz teljesül az $a ∣ b$ oszthatóság.

3. tulajdonság: Tekintve, hogy a 16.2. Tétel 1. pontja alapján minden elem osztója önmagának – beleértve $a$ -t is –, így ez a 2. tulajdonság speciális esete, amikoris $b = a$ .

4. tulajdonság: Tekintve, hogy a 16.2. Tétel 3. pontja alapján minden elem osztója a nullelemnek – beleértve $a$ -t is –, így ez a 2. tulajdonság speciális esete, amikoris $b = 0$ .

5. tulajdonság: Ez a 4. tulajdonság speciális esete, amikoris $a = 0$ . A $\sim$ szimbólum helyetti egyenlőségjel azért indokolt, mivel a 16.8. Tétel 3. pontja alapján a $0$ csak önnmagának asszociáltja.

∎

Jogosan merülhet fel a kérdés az Olvasóban, hogy miért használtuk ugyanazt a jelölést a kitüntetett és a legnagyobb közös osztó esetén, amikor ezek látszólag teljesen különböző fogalmak. Ennek tisztázása érdekében most megmutatjuk, hogy ha két egész számnak egyáltalán létezik kitüntetett közös osztója, akkor az csak a legnagyobb közös osztó valamelyik asszociáltja lehet.

17.7. Tétel:

Tegyük fel, hogy a $d$ egész szám valamely $a$ és $b$ egész számok legnagyobb közös osztója. Tegyük fel továbbá, hogy $a$ -nak és $b$ -nek létezik legalább egy kitüntetett közös osztója, amelyet jelöljünk most $e$ -vel. Ekkor $d$ és $e$ egymás asszociáltjai, és így a 17.5. Tétel értelmében $d$ is kitüntetett közös osztó.

♣

Bizonyítás:

Biztos, hogy $a$ és $b$ közül legalább az egyik nem $0$ , máskülönben a 17.1. Definíció utáni megjegyzés alapján nem létezhetne a $d$ legnagyobb közös osztó. Ebből viszont következik, hogy a feltételezett $e$ kitüntetett közös osztó biztosan nem $0$ , hiszen a 16.2. Tétel 4. pontja miatt a $0$ csak saját magának osztója, és így nem lehetne közös osztója $a$ -nak és $b$ -nek. Így tehát $e$ az egész számok rendezésének trichotómiája miatt vagy pozitív, vagy pedig negatív.

Legyen $f = e$ , ha $e$ pozitív, és $f = - e$ ha $e$ negatív. Ekkor egyrészt a 15.9. Lemma 1. pontja miatt $f$ biztosan pozitív, másrészt pedig $e$ -nek asszociáltja – vagy azért, mert megegyezik vele, vagy pedig a 16.8. Tétel 1. pontja miatt. Ebből viszont a 17.5. Tétel miatt következik, hogy $f$ is kitüntetett közös osztó.

Mivel $f$ közös osztó, és $d$ a legnagyobb közös osztó, ezért egyrészt teljesül az $f \leq d$ reláció. Másrészt mivel $d$ szintén közös osztó, és $f$ kitüntetett, ezért teljesül a $d ∣ f$ oszthatóság is. Ekkor azonban $0 < f$ miatt alkalmazható a 17.2. Lemma, ami alapján teljesül a $d \leq f$ reláció is.

Minthogy $f \leq d$ és $d \leq f$ egyszerre teljesül, ezért a $\leq$ reláció antiszimmetriája miatt $d = f$ . Azaz $d$ valóban asszociáltja a tételben szereplő $e$ kitüntetett közös osztónak, és így a 17.5. Tétel értelmében ő maga is kitüntetett közös osztó.

∎

Ez mind szép és jó, azonban vigyázzunk! Ez a tétel csak annyit garantál, hogy ha valamely egész számoknak létezik kitüntetett közös osztója, akkor e számok legnagyobb közös osztója is rendelkezni fog a 17.4. Definíció szereplő "kitüntetett" tulajdonsággal – azaz, hogy ő többszöröse bármely közös osztónak. A legnagyobb közös osztó a 17.3. Tétel alapján egyetlen esetet leszámítva mindig létezik, ám a kitüntetett közös osztó létezése egyáltalán nem magától értetődő.

Szerencsére a $Z$ gyűrűben valóban mindig létezik a kitüntetett közös osztó, amelyre hamarosan egy úgynevezett "konstruktív bizonyítást" adunk. Ez azt jelenti, hogy a bizonyítás egy meglehetősen hatékony eljárást is fog szolgáltatni a kitüntetett közös osztó kiszámításához. Ez az eljárás az ókorból ered, és "euklidészi algoritmus" néven ismeretes, az alapgondolatát pedig a 17.4. szakaszban fogjuk bemutatni.

Mielőtt azonban erre rátérnénk, vizsgáljuk meg, hogy miért is olyan fontos nekünk a kitüntetett közös osztó létezése egy adott integritástartományban.

17.3A kitüntetett közös osztó jelentősége

Ebben a szakaszban azt fogjuk megmutatni, hogy amennyiben egy $R$ integritástartományban bármely két elemnek létezik kitüntetett közös osztója, akkor $R$ minden felbonthatatlan eleme prímtulajdonságú, következésképp a 16.18. Tétel alapján teljesül a számelmélet alaptételének egyértelműségi része.

Ehhez szükségünk lesz három segédtételre. Először az oszthatósági reláció egy újabb egyszerű tulajdonságát igazoljuk, amely nagyon hasonló a 16.2. Tétel 7. pontjában megfogalmazott állításhoz, ám annál egy kicsit többet mond. Ez hasznunkra lesz a továbbiakban is.

17.8. Tétel:

Legyen $R$ egy tetszőleges kommutatív gyűrű. Ekkor bármely $a$ , $b$ és $c$ elemek esetén az $a ∣ b$ oszthatóságból következik az $a c ∣ b c$ oszthatóság. Ha $R$ nullosztómentes és $c \neq = 0$ , akkor az állítás megfordítása is igaz, vagyis az $a c ∣ b c$ oszthatóságból következik az $a ∣ b$ oszthatóság.

Egyrészt tehát egy kommutatív gyűrűben egy oszthatóság mindkét oldalát szabad megszorozni bármilyen elemmel. Másrészt – ha a gyűrű nullosztómentes is –, akkor az oszthatóság mindkét oldalát szabad egyszerűsíteni bármilyen nemnulla elemmel.

♣

Például az egész számok gyűrűjében teljesül a $6∣18$ oszthatóság, és így a tétel alapján teljesül a $3∣9$ oszthatóság is.

Bizonyítás:

Az, hogy fennáll az $a ∣ b$ oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan $k$ elem, amelyre teljesül az alábbi egyenlet:

ak = b

Az egyenlet mindkét oldalát a $c$ elemmel megszorozva ezt kapjuk:

(ak) c = b c

Mivel azonban a 14.12. Definíció 4. pontja alapján a szorzás asszociatív, valamint – kommutatív gyűrűről lévén szó – a 6. pont alapján kommutatív is, ezért ennek az egyenletnek a baloldala átzárójelezhető és átrendezhető:

(a c) k = b c

Létezik tehát olyan elem, amellyel $a c$ -t megszorozva $b c$ -t kapunk, nevezetesen a $k$ . Ez viszont épp azt jelenti, hogy $a c ∣ b c$ . Vegyük észre, hogy ehhez nem használtuk fel a nullosztómentességet, valamint a $c = 0$ esetre is működik.

A megfordítás bizonyítása: ehhez már fel kell használni a nullosztómentességet is. Ebben az esetben az $a c ∣ b c$ oszthatóságból az előző lépéseket visszafele eljátszva következik az alábbi egyenlet:

(ak) c = b c

Ezt a $c \neq = 0$ feltétel, valamint a nullosztómentesség miatt a 15.4. Tétel alapján egyszerűsíteni lehet $c$ -vel, azaz:

ak = b

Ez viszont a 16.1. Definíció alapján épp azt jelenti, hogy $a ∣ b$ .

∎

Az oszthatóságnak ezt a tulajdonságát most fel fogjuk használni egy, a kitüntetett közös osztóval kapcsolatos fontos összefüggés igazolásához.

17.9. Tétel (A kitüntetett közös osztó kiemelési tulajdonsága):

Legyen $R$ egy tetszőleges integritástartomány, amelyben bármely két elemnek létezik kitüntetett közös osztója. Ekkor tetszőleges $a$ , $b$ és $c$ elemekre érvényes az alábbi összefüggés:

(a c, b c) \sim (a, b) c

Azaz $(a c, b c)$ és $(a, b) c$ mindig egymás asszociáltjai.

♣

Például a $Z$ gyűrűben $(6, 9) \sim 3$ , és így $(18, 27) \sim (6 \cdot 3, 9 \cdot 3) \sim (6, 9) \cdot 3 \sim 9$ .

Bizonyítás:

Ha $c = 0$ , akkor nyilván igaz az állítás, hiszen a 17.6. Tétel 5. pontja miatt egyrészt $(a 0, b 0) = (0, 0) = 0$ , másrészt a 15.1. Tétel 1. pontja miatt $(a, b) 0 = 0$ .

Ha $a = b = 0$ , akkor hasonló okok miatt szintén nyilvánvalóan teljesül a tétel, hiszen egyrészt $(0 c, 0 c) = (0, 0) = 0$ , másrészt $(0, 0) c = 0 c = 0$ .

Az általánosság megsértése nélkül feltehetjük tehát, hogy $c \neq = 0$ , valamint $a$ és $b$ közül legalább az egyik nem $0$ , és emiatt a 16.2. Tétel 4. pontja miatt $(a, b) \neq = 0$ .

Mivel $(a, b)$ közös osztó, ezért teljesülnek az alábbi oszthatóságok:

(a, b) (a, b) ∣ a ∣ b

Ekkor azonban a 17.8. Tétel miatt teljesülnek az alábbi oszthatóságok is:

(a, b) c (a, b) c ∣ a c ∣ b c

Ez viszont azt jelenti, hogy $(a, b) c$ közös osztója $a c$ -nek és $b c$ -nek. Mivel feltételeztük, hogy bármely két elemnek létezik kitüntetett közös osztója, ezért nyilván létezik az $(a c, b c)$ kitüntetett közös osztó is. Ez viszont – kitüntetett lévén – többszöröse bármely más közös osztónak, így $(a, b) c$ -nek is. Azt tehát már tudjuk a tételben szereplő két kifejezésről, hogy teljesül közöttük az alábbi oszthatóság:

(a, b) c ∣ (a c, b c)

Ez viszont a 16.1. Definíció alapján épp azt jelenti, hogy létezik olyan $k$ elem, amelyre teljesül az alábbi egyenlet:

(a, b) c k = (a c, b c)

Azt fogjuk megmutatni, hogy $k$ egység, mivel ebből a 16.10. Tétel miatt már következik az $(a, b) c \sim (a c, b c)$ asszociáltság. Vizsgáljuk hát meg a fenti egyenletet.

Ennek jobboldala $a c$ és $b c$ közös osztója, így az egyenlet baloldala is. Fennállnak tehát az alábbi oszthatóságok:

(a, b) c k (a, b) c k ∣ a c ∣ b c

Mivel a bizonyítás elején az általánosság megsértése nélkül feltehettük, hogy $c \neq = 0$ , így mindkét oszthatóságot egyszerűsíteni lehet vele a 17.8. Tétel miatt. Ekkor ezt kapjuk:

(a, b) k (a, b) k ∣ a ∣ b

Azt kaptuk tehát, hogy $(a, b) k$ közös osztója $a$ -nak és $b$ -nek, és így osztója az ő kitüntetett közös osztójuknak. Azaz:

(a, b) k ∣ (a, b)

Mivel a bizonyítás elején láttuk, hogy $(a, b) \neq = 0$ , ezért ismét alkalmazható a 17.8. Tétel, amely szerint mindkét oszthatóságot egyszerűsíteni lehet $(a, b)$ -vel. Ekkor ezt kapjuk:

k ∣1

A $k$ elem tehát osztója az egységelemnek, emiatt a 16.5. Tétel értelmében valóban egység. Következésképp a 16.10. Tétel miatt $(a, b) c k = (a c, b c)$ -ből következik az $(a, b) c \sim (a c, b c)$ asszociáltság, ahogyan a tétel állítja.

∎

Végül igazoljuk az úgynevezett "euklidészi lemmát". Ez arra ad feltételt, hogy egy elem mely esetekben osztója egy adott szorzat valamelyik tényezőjének, ha egyébként magának a szorzatnak osztója. A 16.4. szakaszban már megemlítettük, hogy ez általánosságban nem igaz. Például $8∣2 \cdot 12$ , ugyanakkor sem a $8∣2$ , sem pedig a $8∣12$ oszthatóság nem teljesül.

A 16.13. Definícióban épp azokat az elemeket neveztük prímeknek, amelyek bármely olyan szorzatra teljesítik ezt a kritériumot, amelynek egyébként osztói. Az euklidészi lemma a prímtulajdonságnál gyengébb feltételt határoz meg erre vonatkozóan. Ez alapján egy elemnek nem feltétlenül kell prímnek lennie ahhoz, hogy egy adott szorzat valamely tényezőjének osztója legyen. Viszont szükséges, hogy a másik tényezőjével a "lehető legkevesebb" közös osztójuk legyen. Először is tisztázzuk, hogy mikor mondjuk két elemről, hogy a "lehető legkevesebb" közös osztójuk van. Ennek az esetnek külön neve is van, amelyet a továbbiakban gyakran fogunk használni.

17.10. Definíció (Relatív prímek):

Legyen $R$ tetszőleges integritástartomány. Amennyiben valamely $a$ és $b$ elemeknek minden közös osztója egység, akkor azt mondjuk, hogy $a$ és $b$ relatív prímek egymáshoz.

♣

Megjegyzés:

Figyelem! Ez a fogalom nem azonos sem a felbonthatatlanok, sem pedig a prímek fogalmával. Abból ugyanis, hogy két elem egymáshoz relatív prím, még nem következik, hogy közülük bármelyik is akár felbonthatatlan, akár prím lenne. Például a $Z$ gyűrűben a $8$ és a $9$ egész számoknak a $- 1$ -en és az $1$ -en – tehát a gyűrű egységein – kívül nincs más közös osztójuk, így relatív prímek. Ám egyikük sem felbonthatatlan, hiszen a $8 = 2 \cdot 4$ és a $9 = 3 \cdot 3$ nemtriviális felbontások. És mivel nem felbonthatatlanok, ezért a 16.14. Tétel miatt nem is prímek.

Megjegyezzük még, hogy $a$ és $b$ relatív prímsége esetén nem csak az teljesül, hogy minden közös osztó egység, hanem az is, hogy minden egység közös osztó, hiszen az egységek minden elemnek osztói, így nyilván $a$ -nak is és $b$ -nek is. Másként fogalmazva relatív prímség esetén pontosan az egységek a közös osztók. Ezért a relatív prímséget gyakran az alábbi asszociáltsággal jelöljük:

(a, b) \sim 1

♣

Ezek után az euklidészi lemma a következőképpen fogalmazható meg.

17.11. Tétel (Euklidészi lemma):

Legyen $R$ egy tetszőleges integritástartomány, amelyben bármely két elemnek létezik kitüntetett közös osztója. Ekkor ha valamely $a$ , $b$ és $c$ elemek esetén teljesül az $a ∣ b c$ oszthatóság, valamint $a$ és $b$ relatív prímek, akkor teljesül az $a ∣ c$ oszthatóság is.

♣

Például a $Z$ gyűrűben $4∣9 \cdot 8$ , és mivel $4$ és $9$ relatív prímek – azaz $(4, 9) \sim 1$ –, ezért $4∣8$ .

Bizonyítás:

A tétel szövegének megfelelően tegyük fel, hogy teljesül az $a ∣ b c$ oszthatóság, valamint $a$ és $b$ relatív prímek, azaz a 17.10. Definíció utáni megjegyzés miatt $(a, b) \sim 1$ .

Mivel $R$ egységelemes, ezért a 16.2. Tétel 1. pontja miatt teljesül az $a ∣ a$ oszthatóság, és így ugyanezen tétel 7. pontja miatt az $a ∣ a c$ oszthatóság is. Továbbá a tétel szövegéből tudjuk, hogy $a ∣ b c$ , tehát az $a$ elem közös osztója $a c$ -nek és $b c$ -nek, így osztója ezek kitüntetett közös osztójának. Azaz:

a ∣ (a c, b c)

A 17.9. Tétel miatt azonban teljesül az $(a c, b c) \sim (a, b) c$ asszociáltság, így:

a ∣ (a, b) c

Végül, mivel $(a, b) \sim 1$ – tehát $(a, b)$ egység –, ezért teljesül az $(a, b) c \sim c$ asszociáltság is, azaz valóban $a ∣ c$ , ahogy a tétel állítja.

∎

Az euklidészi lemma felhasználásával mostmár igazolhatjuk a kitüntetett közös osztó létezésének jelentőségét a számelmélet alaptétele kapcsán.

17.12. Tétel:

Legyen $R$ egy tetszőleges integritástartomány. Ha bármely két elemnek létezik kitüntetett közös osztója, akkor $R$ -ben minden felbonthatatlan elem prímtulajdonságú.

♣

Bizonyítás:

Legyen $p$ egy tetszőleges felbonthatatlan elem $R$ -ben. Azt kell megmutatni, hogy prímtulajdonságú, azaz hogy ha valamilyen $a$ és $b$ elemek esetén teljesül a $p ∣ ab$ oszthatóság, de $p ∤ a$ , akkor szükségképpen teljesül a $p ∣ b$ oszthatóság is.

Tegyük hát fel, hogy $p ∤ a$ . Mivel azt mondtuk, hogy bármely két elemnek létezik kitüntetett közös osztója $R$ -ben, ezért nyilván $p$ -nek is és $a$ -nak is létezik a $(p, a)$ kitüntetett közös osztója. Mivel $(p, a)$ közös osztó, ezért nyilván teljesül a $(p, a) ∣ p$ oszthatóság. De mivel $p$ felbonthatatlan, ezért a 16.11. Definíció miatt az alábbi két eset lehetséges:

(p, a) (p, a) \sim p \sim 1

Azaz $(p, a)$ vagy egység, vagy pedig $p$ valamely asszociáltja. Ez utóbbi azonban lehetetlen, hiszen ekkor – lévén, hogy $(p, a)$ közös osztó – teljesülne a $(p, a) ∣ a$ oszthatóság, és így $(p, a) \sim p$ miatt teljesülne a $p ∣ a$ oszthatóság is, ami ellentmond a feltételezésünknek, miszerint $p ∤ a$ .

Azt kaptuk tehát, hogy $(p, a)$ csak egység lehet, azaz $p$ és $a$ relatív prímek. Ha tehát teljesül a $p ∣ ab$ oszthatóság, akkor ebből a 17.11. Tétel miatt következik a $p ∣ b$ oszthatóság is. Azaz $p$ valóban prímtulajdonságú, ahogy a tétel állítja.

∎

Mostmár tehát tudjuk, hogy ha egy integritástartományban bármely két elemnek létezik a kitüntetett közös osztója, akkor minden felbonthatatlan elem prímtulajdonságú. Ebből viszont a 16.18. Tétel miatt következik, hogy teljesül a számelmélet alaptételének egyértelműségi állítása.

A 17.2. szakasz végén a 17.7. Tételben már láttuk, hogy a kriptográfiai szempontból számunkra fontos $Z$ gyűrűben ha egy elempárnak létezik kitüntetett közös osztója, akkor a legnagyobb közös osztójuk is kitüntetett. Megemlítettük ugyanakkor, hogy ez a tétel még nem garantálja azt, hogy bármely két egész számnak létezik a kitüntetett közös osztója. Ennek igazolására most megismerkedünk egy igen fontos számelméleti algoritmussal.

17.4Az euklidészi algoritmus alapgondolata

Az euklidészi algoritmus az egyik legősibb, igen gyakran használt számelméleti algoritmus. Nevét az ókori görög matematikusról, Euklidészről kapta, aki Kr.e. 300 körül írta le az Elemek című művében. Ez egy rendkívül hatékony módszert határoz meg két egész szám kitüntetett közös osztójának előállítására.

Az általános iskolából nyilván mindenki emlékszik arra a módszerre, amely a két számnak a számelmélet alaptétele szerinti prímtényezős felbontásából indul ki. Mivel a 16.8. Tétel 1. pontja alapján egy egész szám és az ellentettje ugyanúgy viselkedik oszthatóság szempontjából, ezért elegendő csak a pozitív egészekre és a pozitív prímtényezőkre szorítkozni. Ha tehát rendelkezésünkre áll a két szám prímtényezős felbontása, akkor a keresett kitüntetett közös osztó prímtényezős felbontása pontosan azokból a prímtényezőkből fog állni, amelyek mindkét szám felbontásában szerepelnek. Így például a $18$ és a $45$ kitüntetett közös osztója $9$ , mivel a két eredeti szám felbontása:

1845 = 2 \cdot 3 \cdot 3 = 3 \cdot 3 \cdot 5

A két felbontás közös prímtényezői adják a kitüntetett közös osztót, azaz $3 \cdot 3 = 9$ .

Ezzel a módszerrel – bár helyes – két alapvető probléma van. Egyrészt azt még nem bizonyítottuk, hogy a $Z$ gyűrűben valóban teljesül a számelmélet alaptétele, így azt elméletben még nem használhatnánk. Másrészt viszont – és ez egy jóval nagyobb, gyakorlati probléma – ehhez a módszerhez szükségünk van a két szám prímtényezős felbontására. Ennek meghatározására jelenlegi tudásunk szerint azonban nem létezik hatékony eljárás, habár ez még bizonyításra vár. Hogy mit értünk "hatékony eljárás" alatt, arról a 6., 7. és 8. fejezetekben volt szó részletesen, így azt nem ismételnénk meg. Azonban saját bőrünkön is érzékelhetjük a problémát, ha megpróbáljuk megtalálni például a $12439705049$ és a $15828713003$ kitüntetett közös osztóját ezzel a módszerrel.

Az említett "iskolás" módszert követve persze elkezdhetjük a prímtényezőkre bontást. Hamar beletörik azonban a bicskánk, mivel ezt a két számot szándékosan nagy prímtényezőkből állítottam össze. Nevezetesen:

1243970504915828713003 = 2797 \cdot 2999 \cdot 1483 = 2999 \cdot 1483 \cdot 3559

Innen persze a közös prímtényezők kiválogatása, és a kitüntetett közös osztó kiszámítása már egyszerű:

2999 \cdot 1483 = 4447517

Mondhatnánk, hogy számítógéppel pillanatok alatt prímtényezőire bonthatjuk ezt a két számot. Ez minden bizonnyal így is van az ilyen nagyságrendű számok esetén. A problémát az okozza, hogy a bemeneti számjegyek számának növelésével a prímtényezők kiszámításához szükséges idő nagyon meredeken kezd emelkedni. Olyannyira, hogy például egy több száz számjegyből álló szám prímtényezőire bontása még a világ összes számítógépének is beláthatatlanul sok ideig tartana. A kriptográfiában használt RSA-eljárás algoritmikus biztonsága épp a prímtényezős felbontás feladatának e roppant nehézségén alapszik.

Az euklidészi algoritmus ezzel szemben egy olyan eljárást ad két egész szám kitüntetett közös osztójának kiszámítására, amelyhez nincs szükség a két szám prímtényezőire. Az algoritmus alapötlete az oszthatóság tulajdonságairól szóló a 16.2. Tétel 6. és 7. pontjainak egy egyszerű következményén alapul. Nézzük is meg ezt az összefüggést.

17.13. Tétel:

Legyen $R$ egy tetszőleges integritástartomány. Ekkor ha valamely $a$ és $b$ elemeknek létezik az $(a, b)$ kitüntetett közös osztója, akkor tetszőleges $k$ elem esetén érvényes az alábbi összefüggés:

(a, b) \sim (b, a - k b)

♣

Bizonyítás:

Mivel $(a, b)$ közös osztó, ezért teljesülnek az alábbi oszthatóságok:

(a, b) (a, b) ∣ a ∣ b

A második oszthatóság jobboldala a 16.2. Tétel 7. pontja miatt tetszőleges $k$ elemmel megszorozható:

(a, b) ∣ k b

Az $(a, b)$ tehát osztója $a$ -nak és $k b$ -nek, így ugyanezen tétel 6. pontja miatt osztója a különbségüknek is:

(a, b) ∣ a - k b

Azt kaptuk, hogy az $(a, b)$ elem $a$ -n és $b$ -n kívül közös osztója $b$ -nek és $a - k b$ -nek is. Már csak azt kell megmutatni, hogy ennek az elempárnak szintén kitüntetett közös osztója, azaz bármely más közös osztónak többszöröse. Tegyük fel például, hogy $d$ egy ilyen közös osztó, azaz:

d d ∣ b ∣ a - k b

Az első oszthatóság jobboldalát a 16.2. Tétel 7. pontja miatt $k$ -val megszorozhatjuk:

d ∣ k b

A $d$ elem tehát osztója $a - k b$ -nek és $k b$ -nek, így ugyanezen tétel 6. pontja miatt osztója az összegüknek is, amelyben a $k b$ és $- k b$ tagok kiejtik egymást:

d ∣ a - k b + k b

Azt kaptuk tehát, hogy $d$ közös osztója $a$ -nak és $b$ -nek, emiatt osztója az ő kitüntetett közös osztójuknak, azaz $(a, b)$ -nek is. Igenám, de fentebb már láttuk, hogy $(a, b)$ nem csak az $a$ és $b$ elemek közös osztója, hanem a $b$ és $a - k b$ elemeknek is. Így ő végülis ezeknek az elemeknek is kitüntetett közös osztója, és így a két kitüntetett közös osztó a 17.5. Tétel alapján egymás asszociáltjai, azaz valóban:

(a, b) \sim (b, a - k b)

∎

Nézzük is meg, hogy miképpen tudunk profitálni ebből az imént kapott $(a, b) \sim (b, a - k b)$ összefüggésből. Egyelőre tegyük fel, hogy $Z$ gyűrűben vagyunk, mind $a$ , mind pedig $b$ pozitív egészek, valamint $a > b$ . Később majd általánosítani fogjuk az algoritmust tetszőleges esetre, sőt tetszőleges integritástartományra, most azonban a működés alapelvének megértése a cél.

**17.1. ábra:** Maradékos osztás szemléltetése rudakkal

Ha belegondolunk, tulajdonképpen az történt, hogy az $a$ pozitív egész számot sikerült kifejeznünk "valahányszor $b$ , meg egy kis maradék" alakban, ahol $k_{1}$ -gyel jelöltük a "valahányszort", $r_{1}$ -gyel pedig a "maradékot":

a = k_{1} b + r_{1}

Ráadásul – és ez kulcsfontosságú – az $r_{1}$ maradékra teljesül, hogy legalább $0$ , viszont szigorúan kisebb $b$ -nél:

0 \leq r_{1} < b

**17.2. ábra:** Maradékos osztás (második lépés)

Ekkor tulajdonképpen a $b$ -t sikerült kifejeznünk "valahányszor $r_{1}$ , meg egy kis maradék" alakban. Ezt az eljárást folytatva a következő sorozathoz jutunk:

a b r_{1} r_{2} = k_{1} b + r_{1} = k_{2} r_{1} + r_{2} = k_{3} r_{2} + r_{3} = k_{4} r_{3} + r_{4} ⋮

Mindeközben pedig a lépések során kapott maradékok így alakulnak:

0 \leq \dots < r_{4} < r_{3} < r_{2} < r_{1} < b

Továbbá a keresett kitüntetett közös osztóra igaz lesz az alábbi:

(a, b) \sim (b, r_{1}) \sim (r_{1}, r_{2}) \sim (r_{2}, r_{3}) \sim \dots

A maradékok tehát egyre kisebbek és kisebbek lesznek, miközben mindegyikről tudjuk, hogy $0$ -nál semmiképpen sem lehetnek kisebbek. Ezért érezhetően véges számú lépés után valamelyik maradék előbb-utóbb biztosan $0$ lesz. A 17.5. szakaszban megmutatjuk, hogy ez valóban a 11.1. Definíció szerinti Peano-axiómarendszer egy következménye. Egyelőre tegyük fel, hogy ez tényleg így van, és az utolsó nemnulla maradék $r_{n}$ . Ekkor befejezhetjük az eljárást, és mivel $r_{n} \neq = 0$ , továbbá a 16.2. Tétel 3. pontja miatt $r_{n} ∣0$ ugye teljesül, így alkalmazhatjuk a 17.6. Tétel 4. pontját. Ez alapján gyakorlatilag megkaptuk a keresett kitüntetett közös osztót, ami nem más, mint $r_{n}$ :

(a, b) \sim (r_{n}, 0) \sim r_{n}

Maradékos osztásnak nevezzük azt a műveletet, melynek során kiszámítjuk, hogy egy szám egy másikkal osztva mennyi maradékot ad. A maradékos osztás – itt nem részletezett digitális áramköri okok miatt – egy számítógép számára rendkívül hatékonyan elvégezhető. Ráadásul megmutatható – habár erre most nem térünk ki –, hogy a fenti algoritmushoz szükséges maradékos osztások száma a kisebbik bemenet számjegyeinek a számával egyenesen arányos. Ez azt jelenti, hogy még az több száz jegyű számok tartományában is nagyságrendileg pár száz maradékos osztásból megkaphatjuk a kitüntetett közös osztót. Egy átlagos számítógép számára ez egy szemvillanás alatt elvégezhető. Ezzel szemben a prímtényezős módszer az idők végezetéig is eltartana ebben a számtartományban.

E gyorsaság demonstrálására nézzük is meg, hogy mennyire gyorsan kapjuk meg a szakasz elején ismertetett példában szereplő $12439705049$ és $15828713003$ számok kitüntetett közös osztóját. A maradékos osztás műveletét könnyedén el tudjuk végezni a legegyszerűbb kalkulátorral is. Ezt általában a mod – vagy hasonló – feliratú nyomógombbal érhetjük el, és egyetlen lépésben képezni fogja nekünk a képződő maradékot. Például a $8 mod 3$ műveletet elvégezve az eredmény $2$ , mivel a $8$ -at $3$ -mal osztva a maradék $2$ .

Az euklideszi algoritmust a két bemeneti számunkon lefuttatva az alábbi lépéseken keresztül jutunk el a keresett kitüntetett közös osztóig:

\sim \sim \sim \sim \sim \sim \sim (15828713003, 12439705049) \sim (12439705049, 3389007954) \sim (3389007954, 2272681187) \sim (2272681187, 1116326767) \sim (1116326767, 40027653) \sim (40027653, 35580136) \sim (35580136, 4447517) \sim (4447517, 0)

A keresett kitüntetett közös osztó tehát $4447517$ . Valóban ugyanazt az eredményt kaptuk, mint a prímtényezős felbontást használó módszerrel, csak épp nem sok ezer – vagy épp millió – osztáspróbával, hanem mindössze hét maradékos osztással. Úgy gondolom ez eléggé meggyőző, amikor hatékonyságról beszélünk.

17.5A végtelen leszállás módszere

Hamarosan azt fogjuk megvizsgálni, hogy az imént tanult eljárást hogyan tudjuk olyan integritástartományokra is kiterjeszteni, amelyek nem feltétlenül számokat tartalmaznak. Ehhez először megismerkedünk a "végtelen leszállás" néven ismeretes indirekt bizonyítási módszerrel. Ezzel fogjuk tudni igazolni, hogy az euklidészi algoritmus véges számú lépés után valóban befejeződik. A módszer a természetes számok $N$ halmazának egy fontos tulajdonságán alapul. Ám mielőtt ezt ismertetnénk, először egy segédtételt fogunk bizonyítani.

17.14. Lemma:

Legyenek $n$ és $x$ a természetes számok $N$ halmazának tetszőleges elemei, és jelölje $s (n)$ az $n$ természetes szám 11.1. Definíció szerinti rákövetkezőjét. Ekkor tetszőleges $x$ természetes szám esetén teljesülnek az alábbiak:

n < x \leq s (n)

, akkor

x = s (n)

n \leq x < s (n)

, akkor

x = n

♣

Bizonyítás:

Kezdjük az 1. állítás igazolásával. Mivel $x \leq s (n)$ , ezért az alábbi két eset lehetséges:

n < x n < x = s (n) < s (n)

Tegyük fel indirekt, hogy a tétel állításával szemben a második eset áll fenn, azaz:

n < x < s (n)

Ekkor az egész számok rendezésének a 15.18. Tételben szereplő definíciója alapján léteznek olyan $k_{1} \neq = 0$ és $k_{2} \neq = 0$ természetes számok, hogy teljesül az alábbi:

= x n + k_{1} + k_{2} = s (n)

A 11.4. Definíció 2. pontja alapján ez így írható:

n + k_{1} + k_{2} = = s (n) n + s (0)

Az egyenlet mindkét oldalát egyszerűsíthetjük $n$ -nel a 12.18. Lemma miatt:

k_{1} + k_{2} = s (0)

Mivel $k_{1} \neq = 0$ , ezért a 11.1. Definíció 3. pontja miatt létezik olyan $k_{0}$ természetes szám, amelynek épp $k_{1}$ a rákövetkezője, azaz $s (k_{0}) = k_{1}$ . Ekkor az egyenlet így írható:

= k_{1} s (k_{0}) + k_{2} = s (0)

Ismét a 11.4. Definíció 2. pontja, valamint az összeadás kommutativitása miatt ez így is írható:

= s (k_{0}) + k_{2} s (k_{0} + k_{2}) = s (0)

A 11.1. Definíció 2. pontja alapján ekkor:

k_{0} + k_{2} = 0

Végül alkalmazhatjuk a 12.19. Lemmát, mely szerint ez csak akkor lehetséges, ha teljesülnek az alábbiak:

k_{0} k_{2} = 0 = 0

Ez viszont ellentmond annak, hogy $k_{2} \neq = 0$ , vagyis az indirekt feltevésünk hibás volt, és így kizárólag csak az alábbi eset fordulhat elő, ahogy a tétel állítja:

n < x = s (n)

Most igazoljuk a 2. állítást. Mivel $n \leq x$ , ezért az alábbi két eset lehetséges:

n = x n < x < s (n) < s (n)

Tegyük fel indirekt, hogy a tétel állításával szemben a második eset áll fenn, azaz:

n < x < s (n)

Erről viszont az 1. állítás kapcsán már láttuk, hogy lehetetlen.

∎

Ezt a segédtételt felhasználva most megmutatjuk a természetes számok $N$ halmazának a már említett fontos tulajdonságát.

17.15. Tétel (A természetes számok minimumtétele):

Ha $P$ a természetes számok $N$ halmazának tetszőleges nemüres részhalmaza, akkor $P$ -nek van minimuma a 15.18. Tétel szerinti $\leq$ relációra nézve. Minimum alatt egy olyan $P$ -beli $p$ elem létezését értjük, amelyre tetszőleges, szintén $P$ -beli $q$ elem esetén teljesül a $p \leq q$ reláció.

♣

Megjegyzés:

Eszerint tehát sehogyan sem lehet kiválogatni véges vagy akár végtelen sok természetes számot úgy, hogy ezek között ne lenne legkisebb. Vegyük észre, hogy ez az egész számok $Z$ halmazára például nem érvényes, mivel bármilyen egész számnál létezik nála kisebb egész szám, hiszen itt a számegyenes mindkét irányban végtelen. De bizonyos számkörökben még csak erre sincs feltétlenül szükség. Habár a "törtszámokat" még nem építettük fel az axiómák segítségével, de intuitív módon érezhető, hogy bármely két törtszám között végtelen sok további törtszám létezik. Következésképp ebben a számkörben a számegyenes semmilyen véges hosszú szakaszára nem igaz a fenti tétel.

Az tehát, hogy a természetes számokra mégis igaz, egyáltalán nem magától értetődő, akármennyire is annak látszik. Szerencsénkre, ez ugyanis lehetőséget teremt egy újfajta bizonyítási módszerre, amelyet végtelen leszállásnak nevezünk. Ezt Pierre de Fermat fejlesztette ki a 17. században, és számos fontos eredményhez jutott ennek segítségével. A módszer tulajdonképpen egy indirekt érvelés, melynek során megmutatjuk, hogy ha a szóban forgó állítás hamis, akkor elő lehet állítani egy olyan természetes számokból álló sorozatot, amelynek nincs minimuma. Ez ugye ellentmondana a minimumtételnek, a bizonyítandó állítás tehát nem lehet hamis, következésképp igaznak kell lennie.

♣

Bizonyítás:

**17.3. ábra:** P és Q halmazok elhelyezkedése

Egyelőre még nem tudjuk, hogy mely természetes számok tartoznak $P$ -be, és melyek $Q$ -ba. Az viszont bizonyos, hogy ha egy $q$ természetes szám $Q$ -ba tartozik, akkor nem tartozhat egyúttal $P$ -be is, máskülönben teljesülne a $q < q$ reláció. Ez viszont lehetetlen, hiszen a 15.18. Tétel alapján ekkor léteznie kéne egy olyan $k \neq = 0$ természetes számnak, amelyre $q + k = q$ teljesül. Mindkét oldalból $q$ -t kivonva $k = 0$ adódna, ami ellentmond $k \neq = 0$ -nak.

Azt kell megmutatnunk, hogy valójában minden természetes szám $Q$ -ba tartozik, azaz $Q = N$ , hiszen ebből következne, hogy – indirekt feltételezésünkkel ellentétben – $P$ csak az üres halmaz lehet. Ezt teljes indukcióval fogjuk bizonyítani, amelyre a Peano-axiómarendszer 11.1. Definíciójának 4. pontja ad lehetőséget.

Kezdjük a $0$ -val. Tegyük fel indirekt, hogy a $0$ nincs benne $Q$ -ban, azaz létezik olyan $P$ -beli $p$ elem, amelyre nem teljesül a $0 < p$ reláció. Ekkor viszont az egész számok rendezésének trichotómiája miatt szükségképpen teljesülne a $p \leq 0$ reláció. Ez a 15.18. Tétel miatt azt jelentené, hogy létezik olyan $k$ természetes szám, amelyre $p + k = 0$ . A 12.19. Lemma alapján azonban a természetes számok körében egy összeg csak úgy lehet $0$ , ha mindkét tagja $0$ , és így $p = 0$ lenne.

Abból az indirekt feltételezésből tehát, miszerint a $0$ nincs benne $Q$ -ban az következik, hogy benne van $P$ -ben. Ez viszont lehetetlen, hiszen bármely $n$ természetes számra teljesül $0 \leq n$ reláció, és így $P$ -nek a $0$ minimuma lenne, márpedig $P$ -ről a bizonyítás elején feltettük, hogy nincs minimuma. A $0$ -nak tehát szükségképpen $Q$ -ban kell lennie.

Tegyük most fel, hogy egy valamilyen $n$ természetes számról már tudjuk, hogy $Q$ -ban van – mint például a $0$ , amiről ezt az imént láttunk be. Azt szeretnénk megmutatni, hogy ekkor $s (n)$ – azaz $n$ -nek a 11.1. Definíció szerinti rákövetkezője – is benne van a $Q$ -ban.

Ezt ismét indirekt módon bizonyítjuk. Tegyük ezért fel az állítás ellenkezőjét, azaz hogy $s (n)$ nincs benne a $Q$ halmazban. Egyrészt ez azt jelentené, hogy létezne olyan $P$ -beli $p$ elem, amelyre nem teljesül az $s (n) < p$ reláció. Ismét a trichotómia miatt ekkor szükségképpen teljesülne a $p \leq s (n)$ reláció. Másrészt, mivel ugye $n$ az indukciós feltétel miatt benne van a $Q$ halmazban, így teljesül az $n < p$ reláció is. Azaz összefoglalva:

n < p \leq s (n)

Ebből viszont a 17.14. Lemma miatt az következik, hogy $s (n)$ benne van a $P$ halmazban, mivel:

p = s (n)

Egyrészt tehát azt kaptuk, hogy ha $s (n)$ nem lenne $Q$ -ban, akkor szükségképpen $P$ -ben kellene lennie. Másrészt viszont az iménti gondolatmenetet bármely $P$ -beli $x$ elemre megismételve azt kapnánk, hogy $x \leq s (n)$ csak úgy teljesülhet, ha $x = s (n)$ . Így tehát a $P$ halmaznak mégiscsak lenne minimuma, nevezetesen $s (n)$ . Tehát hibás volt az indirekt feltételezésünk, ezért ha $n$ benne van $Q$ -ban, akkor az ő rákövetkezője is szükségképpen $Q$ -ban kell legyen.

Ezzel kész a teljes indukció, hiszen láttuk, hogy a $0$ benne van $Q$ -ban, így az iménti gondolatmenet alapján az ő rákövetkezője is, majd annak a rákövetkezője, és így tovább a végtelenségig. A 11.1. Definíció 4. pontja alapján így minden természetes számot lefedünk, azaz $Q = N$ . Ekkor $P$ csak az üres halmaz lehet, azaz valóban nem létezik olyan nemüres részhalmaza $N$ -nek, amelynek nincs minimuma – épp ahogyan a tétel állítja.

∎

A fenti tételen kívül szükségünk lesz még egy állításra, amely a $\leq$ -nél szigorúbb $<$ reláció tranzitivitását garantálja. A $\leq$ reláció tranzitivitását már igazoltuk a 12.17. Tételben. Nem meglepő módon ez a tulajdonság a $<$ relációra is teljesül, így most ezt mutatjuk meg.

17.16. Tétel:

Tetszőleges $a$ , $b$ és $c$ egész számok esetén ha $a \leq b$ és $b \leq c$ teljesül, valamint az ennél szigorúbb $a < b$ vagy $b < c$ közül legalább az egyik teljesül, akkor $a < c$ is teljesül.

♣

Bizonyítás:

Az $a \leq b$ és $b \leq c$ relációk teljesülése, valamint az $a < b$ vagy $b < c$ relációk közül legalább az egyiknek a teljesülése a 15.18. Tétel miatt azt jelenti, hogy léteznek $n$ és $k$ természetes számok, amelyek közül legalább az egyik nem $0$ , és amelyekre igazak az alábbi egyenletek:

a + n b + k = b = c

A második egyenletbe $b$ helyére az első egyenlet baloldalát behelyettesíthetjük:

= b a + n + k = c

Az $n + k$ összegről viszont tudjuk, hogy mindkét tagja természetes szám, melyek közül legalább az egyik nem $0$ . Márpedig a 12.19. Lemma kimondja, hogy ebben az esetben maga az összeg sem $0$ . Azaz létezik olyan nem $0$ természetes szám – nevezetesen az $n + k$ –, amelyet $a$ -hoz adva $c$ -t kapunk. Ez a 15.18. Tétel miatt épp azt jelenti, hogy:

a < c

∎

Ezek után a fejezet hátralévő részében a 17.15. Tétel utáni megjegyzésben ismertetett végtelen leszállás módszerét fogjuk felhasználni annak megmutatásához, hogy a számelmélet alaptétele teljesül gyűrűk egy speciális osztályában, az úgynevezett "euklidészi gyűrűkben".

17.6Euklidészi gyűrűk

Az euklidészi algoritmus alapgondolatának ismertetésekor a 17.4. szakaszban feltételeztük, hogy az $a$ és $b$ bemenet egy-egy pozitív egész szám, amelyeknek tehát a kitüntetett közös osztóját keressük. Az alapötletet a 17.13. Tétel szolgáltatta, mely szerint ha $a$ és $b$ között el tudjuk végezni a maradékos osztást, akkor az $(a, b)$ kitüntetett közös osztó – amennyiben létezik – asszociáltja lesz a $(b, r_{1})$ kitüntetett közös osztónak, ahol $r_{1}$ a maradékos osztás során képződő maradék. Ezek után a $b$ és $r_{1}$ között kell maradékos osztást végezni, így ha a képződő maradék $r_{2}$ , akkor a $(b, r_{1})$ kitüntetett közös osztó – amennyiben létezik – asszociáltja lesz az $(r_{1}, r_{2})$ kitüntetett közös osztónak.

Ezt az eljárást tovább folytatjuk mindaddig, míg valamelyik lépésben a képződő maradék $0$ nem lesz. Ha az utolsó nemnulla maradék $r_{n}$ , akkor végülis azt kaptuk, hogy az $(a, b)$ kitüntetett közös osztó létezik, mivel ő $(r_{n}, 0)$ asszociáltja, ami viszont a 17.6. Tétel 4. pontja alapján $r_{n}$ asszociáltja.

Látható tehát, hogy az $(a, b)$ kitüntetett közös osztó létezése azon múlik, hogy véges számú lépés után biztosan $0$ lesz-e a képződő maradék. Ezt fentebb csak feltételeztük, most azonban a végtelen leszállás módszerével könnyedén adódik. Ugyanis valamely $x$ és $y$ elemek maradékos osztásánál ugyanis fontos követelmény volt, hogy az $x$ elemet úgy tudjuk kifejezni "valahányszor $y$ , meg egy kis maradék" alakban, hogy a maradék mindig szigorúan kisebb legyen, mint $y$ .

Tegyük fel indirekt, hogy a maradékos osztást mindig el tudjuk végezni ebben az értelemben, ám az eljárás ennek ellenére nem ér véget véges számú lépés után. Ebben az esetben az

r_{1} > r_{2} > r_{3} > \dots

sorozat a $>$ reláció 17.16. Tétel szerinti tranzitivitása miatt a természetes számoknak egy olyan részhalmaza lenne, amelynek nem lenne minimuma. Ez viszont a 17.15. Tétel alapján ellentmondás. Ha tehát a maradékos osztást el tudjuk végezni minden esetben, akkor az euklideszi algoritmus biztosan lefut véges számú lépés után, és kiszámítja a keresett kitüntetett közös osztót.

Igenám, csakhogy mi tetszőleges integritástartományra szeretnénk kiterjeszteni ezt az algoritmust. Márpedig például az egész számok gyűrűjére nem érvényes a minimumtétel. Más integritástartományok pedig még csak nem is feltétlenül számokból, hanem egyéb objektumokból állhatnak. Sőt, még az is előfordulhat, hogy a "kisebb-nagyobb" relációnak nincs is értelme egy $R$ integritástartományon, mert mondjuk $R$ még csak nem is rendezhető.

Vegyük azonban észre, hogy minket nem konkrétan a képződő maradékok és a közöttük lévő valamilyen módon értelmezett "kisebb-nagyobb" viszonyok érdekelnek. Ehelyett ezeknek a maradékoknak a – bizonyos absztrakt értelemben vett – "nagysága" az, ami igazán fontos. Ha valahogy sikerülne az adott gyűrű elemeinek "nagyságát" természetes számokkal "mérni" úgy, hogy az euklidészi algoritmus lépései során keletkező maradékok "nagysága" egy szigorúan csökkenő számsorozatot alkosson, akkor nyert ügyünk lenne.

A most következő definíció precízen megfogalmazza, hogy pontosan mit értünk egy ilyen jellegű absztrakt "mérhetőség" alatt, és külön nevet ad az olyan integritástartományoknak, amelyek ebben az értelemben "mérhetőek".

17.17. Definíció (Euklidészi gyűrűk):

Legyen $R$ tetszőleges integritástartomány, és jelöljük $R$ nemnulla elemeinek halmazát $R_{\neq = 0}$ -rel, míg $R$ nullelemét $0_{R}$ -rel. Legyen továbbá értelmezve egy

f : R_{\neq = 0} \to N

függvény úgy, hogy teljesüljenek az alábbi követelmények:

Tetszőleges

R

-beli

a

és

b \neq = 0_{R}

elemekhez található olyan

k

hányados és

r

maradék

R

-ben, hogy

a = k b + r

Az alábbiak közül legalább az egyik teljesül:

r f (r) = 0_{R} < f (b)

Ekkor $f$ -et az $R$ integritástartományon értelmezett euklidészi függvénynek, az $a$ és $b$ elemekhez tartozó $k$ és $r$ elemek előállítását pedig euklidészi osztásnak vagy maradékos osztásnak nevezzük. Amennyiben $R$ -hez létezik ilyen tulajdonságú $f$ függvény, úgy $R$ -et euklidészi gyűrűnek nevezzük.

♣

Megjegyzés:

Az euklidészi gyűrű fogalmának bevezetése mögött tehát az a motiváció, hogy az euklidészi algoritmus ne csak a nemnegatív egész számok halmazán működhessen, hanem azt az $f$ euklidészi függvény segítségével ki lehessen terjeszteni integritástartományok lehetőleg minél szélesebb körére is.

Ez azáltal válik lehetségessé, hogy a maradékokhoz az $f$ függvény természetes számokat rendel hozzá, miközben olyan követelményeknek tesz eleget, amely követelmények biztosítják azt, hogy az eljárás véges számú lépés után garantáltan befejeződjön. Ezt a 17.18. Tételben fogjuk precízen kimondani és bizonyítani.

Fontos megjegyezni még, hogy egy euklidészi gyűrűnek, mint algebrai struktúrának nem része a konkrét euklidészi függvény. A definíció szerint elegendő, ha létezik ilyen függvény az adott gyűrűhöz. Sőt, egy euklidészi gyűrűhöz sok esetben több euklidészi függvény is értelmezhető.

Általában azonban igen nehéz annak eldöntése, hogy egy $R$ integritástartomány euklidészi gyűrű-e vagy sem. Természetesen ha találunk egy olyan függvényt, amely euklidészi, akkor $R$ nyilván euklidészi gyűrű. Ha azonban nem találunk ilyen függvényt, akkor ez még önmagában nem elég a nemleges válaszhoz. Ehhez azt kéne igazolni, hogy ilyen függvény egyáltalán nem is létezik az adott $R$ -hez. Ez számos nyitott kérdéshez és sejtéshez vezet, melyek a mai napig bizonyítatlanul várják az utókor ötleteit.

♣

Most azt fogjuk megvizsgálni, hogy miért olyan fontosak az euklidészi gyűrűk a számelmélet alaptétele szempontjából. Például azért, mert – ahogyan azt a most következő tételben ki is mondjuk – ezekben bármely két elemnek létezik kitüntetett közös osztója, és emiatt a 17.12. és a 16.18. Tételek értelmében teljesül bennük a számelmélet alaptételének egyértelműségi állítása.

17.18. Tétel:

Legyen $R$ tetszőleges euklidészi gyűrű. Ekkor $R$ -ben bármely két elemnek létezik kitüntetett közös osztója.

♣

Bizonyítás:

Legyen $a$ és $b$ az $R$ két tetszőleges eleme, és jelöljük $0_{R}$ -rel a nullelemet. Az általánosság megsértése nélkül feltételezhetjük, hogy $a \neq = 0_{R}$ és $b \neq = 0_{R}$ , minden más esetben ugyanis a 17.6. Tételből azonnal megkapjuk a keresett kitüntetett közös osztót.

Mivel $R$ euklidészi gyűrű, ezért a 17.17. Definíció 1. pontja szerint $a$ és $b$ között elvégezhető a maradékos osztás egy valamilyen $f$ euklidészi függvény szerint. Azaz $R$ -ben létezik $k_{1}$ hányados és $r_{1}$ maradék $R$ -ben úgy, hogy teljesüljön az alábbi egyenlet:

a = k_{1} b + r_{1}

Ekkor a 17.17. Definíció 2. pontja szerint az alábbiak közül legalább az egyik teljesül:

r_{1} f (r_{1}) = 0_{R} < f (b)

Ha $r_{1} = 0_{R}$ , akkor a 17.13. Tétel, valamint a 17.6. Tétel 4. pontja alapján $b$ lesz a kitüntetett közös osztó, hiszen

(a, b) \sim (b, = a - k_{1} b r_{1}) \sim (b, = r_{1} 0_{R}) \sim b

Ha viszont $r_{1} \neq = 0_{R}$ , akkor egyrészt a 17.17. Definíció 2. pontja értelmében szükségképpen teljesül az alábbi szigorú egyenlőtlenség:

f (b) > f (r_{1})

Másrészt pedig a 17.17. Definíció 1. pontja alapján ezúttal $b$ és $r_{1}$ között ismét elvégezhető az $f$ szerinti maradékos osztás.

Ezt az eljárást mindaddig folytatjuk, amíg meg nem kapjuk a nullelemet maradékként valamelyik lépésben. Ekkor – ismételten a 17.13. Tétel, és a 17.6. Tétel 4. pontja miatt – az utolsó olyan maradék lesz a kitüntetett közös osztó, amely nem a nullelem.

Az eljárás garantáltan véget fog érni véges számú lépés után, máskülönben a maradékos osztások során előállna az alábbi, természetes számokból álló végtelen sorozat:

f (b) > f (r_{1}) > f (r_{2}) > f (r_{3}) > \dots

Ez $N$ -nek egy olyan részhalmaza lenne, amelynek a 17.16. Tétel miatt nincs minimuma, ami viszont a 17.15. Tétel alapján lehetetlen. Így az euklidészi algoritmus garantáltan leáll véges számú lépés után, és előállítja az $a$ és $b$ kitüntetett közös osztóját, amely tehát az utolsó nemnulla maradék lesz.

∎

A 17.8. szakaszban meg fogjuk mutatni, hogy ennél több is igaz. Nevezetesen: nemcsak a számelmélet alaptételének egyértelműségi állítása, hanem a felbontások létezése is garantált euklidészi gyűrűkben. Először azonban azt igazoljuk, hogy az egész számok gyűrűje is euklidészi.

17.7Euklidészi függvény a $Z$ gyűrűn

A 15.18. Tételben definiált teljes rendezés segítségével most egy függvényt fogunk értelmezni a $Z$ halmazon, majd megmutatjuk, hogy az egy euklidészi függvény. Nézzük először a kérdéses függvényt.

17.19. Definíció (Az egész számok abszolútértéke):

Definiáljunk egy $f : Z \to N$ függvényt a következőképpen:

f (a) = {a - a ha a \geq 0 ha a < 0

Ekkor az $f (a)$ természetes számot az $a$ egész szám abszolút értékének, az $f$ függvényt pedig abszolútérték-függvénynek nevezzük. Az $a$ egész szám abszolút értékének jelölése: $∣ a ∣$ .

♣

Amennyiben tehát az egész számokat a mindkét irányban végtelen számegyenesen ábrázoljuk, akkor ez a függvény intuitív módon a $0$ egész számtól való távolságot méri ezen az egyenesen. Ez alapján például az $5$ és a $- 5$ egész számok egyaránt $5$ távolságra vannak a $0$ -tól, azaz

∣5∣ = ∣ - 5∣ = 5

**17.4. ábra:** Abszolútérték a számegyenesen

Az abszolútérték-függvénynek a következő tétel miatt van jelentősége számunkra.

17.20. Tétel:

A 17.19. Definíció szerinti $f (a) = ∣ a ∣$ abszolútérték-függvény egy euklidészi függvény a $Z$ gyűrűn, azaz $Z$ euklidészi gyűrű.

♣

Megjegyzés:

Ha egészen precízek akarunk lenni, akkor valójában nem pontosan a tételben szereplő $f$ függvény, hanem annak a nemnulla egész számokat tartalmazó halmazra történő megszorítása euklidészi. A 17.17. Definícióban található jelölést alkalmazva jelöljük ezt a halmazt $Z_{\neq = 0}$ -val. Ekkor valójában az alábbi $f^{'} : Z_{\neq = 0} \to N$ függvényről van szó:

f^{'} (a) = {a - a ha a > 0 ha a < 0

Ez tehát pusztán abban különbözik a 17.19. Definícióban szereplő abszolútérték-függvénytől, hogy nincs értelmezve a $0$ -ra. Ám a tétel bizonyításában ezt nem használjuk ki, így az egyszerűség kedvéért ettől az apróságtól eltekintünk.

♣

Bizonyítás:

A 17.17. Definíció 1. pontja alapján egyrészt azt kell megmutatni, hogy tetszőleges $a$ és $b \neq = 0$ egész számokhoz léteznek $k$ és $r$ egész számok úgy, hogy teljesül az alábbi egyenlet:

a = k b + r

Másrészt pedig a 17.17. Definíció 2. pontja alapján azt is meg kell mutatni, hogy emellett legalább az egyik teljesül az alábbiak közül:

r ∣ r ∣ = 0 < ∣ b ∣

Mivel a $Z$ gyűrűben vagyunk, és a 17.19. Definíció alapján $r = 0$ ekvivalens $∣ r ∣ = 0$ -val, ezért ez utóbbi feltétel az alábbi rövidebb alakban is leírható:

0 \leq ∣ r ∣ < ∣ b ∣

A bizonyítás további részében ezt az alakot fogjuk használni.

A bizonyítás konstruktív lesz, azaz $k$ és $r$ létezését azáltal igazoljuk, hogy egy eljárást mutatunk a kiszámításukra. Ez az eljárás a gyakorlatban nem lenne túl hatékony, ám nekünk a bizonyításhoz épp elegendő lesz. Továbbá ki fogjuk használni, hogy a 15.18. Tételben definiált $\leq$ reláció teljesíti a 15.11. Definícióban megfogalmazott rendezési axiómákat.

Először szorítkozzunk arra az esetre, amikor egyik bemeneti számunk sem negatív, azaz teljesülnek az alábbiak:

00 \leq a < b

Az eljárás lényege, hogy a hányadost és a maradékot próbálgatással keressük meg az alábbi lépéseket végrehajtva:

a a a a a = 0 b + = r_{0} a = 1 b + = r_{1} (a - b) = 2 b + = r_{2} (a - 2 b) ⋮ = k_{i} b + = r_{i} (a - k_{i} b) = k_{i + 1} b + = r_{i + 1} (a - k_{i + 1} b) ⋮

Itt az $i$ -edik lépésben kipróbált hányados-jelöltet $k_{i}$ -vel, míg az ugyanebben a lépésben kipróbált maradék-jelöltet $r_{i}$ -vel jelöltük.

Nyilván mindegyik egyenlet teljesül, hiszen minden lépésben tulajdonképpen annyi történik, hogy a jobboldalhoz hozzá is adunk, és ki is vonunk $b$ -t. Csak épp a hozzáadást a hányados-jelölt $1$ -gyel történő megnövelésével, míg a kivonást a maradék-jelölt $b$ -vel történő csökkentésével érjük el. Emiatt az $i$ -edik lépésből az $i + 1$ -edik lépésbe így jutunk:

k_{i + 1} r_{i + 1} = k_{i} + 1 = r_{i} - b

Az eljárás megkezdésekor a kiinduló állapot: $k_{0} = 0$ és $r_{0} = a$ .

Az eljárást mindaddig nem fejezzük be, ameddig az aktuális $r_{i}$ maradék-jelöltre már igaz nem lesz, hogy $r_{i} < b$ . A befejezés előtti lépésekben tehát még $b \leq r_{i}$ , és ezekben az esetekben, mivel a 15.11. Definíció szerinti 1. rendezési axióma alapján a $\leq$ reláció kompatibilis az összeadással, ezért teljesül az alábbi:

0 \leq = r_{i + 1} r_{i} - b

Azaz egyrészt minden újabb lépésben folyamatosan nemnegatív maradék-jelölteket kapunk, azok tehát mindannyian természetes számok.

Másrészt, mivel $r_{i + 1} = r_{i} - b$ , ezért $r_{i + 1} + b = r_{i}$ , de ugye a bizonyítás elején egyelőre kikötöttük, hogy $0 < b$ , emiatt:

r_{i + 1} < r_{i}

Azaz minden újabb lépésben szigorúan kisebb maradék-jelölteket kapunk, mint az azt megelőző lépésben.

Az eljárás emiatt nyilván véges számú lépés után garantáltan befejeződik, máskülönben egy végtelen leszálló természetes számokból álló sorozatot kapnánk, ami a 17.15. Tétel miatt ellentmondás. Az utolsó lépésben tehát az előbbiek alapján kaptunk egy olyan $k$ hányadost és $r$ maradékot, amelyekre teljesül, hogy

a 0 = k b + r \leq r < b

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor $0 < b$ – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0 \leq = r ∣ r ∣ < = b ∣ b ∣

Azaz ebben az esetben teljesülnek a euklidészi függvényre vonatkozó követelmények.

Eddig tehát azt az esetet fedtük le, amikoris $0 \leq a$ és $0 < b$ . Ennek az eredménynek az általánosítása a többi előjel-kombinációra már egyszerű. Az alábbiakban ennek technikai részleteit ismertetjük.

0 \leq a \overset{e}{ˊ} s b < 0

Ekkor a 15.9. Lemma 1. pontja miatt $0 < (- b)$ , tehát a fenti eljárás szóról szóra megismételhető, csak ekkor $b$ helyét $(- b)$ veszi át. Az utolsó lépésben így kapunk egy olyan $k$ hányadost és $r$ maradékot, amelyekre teljesülnek az alábbiak:

a 0 = k (- b) + r \leq r < (- b)

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor $0 < (- b)$ – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0 \leq = r ∣ r ∣ < = (- b) ∣ - b ∣

Nekünk azonban $a$ -nak $(- b)$ helyett a $b$ -vel történő maradékos osztására, és ezért a $∣ - b ∣$ helyett a $∣ b ∣$ abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 3. pontja, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a 0 = (- k) b + r \leq ∣ r ∣ < = ∣ - b ∣ ∣ b ∣

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a \leq 0 \overset{e}{ˊ} s 0 < b

Ekkor a 15.9. Lemma 1. pontja miatt $0 \leq (- a)$ , tehát a fenti eljárás szóról szóra megismételhető, csak ekkor $a$ helyét $(- a)$ veszi át. Az utolsó lépésben így kapunk egy olyan $k$ hányadost és $r$ maradékot, amelyekre teljesülnek az alábbiak:

(- a) 0 = k b + r \leq r < b

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor $0 < b$ – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0 \leq = r ∣ r ∣ < = b ∣ b ∣

Nekünk azonban $(- a)$ helyett $a$ -nak a $b$ -vel történő maradékos osztására van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5. és 3. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a 0 = (- k) b + (- r) \leq = ∣ r ∣ ∣ - r ∣ < ∣ b ∣

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a \leq 0 \overset{e}{ˊ} s b < 0

Ekkor a 15.9. Lemma 1. pontja miatt $0 < (- b)$ és $0 \leq (- a)$ , tehát a fenti eljárás szóról szóra megismételhető, csak ekkor $a$ helyét $(- a)$ és $b$ helyét $(- b)$ veszi át. Az utolsó lépésben így kapunk egy olyan $k$ hányadost és $r$ maradékot, amelyekre teljesülnek az alábbiak:

(- a) 0 = k (- b) + r \leq r < (- b)

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor $0 < (- b)$ – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0 \leq = r ∣ r ∣ < = (- b) ∣ - b ∣

Nekünk azonban $(- a)$ helyett $a$ -nak a $(- b)$ helyett $b$ -vel történő maradékos osztására, és ezért a $∣ - b ∣$ helyett a $∣ b ∣$ abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5., 3. és 4. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a 0 = k b + (- r) \leq = ∣ r ∣ ∣ - r ∣ < = ∣ - b ∣ ∣ b ∣

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

Ezzel már minden esetet lefedtünk, azaz tetszőleges $a$ és $b \neq = 0$ elemek között elvégezhető az abszolútérték-függvény szerinti maradékos osztás. Ez a függvény tehát valóban egy euklidészi függvény a $Z$ gyűrűn.

∎

Most tehát már tudjuk, hogy az egész számok gyűrűje egy euklidészi gyűrű, és így – mint ahogyan azt a 17.6. szakaszban megemlítettük – teljesül benne a számelmélet alaptételének egyértelműségi állítása.

17.8A számelmélet alaptétele euklidészi gyűrűkben

A számelmélet alaptételének egyértelműségi állítása pusztán annyit állít, hogy ha egy elemnek létezik felbontása, akkor az a tényezők sorrendjétől és asszociáltságtól eltekintve egyértelmű a 16.16. Definíció szerinti értelemben. Semmit nem mond azonban arról, hogy bármely elemnek egyáltalán létezik-e ilyen felbontása. Most azt fogjuk igazolni, hogy euklidészi gyűrűkben a felbontás létezése is garantált. Ehhez a kulcsot a következő tétel fogja jelenteni.

17.21. Tétel:

Legyen $R$ tetszőleges euklidészi gyűrű, és jelöljük $R$ nullelemét $0_{R}$ -rel. Ekkor $R$ -hez létezik olyan $g$ euklidészi függvény, amely a 17.17. Definícióban megfogalmazott követelményeken kívül tetszőleges $a$ és $b \neq = 0_{R}$ elemekre teljesíti az alábbi monotonitási tulajdonságot is:

g (a) \leq g (ab)

Ilyenkor $g$ -t monoton euklidészi függvénynek nevezzük – amikor tehát a nemnulla elemekkel való szorzás nem csökkenti az euklidészi függvény értékét.

♣

Bizonyítás:

Legyen $f$ egy tetszőleges euklidészi függvény $R$ -hez. Ilyen ugye létezik, mivel $R$ euklidészi gyűrű. A bizonyítás konstruktív lesz, azaz $f$ felhasználásával definiálni fogunk egy olyan $g$ függvényt, amely maga is euklidészi függvény, de ezen felül teljesíti a tételben szereplő monotonitási tulajdonságot is.

Tegyük fel, hogy valamilyen tetszőleges $k$ elemre szeretnénk kiszámítani a $g (k)$ függvényértéket. Ehhez először képezzük a $k$ elem összes nemnulla többszörösének az $f$ függvény szerinti értékét, azaz minden $R$ -beli $x \neq = 0$ elemre kiszámítjuk az $f (k x)$ természetes számokat. Ezután válasszuk $g (k)$ értékének ezek közül a legkisebbet, amely ugye a 17.15. Tétel miatt biztosan létezik. Más szavakkal a $g (k)$ függvényérték legyen az eredeti $f$ függvénynek a $k$ elem nemnulla többszörösein felvett minimuma.

A $g$ függvény iménti definíciója alapján tehát a tételben szereplő $a$ és $b \neq = 0_{R}$ elemek esetén létezik olyan $c \neq = 0_{R}$ elem, amelyre $g (ab) = f (ab c)$ teljesül. Nevezetesen épp az a $c$ elem, amelyre az $f (ab c)$ felveszi a minimumát.

Mivel ugyanakkor az $ab c$ szorzat az $ab$ elemen kívül az $a$ elemnek is egy nemnulla többszöröse, ezért ismét a $g$ függvény fenti definíciója miatt:

g (a) \leq f (ab c)

De mivel azt mondtuk, hogy $g (ab) = f (ab c)$ , ezért valóban fennáll a tételben szereplő egyenlőtlenség:

g (a) \leq = f (ab c) g (ab)

Már csak annyit kell igazolni, hogy maga $g$ is euklidészi függvény $R$ -hez. Legyen $b \neq = 0_{R}$ egy tetszőleges nemnulla $R$ -beli elem, valamint válasszuk ki $b$ -nek egy olyan nemnulla többszörösét, amelyre az eredeti $f$ euklidészi függvény épp a minimumát veszi fel. Ez ugye biztosan létezik, mint azt már láttuk fentebb. Azaz válasszunk ki egy olyan $c \neq = 0_{R}$ elemet, amelyre

g (b) = f (b c)

Minthogy $b \neq = 0_{R}$ és $c \neq = 0_{R}$ ezért a nullosztómentesség miatt $b c \neq = 0_{R}$ . Azaz tetszőleges $a$ elem maradékosan elosztható a $b c$ elemmel az eredeti $f$ euklidészi függvény szerint. Ez azt jelenti, hogy létezik olyan $k$ hányados és $r$ maradék, amelyekre teljesül az alábbi egyenlet:

a = k \cdot (b c) + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r f (r) = 0_{R} < f (b c)

Az általánosság megsértése nélkül feltehetjük, hogy $r \neq = 0_{R}$ , és így az $f$ -re vonatkozó egyenlőtlenség áll fenn, máskülönben a további lépésekben amúgysem nyernénk semmilyen további információt $g$ -ről.

Egyrészt a $g$ függvény definíciója miatt $g (r) \leq f (r)$ , hiszen $r$ a 16.2. Tétel 1. pontja alapján önmagának is többszöröse. Másrészt viszont a $c$ elemet épp úgy választottuk ki, hogy $f (b c) = g (b)$ teljesüljön. Létezik tehát olyan hányados – nevezetesen $k c$ – és maradék – nevezetesen $r$ –, amelyre teljesülnek az alábbiak:

a \leq f (r) g (r) = (k c) \cdot b + r < = f (b c) g (b)

Azaz tetszőleges $a$ elem tetszőleges $b \neq = 0_{R}$ elemmel maradékosan elosztható a $g$ függvény szerint is, így $g$ valóban egy euklidészi függvény.

∎

Az iménti tételben szereplő monotonitási tulajdonság tehát azt jelenti, hogy egy ilyen euklidészi függvény tetszőleges elem bármely nemnulla többszörösére legalább akkora "nagyságot" fog "mérni", mint magára az elemre. A most következő tétel arra ad választ, hogy mely esetekben teljesül egyenlőség a két oldal között, és mely esetekben nem.

17.22. Tétel:

Legyen $R$ tetszőleges euklidészi gyűrű, $g$ pedig egy monoton euklidészi függvény $R$ -hez, amelyre tehát teljesül a 17.21. Tétel szerinti monotonitási tulajdonság. Jelöljük $R$ nullelemét $0_{R}$ -rel.

Ekkor tetszőleges $a \neq = 0_{R}$ és $b \neq = 0_{R}$ elemek esetén

g (a) = g (ab)

akkor és csak akkor teljesül, ha $b$ egység.

Minden más esetben szigorú egyenlőtlenség áll fenn, azaz

g (a) < g (ab)

♣

Bizonyítás:

Ha $b$ egység, akkor a 16.5. Tétel értelmében osztója az egységelemnek. Létezik tehát olyan $c$ elem, amelyre $b c = 1$ teljesül. Mivel $c \neq = 0_{R}$ – máskülönben a 15.1. Tétel 1. pontja alapján a $b c$ szorzat a nullelem lenne –, ezért a $g$ euklidészi függvény monotonitási tulajdonsága miatt:

g (ab) \leq g (a = 1 b c) = g (a)

Ugyanakkor szintén a monotonitási tulajdonság miatt:

g (a) \leq g (ab)

Mindkét irányban fennáll tehát a $\leq$ reláció, így az antiszimmetria miatt szükségképpen

g (a) = g (ab)

Visszafelé: Tegyük fel indirekt, hogy $b$ nem egység, ám ennek ellenére

g (a) = g (ab)

Mivel $a$ -ról és $b$ -ről a tétel szövege alapján tudjuk, hogy egyik sem a nullelem, ezért a nullosztómentesség miatt az $ab$ szorzat sem lehet az. Emiatt az $a$ elem maradékosan elosztható az $ab$ elemmel a $g$ euklidészi függvény szerint. Azaz létezik olyan $k$ hányados és $r$ maradék, hogy teljesül az alábbi egyenlet

a = k ab + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r g (r) = 0_{R} < g (ab)

Az általánosság megsértése nélkül feltehetjük, hogy $r \neq = 0_{R}$ , és így a $g$ -re vonatkozó egyenlőtlenség áll fenn, máskülönben a további lépésekben amúgysem nyernénk semmilyen további információt $g$ -ről.

Az egyenlet mindkét oldalából $k ab$ -t levonva ezt kapjuk:

a - k ab = r

A baloldalt a disztributivitási szabályok miatt így írhatjuk át:

a \cdot (1 - k b) = r

Mivel $b$ -ről indirekt azt mondtuk, hogy nem egység, ezért a 16.5. Tétel miatt nem lehet osztója az egységelemnek. Emiatt $k b \neq = 1$ , és így $1 - k b$ biztosan nem a nullelem. Minthogy a tétel szöveg alapján $a$ sem a nullelem, ezért a nullosztómentesség miatt $r$ az $a$ -nak egy nemnulla többszöröse – egész konkrétan $1 - k b$ -szerese –, és így a $g$ euklidészi függvény monotonitási tulajdonsága miatt teljesül a következő egyenlőtlenség:

g (a) \leq g (= a \cdot (1 - k b) r)

Ugyanakkor indirekt feltételeztük, hogy $g (a) = g (ab)$ , így a fentebbi maradékos osztásból kapott $g (r) < g (ab)$ szigorú egyenlőtlenségből

g (r) < g (a)

következik.

Ez ellentmondás, hiszen $g (r)$ nem lehet egyszerre legalább akkora, mint $g (a)$ , és határozottan kisebb is nála. Az indirekt feltételezésünk hibás volt, azaz a $g (a) = g (ab)$ egyenlőség nem állhat fenn, amennyiben $b$ nem egység.

∎

Az iménti két tételt felhasználva már könnyedén beláthatjuk ennek a résznek a főtételét, amely az euklidészi gyűrűk legfontosabb tulajdonságát mondja ki.

17.23. Tétel:

Minden euklidészi gyűrűben – és így a 17.20. Tétel miatt az egész számok gyűrűjében is – teljesül a számelmélet alaptétele.

♣

Bizonyítás:

Legyen $R$ valamilyen euklidészi gyűrű. A 17.18. Tétel alapján $R$ -ben bármely két elemnek létezik kitüntetett közös osztója. Így a 17.12. Tétel miatt minden felbonthatatlan elem prím. Ebből viszont a 16.18. Tétel szerint következik a számelmélet alaptételének egyértelműségi állítása. Ha tehát valamely elemnek egyáltalán létezik felbontása, akkor az sorrendtől és asszociáltságtól eltekintve egyértelmű.

Így már csak azt kell megmutatni, hogy bármely nemnulla és nem egység elemnek ténylegesen létezik felbontása. Tegyük fel, hogy $g$ egy olyan euklidészi függvény, amely eleget tesz a 17.21. Tételben szereplő monotonitási tulajdonságnak is. Ilyen euklidészi függvény ugyanezen tétel miatt garantáltan létezik. A bizonyításhoz a $g$ norma értékkészletén, azaz a természetes számok $N$ halmazán fogunk teljes indukciót alkalmazni.

**17.5. ábra:** A teljes indukció vázlata

Először is indukciós feltételként feltesszük, hogy valamilyen $n$ -re már igaz az állítás, azaz bármely $n$ -nél nemnagyobb $g$ -értékű nemnulla és nem egység elemnek létezik prímtényezős felbontása. Ezt az elemhalmazt a fenti ábrán $A_{n}$ -nel jelöltük. Azt kell megmutatnunk, hogy ekkor az $A_{n + 1}$ halmaz elemeire is teljesülni fog az állítás. Tegyük fel, hogy $a$ egy tetszőleges $A_{n + 1}$ -beli elem. Feltételezhetjük, hogy nincs benne $A_{n}$ -ben, hiszen máskülönben az indukciós feltétel miatt róla már amúgyis tudnánk, hogy létezik prímtényezős felbontása. Így tehát:

g (a) = n + 1

Ha $a$ felbonthatatlan, akkor az ő prímtényezős felbontása alatt a 16.16. Definíció alapján önmagát, mint "egytényezős szorzatot" értjük, így az nyilván létezik. Feltételezhetjük tehát, hogy $a$ nem felbonthatatlan, azaz felírható $a = b c$ alakban úgy, hogy $b$ és $c$ közül egyik sem egység.

Ekkor azonban a $g$ euklidészi függvényre a 17.22. Tétel miatt fennállnak az alábbi szigorú egyenlőtlenségek, hiszen $a$ nem egységszerese sem $b$ -nek, sem pedig $c$ -nek:

g (b) g (c) < g (a) < g (a)

Ez viszont $g (a) = n + 1$ miatt azt jelenti, hogy

g (b) g (c) \leq n \leq n

Az indukciós feltétel alapján azonban emiatt $b$ -nek és $c$ -nek létezik prímtényezős felbontása, hiszen mindketten benne vannak az $A_{n}$ halmazban. Így ha az $a = b c$ szorzatba $b$ és $c$ helyére beírjuk e két felbontást, akkor épp $a$ -nak a felbontását kapjuk.

Eddig tehát azt bizonyítottuk, hogy ha valamilyen $n$ -re az $A_{n}$ halmaz minden elemének létezik felbontása, akkor ez igaz lesz az őt tartalmazó $A_{n + 1}$ halmaz elemeire is. Már csak el kell indítani az indukciós "dominósor" ledöntését, azaz meg kell mutatni, hogy $n = 0$ -ra valóban teljesül a tétel állítása.

Az $n = 0$ esethez az $A_{0}$ halmaz tartozik, amely tehát azokat a nemnulla és nem egység elemeket tartalmazza, amelyeknek a $g$ -értéke legfeljebb $0$ . Tegyük fel indirekt, hogy ezek között mégis létezik egy olyan $x$ elem, amelynek nem létezik prímtényezős felbontása. Minthogy az $A_{0}$ halmaz definíciója miatt $g (x) \leq 0$ , ugyanakkor $g (x)$ csak nemnegatív szám lehet, mivel a $g$ függvény $N$ -be képez, ezért ez azt jelenti, hogy valójában

g (x) = 0

Jelöljük $1_{R}$ -rel az $R$ egységelemét, és végezzük el a $g$ euklidészi függvény szerinti maradékos osztást $1_{R}$ és $x$ között. Ez megtehető, hiszen $R$ euklidészi gyűrű. Létezik tehát olyan $k$ hányados és $r$ maradék, hogy teljesül az alábbi egyenlet:

1_{R} = k x + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r g (r) = 0_{R} < = 0 g (x)

Az egyenlőtlenség nem teljesülhet, hiszen – mint már említettük – a $g$ függvény $N$ -be képez, és emiatt semmilyen $g$ -érték nem lehet $0$ -nál kisebb. Ezért tehát szükségképpen $r = 0_{R}$ , azaz

1_{R} = k x + = r 0_{R}

Tehát valójában azt kaptuk, hogy $x$ osztója az egységelemnek, azaz a 16.5. Tétel alapján egység. Ez viszont ellentmondás, mivel azt mondtuk, hogy az $A_{0}$ halmazban csak nemnulla és nem egység elemek vannak.

Azt kaptuk tehát, hogy az $A_{0}$ halmazra igaz lesz a tétel állítása. Ekkor azonban a már bizonyított indukciós lépés miatt igaz lesz $A_{1}$ -re is, majd emiatt $A_{2}$ -re is, és így tovább, egészen a végtelenségig. Minthogy a $g$ euklidészi függvény összes lehetséges értékét lefedtük, ezért biztosan nem hagytunk ki egyetlen nemnulla és nem egység elemet sem a buliból. Mindegyikre igaz tehát a prímtényezős felbontás létezése, és így a számelmélet alaptétele.

∎

Ez a tétel egy elégséges feltételt biztosít ahhoz, hogy egy integritástartományban teljesüljön a számelmélet alaptétele. Megjegyezzük azonban, hogy ez a feltétel nem szükséges az alaptételhez. Léteznek olyan integritástartományok is, amelyekben semmilyen értelemben nem végezhető el a maradékos osztás, és így nem euklidészi gyűrűk, ám mégis teljesül bennük a számelmélet alaptétele.

Ebben a fejezetben megismerkedtünk a kitüntetett közös osztó fogalmával, és az euklidészi algoritmussal, amely azt képes hihetetlen sebességgel kiszámítani. A kitüntetett közös osztó azért volt nagyon fontos számunkra, mert annak létezéséből már következik a számelmélet alaptételének egyértelműségi állítása. Ezért általánosságban is megvizsgáltuk, mi kell ahhoz, hogy az euklidészi algoritmus valamilyen integritástartományon működhessen. Ezzel eljutottunk a maradékos osztás és az euklidészi gyűrű fogalmához, és megmutattuk, hogy az ilyen gyűrűkben mindig teljesül a számelmélet alaptételének mindkét állítása. Ezen túlmenően igazoltuk, hogy az egész számok gyűrűje is euklidészi gyűrű – például az abszolútérték-függvényre, mint euklidészi függvényre nézve.

A 9. fejezetben a Diffie-Hellman kulcscsere protokoll kapcsán már felületesen megismerkedtünk az úgynevezett óra-, vagy becsületesebb nevén moduláris aritmetikával. Ez szintén egy fontos összetevője az aszimmetrikus kulcsú titkosítási eljárásoknak, ezért a következő fejezetben ezt a témakört újra elővesszük. Ám ezt ezúttal a gyűrűk absztrakciós szintjén fogjuk megtenni, melynek keretében megismerkedünk az úgynevezett maradékosztálygyűrűkkel és ideálokkal.

17.1A legnagyobb közös osztó

17.1. Definíció (Legnagyobb közös osztó):

Megjegyzés:

17.2. Lemma:

Bizonyítás:

17.3. Tétel:

Bizonyítás:

17.2A kitüntetett közös osztó

17.4. Definíció (Kitüntetett közös osztó):

17.5. Tétel (A kitüntetett közös osztó egyértelműsége):

Megjegyzés:

Bizonyítás:

17.6. Tétel (A kitüntetett közös osztó tulajdonságai):

Bizonyítás:

17.7. Tétel:

Bizonyítás:

17.3A kitüntetett közös osztó jelentősége

17.8. Tétel:

Bizonyítás:

17.9. Tétel (A kitüntetett közös osztó kiemelési tulajdonsága):

Bizonyítás:

17.10. Definíció (Relatív prímek):

Megjegyzés:

17.11. Tétel (Euklidészi lemma):

Bizonyítás:

17.12. Tétel:

Bizonyítás:

17.4Az euklidészi algoritmus alapgondolata

17.13. Tétel:

Bizonyítás:

17.5A végtelen leszállás módszere

17.14. Lemma:

Bizonyítás:

17.15. Tétel (A természetes számok minimumtétele):

Megjegyzés:

Bizonyítás:

17.16. Tétel:

Bizonyítás:

17.6Euklidészi gyűrűk

17.17. Definíció (Euklidészi gyűrűk):

Megjegyzés:

17.18. Tétel:

Bizonyítás:

17.7Euklidészi függvény a Z gyűrűn

17.19. Definíció (Az egész számok abszolútértéke):

17.20. Tétel:

Megjegyzés:

Bizonyítás:

17.8A számelmélet alaptétele euklidészi gyűrűkben

17.21. Tétel:

Bizonyítás:

17.22. Tétel:

Bizonyítás:

17.23. Tétel:

Bizonyítás:

17.7Euklidészi függvény a $Z$ gyűrűn