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.
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.
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.
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.
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.
A definícióból azonnal következnek az alábbi egyszerű állítások.
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.
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.
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.
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.
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.
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.
Ezek után az euklidészi lemma a következőképpen fogalmazható meg.
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.
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.
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:
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 12\space 439\space 705\space 049 és a 15\space 828\space 713\space 003 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:
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ű:
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.
Nézzük is meg, hogy miképpen tudunk profitálni ebből az imént kapott (a,b)\sim (b, a-kb) ö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\gt 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.
Rajzoljunk fel két "rudat", amelyek méretarányosan tükrözik e két szám nagyságát. Kezdjünk el lenyesegetni b-nek megfelelő hosszúságú darabokat az a-t jelölő rúdból mindaddig, amíg a maradék kisebb nem lesz, mint b, vagy akár el nem tűnik teljesen. Ezt a folyamatot láthatjuk a 17.1. ábrán, amelyen a maradék rudacska hosszának megfelelő számot r_1-gyel jelöltük.
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":
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:
A fenti egyenletből az r_1 maradékot ki tudjuk fejezni r_1=a-k_1b alakban. Ez azért baromi jó, mivel az imént bizonyított 17.13. Tétel alapján a (b,r_1) kitüntetett közös osztó egyúttal az a és b elemek kitüntetett közös osztója is lesz. Az eredeti számok kitüntetett közös osztójának kiszámítását tehát sikerült két kisebb szám kitüntetett közös osztójának kiszámítására visszavezetni. Most folytassuk ugyanezt a lenyesegetős eljárást a b és r_1 számokkal. Ez látható a 17.2. ábrán kinagyítva.
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:
Mindeközben pedig a lépések során kapott maradékok így alakulnak:
Továbbá a keresett kitüntetett közös osztóra igaz lesz az alábbi:
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:
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ő 12\space 439\space 705\space 049 és 15\space 828\space 713\space 003 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\space \text{mod}\space 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:
A keresett kitüntetett közös osztó tehát 4\space 447\space 517. 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.
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.
Bizonyítás:
Tegyük fel indirekt, hogy P egy olyan galád nemüres részhalmaza \N-nek, amelynek nincs minimuma. Jelöljük ezenkívül Q-val \N-nek azt a részhalmazát, amely pontosan azokat a természetes számokat tartalmazza, amelyek kisebbek P minden eleménél. Azaz egyrészt minden Q-beli q elemre teljesül, hogy minden P-beli p elem esetén q\lt p, másrészt semmilyen Q halmazon kívüli elemre nem tejesül ez a tulajdonság. Ez a szituáció látható a 17.3. ábrán.
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\lt 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\lt 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)\lt 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\lt p reláció is. Azaz összefoglalva:
Ebből viszont a 17.14. Lemma miatt az következik, hogy s(n) benne van a P halmazban, mivel:
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 \lt 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 \lt relációra is teljesül, így most ezt mutatjuk meg.
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 egy x és egy y elem maradékos osztásánál 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
sorozat a \gt 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".
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.
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.
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
Ezt szemlélteti a 17.4. ábra.
Az abszolútérték-függvénynek a következő tétel miatt van jelentősége számunkra.
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.
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.
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.
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.
Ennek során minden n természetes számra megmutatjuk, hogy R összes olyan nemnulla és nem egység elemének létezik prímtényezős felbontása, amelynek a g euklidészi függvény szerinti értéke legfeljebb n. A 17.5. ábrán az R elemeinek azon A_0, A_1, A_2, ... részhalmazai láthatók, amelyek az első néhány természetes számhoz tartoznak ebben az értelemben. Az elemeket pontokkal jelöltük, valamint ábrázoltuk a g által hozzájuk rendelt értékeket is.
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:
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=bc 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:
Ez viszont g(a)=n+1 miatt azt jelenti, hogy
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=bc 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
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:
Továbbá az alábbiak közül legalább az egyik teljesül:
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
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.