Episode I
Alice és Bob
16. fejezet
Alice és Bob alaptétele
A 11., 12., 13., 14. és 15. fejezetekben betekintést nyertünk abba a gondolkodásmódba, amelyet követve örök érvényű igazságokat tudunk kimondani és bizonyítani a matematikai logika rém egyszerű, ám annál szigorúbb szabályainak betartásával. Mindössze négy állításból, az úgynevezett Peano-axiómarendszerből indultunk ki, amelyek lényegében a természetes számokról alkotott intuitív elképzeléseinket fogalmazzák meg kellő precizitással. Ezekből kiindulva aztán definiáltuk az összeadás és a szorzás műveletét e számok között. Ezután e számkört kibővítettük olyan objektumokkal, amelyek valamiféle adósságot fejeznek ki. Az így kapott halmazt -vel jelöltük és egész számoknak neveztük el őket. Itt már a kivonás is korlátlanul elvégezhető. Végül – elvonatkoztatva a "szám" fogalmától – általánosságban is megfogalmaztuk azokat a követelményeket, amelyeket egy tetszőleges halmaznak teljesítenie kell annak érdekében, hogy az elemeivel a "szokásos" módon "számolni" lehessen. Az ilyen konstrukciókat gyűrűknek neveztük el, amelyeknek számos hasznos tulajdonságát mutattuk meg a 14. és 15. fejezetekben.
De vajon mit kezdjünk azzal, hogy az "osztás" művelete általában nem végezhető el gyűrűkben? Mit jelent az "oszthatóság"? Mikor mondjuk egy gyűrű valamely elemére, hogy "felbonthatatlan" és mely elemeket nevezzük "prímeknek"? Miért van ezeknek kitüntetett szerepük bizonyos gyűrűkben? Mit állít a számelmélet alaptétele, és mitől függ, hogy egy gyűrűben teljesül-e vagy nem? Mi a helyzet az egész számok gyűrűjében? Ebben a fejezetben erről lesz szó...
Figyelem! Ez a fejezet erőteljesen épít a 14. és 15. fejezetben tárgyalt gyűrű fogalmára, valamint az ezekkel kapcsolatos alábbi definíciókra és tételekre:
Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a 14. és a 15. fejezetet, mivel gyakran hivatkozni fogunk rájuk.
Ebben a fejezetben főként az oszthatóság fogalmával fogunk foglalkozni. Számunkra elsősorban az egész számok gyűrűje lesz az érdekes, azonban szeretnénk ezeket a fogalmakat minél általánosabb módon tárgyalni, lehetőleg úgy általában a gyűrűk szintjén. A továbbiakban az egyszerűség kedvéért a kommutatív gyűrűkre szorítkozunk. Ezekben ugyanis az oszthatósággal kapcsolatos definíciók és tételek megfogalmazása jóval egyszerűbbé válik azáltal, hogy a szorzás esetén sem kell törődnünk a tényezők sorrendjével. Amennyiben ettől eltérünk, vagy egy tételhez illetve definícióhoz egyéb tulajdonságra is szükség van – például egységelem létezése vagy nullosztómentesség –, úgy azt külön ki fogjuk hangsúlyozni.
Ezenkívül egy jelölésbeli egyszerűsítést is fogunk tenni a továbbiakban. A 14. és a 15. fejezetben egy alaphalmazú gyűrű jelölésekor mindig felsoroltuk a gyűrű két műveletének szimbólumát is. Például: . Mostantól – ha ez félreértést nem okoz – magát a gyűrűt fogjuk szimplán -rel jelölni. A nullelem és az esetleges egységelem jelölésére rendre a és az , az "összeadás" műveletre a , a "szorzás" műveletre pedig a szimbólumot – vagy az egymás után írást – használjuk majd. Természetesen ha ettől esetleg eltérünk, azt minden ilyen esetben külön jelezni fogjuk. Végül, ha egy elemhez hozzáadjuk egy elem ellentettjét, akkor az kifejezés helyett a rövidebb írásmódot fogjuk használni, és kivonásról, illetve az és elem különbségéről fogunk beszélni.
Egy általános gyűrűben tehát korlátlanul elvégezhető a kivonás bármely két elem között. Nézzük is meg, hogy pontosan mit értünk azalatt, hogy a kivonás lényegében az összeadás "megfordítása". Legyen adva két elem a gyűrűben, jelöljük őket mondjuk -val és -vel. Annyit tudunk róluk, hogy ha az elemet összeadjuk egy másik, ismeretlen elemmel, akkor az eredmény . Feladatunk megtalálni ezt az ismeretlen elemet, amelyet a 16.1. ábrán -val jelöltünk.
Ne feledjük, hogy "összeadás" alatt most a gyűrű szimbólummal jelölt műveletét értjük, semmi egyebet. Erről mindössze annyit tudunk, hogy teljesíti a 14.12. Definíció szerinti rá vonatkozó gyűrűaxiómákat. Az ábrán látható szituációt az alábbi egyenlettel írhatjuk fel:
Feladatunk tehát megtalálni a keresett elemet. Szerencsére a 3. gyűrűaxióma hamar a segítségünkre siet, amely kimondja, hogy a gyűrű minden elemének létezik ellentettje. Így például az elemnek is létezik ilyen, -val jelölt "párja". Az, hogy az inverze a műveletre nézve épp azt jelenti, hogy őket összeadva ugyanezen művelet neutrális elemét kapjuk. A művelet neutrális eleme viszont nem más, mint a gyűrű nulleleme. Ha tehát a fenti egyenlet mindkét oldalához ellentettjét adjuk, akkor a következőt kapjuk:
A baloldalon tehát szerepel, ami a 2. gyűrűaxióma alapján -val egyezik meg. A végeredmény tehát:
Az összeadás "megfordítása" alatt tehát azt értjük, hogy az eredményhez hozzáadva az egyik bemenet ellentettjét, visszakapjuk a másik bemenetet. Vegyük észre, hogy ez épp az általános iskolából ismert kivonással analóg, amikoris a "van forintunk, mennyi kell még ahhoz, hogy épp legyen?" típusú kérdésekre kerestük a választ. A 3. gyűrűaxióma teszi lehetővé, hogy bármilyen számok is szerepeljenek a kérdésben, azt mindig meg tudjuk válaszolni. Nincs más dolgunk ugyanis, mint a második számhoz hozzáadni az első ellentettjét – vagy más szavakkal: a második számból "kivonni" az elsőt –, pont úgy, ahogyan a fenti képlet is leírja. Természetesen ilyen módon adott esetben negatív egész számot is kaphatunk eredményül, amelyet a megfelelő módon kell értelmeznünk. Például a "van forintunk, mennyi kell még ahhoz, hogy épp legyen?" kérdésre a fenti képlet -t ad eredményül, amelyet úgy értelmezhetünk, hogy "el kell költenünk" forintot ahhoz, hogy épp legyen.
16.1Oszthatóság
Lényegesen bonyolultabb a helyzet, ha ugyanezt a kérdést a gyűrű másik műveletére vonatkozóan vizsgáljuk meg. A bevezető szakaszt szóról szóra megismételve, ám a műveletet a műveletre lecserélve ezúttal tehát a következő a feladat: Keressük azt az ismeretlen elemet, amellyel az elemet megszorozva a elemet kapjuk eredményül. A 16.2. ábra mutatja ezt a szituációt.
A bevezetőben ugyan nem hangsúlyoztuk ki, de nagyon fontos, hogy csak a gyűrű elemei között kutakodhatunk, amikor keressük az ismeretlen elemet. Mondhatnánk, hogy egyszerű a feladatunk, hiszen ugyanazt kell csinálni, mint az összeadás megfordítása esetén, két apró különbségtől eltekintve. Egyrészt ezúttal összeadás helyett szorozni kell -t, másrészt pedig ezt a szorzást ellentettje helyett ezúttal multiplikatív inverzével kell végrehajtani. A 14.12. Definíció multiplikatív inverzre vonatkozó jelölését használva ez így fejezhető ki képlettel:
Sajnos azonban az összeadással ellentétben a szorzáshoz nincs olyan gyűrűaxiómánk, amely biztosítja tetszőleges elem multiplikatív inverzének létezését. Ez csak speciális gyűrűkben teljesül, amelyeket a 14.12. Definícióban testeknek neveztünk.
A számunkra fontos egész számok gyűrűje azonban nem test, mivel kizárólag az egységelemnek és az egységelem ellentettjének van multiplikatív inverze: mindkettőnek önmaga. Így ott ez a képlet semmilyen gyakorlatban hasznos esetben nem használható "kiszámításához". Ennek ellenére sok esetben adott és elemekhez mégis létezik olyan elem, amelyre teljesül, hogy . Ez elvezet minket a legfontosabb számelméleti fogalomhoz.
Most nézzünk néhány példát ennek a fogalomnak a megértéséhez. A -vel jelölt egész számok gyűrűjében például , mivel létezik olyan egész szám, amellyel -t megszorozva -ot kapunk: nevezetesen a , hiszen . Ugyanakkor például , mivel nem létezik olyan egész szám, amelyre teljesülne.
Annak demonstrálására, hogy nagyon nem mindegy, melyik gyűrűben beszélünk oszthatóságról, nézzük például a páros – azaz -vel osztható – egész számok halmazát a szokásos összeadással és szorzással. Ezt a halmazt konvencionálisan -vel szoktuk jelölni, és azonnal látszik, hogy ez egy kommutatív gyűrű, hiszen teljesíti a 14.12. Definíció szerinti gyűrűaxiómákat.
A 13.15. és 14.6. Tételben már igazoltuk, hogy az összeadás és a szorzás kommutatív és asszociatív, valamint hogy a szorzás disztributív az összeadásra nézve. A nullelem épp a nulla egész szám, amely szintén páros, továbbá egy páros szám ellentettje is páros, így teljesül a 2. és a 3. gyűrűaxióma is. Már csak annyit kell ellenőrizni, hogy az összeadás és a szorzás valóban művelet-e a halmazon is, azaz nem vezet-e ki belőle. Ez viszont nyilván teljesül, hiszen két páros szám összege és szorzata is páros. Ez a gyűrű viszont nem egységelemes, hiszen a szorzás neutrális eleme az egész szám lenne, ami nem páros. Ugyanakkor nullosztómentes, hiszen ha a 15.6. Tétel alapján semmilyen két nemnulla egész szám szorzata nem lehet , akkor ez speciálisan a páros számokra is nyilván igaz.
Most vizsgáljuk meg a oszthatóságot a gyűrűben is. A gyűrűvel ellentétben itt már nem teljesül ez az oszthatóság, hiszen nem létezik olyan páros szám, amellyel a -t megszorozva -ot kapnánk. Azaz , ugyanakkor .
A 13.3. szakaszban az úgynevezett ekvivalenciarelációk kapcsán ismertük meg a szimmetrikus relációk fogalmát. Ezek olyan relációk, amelyek ha fennállnak az egyik irányban, akkor fennállnak a másik irányban is. Az oszthatósági reláció tehát a gyűrűben nem szimmetrikus, hiszen a fentebbi példa alapján , de .
A 12.6. szakaszban az úgynevezett rendezési relációk kapcsán ismertük meg az antiszimmetrikus relációk fogalmát. Ezek olyan relációk, amelyek ha mindkét irányban fennállnak két elem között, akkor a két elem azonos. A 13.3. szakaszban már említettük, hogy az antiszimmetria és a szimmetria egymással nem ellentétes fogalmak. A gyűrűben értelmezett oszthatósági reláció például – amellett, hogy nem szimmetrikus – az antiszimmetria tulajdonságát sem teljesíti.
Egyrészt ugyanis teljesül az oszthatóság, hiszen létezik olyan egész szám, amellyel -et megszorozva -et kapunk: nevezetesen a . Másrészt teljesül a oszthatóság is, hiszen létezik olyan egész szám is, amellyel -et megszorozva -et kapunk: nevezetesen ismét a . A reláció tehát fennáll mindkét irányban az és a között, ugyanakkor . Ez a reláció tehát valóban nem antiszimmetrikus.
Most vizsgáljuk meg az oszthatósági reláció néhány egyszerű tulajdonságát, amelyek közvetlenül adódnak a 16.1. Definícióból.
A megjegyzés után ismertetjük a tétel bizonyítását.
16.2Egységek
Az oszthatóság tulajdonságairól szóló 16.2. Tétel 4. pontja szerint egy gyűrű nulleleme egyfajta szélsőséget képvisel. Ő ugyanis kizárólag saját magának osztója. A másik szélsőséget azok az elemek képviselik egy gyűrűben, amelyek viszont a gyűrű minden elemének osztói. Ezeknek külön nevük is van.
Az alábbi tétel arra ad választ, hogy mikor létezik egyáltalán egység egy kommutatív gyűrűben.
Azt tehát már tudjuk, hogy egy kommutatív gyűrűben pontosan akkor létezik egység, ha egységelem is létezik. Például a 16.1. szakaszban vizsgált gyűrűben emiatt nem létezik egység, hiszen egységelem sem létezik.
A most következő tétel ahhoz nyújt segítséget, hogy egy kommutatív és egységelemes gyűrűben megtaláljuk az összes egységet. Ehhez mindössze az egységelem ismerete szükséges.
Egy kommutatív és egységelemes gyűrűben tehát az egységek pontosan az egységelem osztói. Az egész számok gyűrűjében ez alapján tehát az -en és a -en kívül nincs más egység, hiszen az egész számnak – mint a gyűrű egységelemének – nincs más osztója.
16.3Asszociált elemek
Most az oszthatóság után egy másik fontos relációval fogunk megismerkedni, amely a 16.2. szakaszban tárgyalt egységekhez kapcsolódik szorosan. Ez a fogalom majd a számelmélet alaptételének a pontos megfogalmazásában lesz segítségünkre a 16.5. szakaszban. Azt fejezi ki, hogy egy gyűrű valamely két eleme az oszthatóság szempontjából "ugyanúgy viselkedik", vagy más szavakkal "megkülönböztethetetlen". Erről szól az alábbi definíció.
Például a gyűrűben az és a egymás asszociáltjai.
Először is megmutatjuk, hogy az asszociáltság egy ekvivalenciareláció a gyűrű alaphalmazán, és így a 13.6. Tétel alapján azt úgynevezett ekvivalencia-osztályokra bontja. Erről a fogalomról bővebben a 13.3. szakaszban volt szó, így javasoljuk az Olvasónak, hogy ismételje át az ezzel kapcsolatos fogalmakat.
Most vizsgáljuk meg, hogy mit tudunk mondani erről az ekvivalenciarelációról. Általános esetben – amikor a gyűrűről csak annyit tudunk, hogy kommutatív – az alábbiakat.
Most vizsgáljuk meg, hogy egységelemes gyűrűk esetén mennyivel tudunk többet mondani az asszociált elempárokról. Az imént bizonyított 16.8. Tétel 4. pontja alapján a kölcsönös oszthatóságból következik az asszociáltság. Kérdés, hogy vajon ez visszafelé is igaz-e, azaz vajon az asszociáltságból következik-e a kölcsönös oszthatóság?
Kommutatív gyűrűk esetén általánosságban nem, azonban az alábbi tétel szerint egy esetleges egységelem létezése már ezt is biztosítja. Ezzel tehát kommutatív és egységelemes gyűrűk esetén kapunk egy elégséges, és egyben szükséges feltételt annak eldöntésére, hogy két tetszőleges elem egymás asszociáltja-e, vagy nem.
Célunk azonban, hogy teljesen feltérképezzük az asszociáltság, mint ekvivalenciareláció által létrehozott ekvivalencia-osztályokat egy adott gyűrűben. Az imént bizonyított 16.9. Tétel alapján két tetszőleges elemről már el tudjuk dönteni, hogy ugyanabba az ekvivalencia-osztályba kerültek-e, vagy sem. Az alábbi tétel ahhoz nyújt segítséget, hogy az egységek ismeretében bármely elemből kiindulva elő tudjuk állítani az őt tartalmazó ekvivalencia-osztály összes többi elemét. Ehhez azonban a kommutativitáson és az egységelem létezésén kívül szükség van a nullosztómentességre is. Az ilyen, sok egyéb szempontból is "normálisan viselkedő" gyűrűket a 15.5. Definícióban integritástartományoknak neveztük.
Ezzel a tétellel már – legalábbis integritástartományok esetén – teljessé vált az asszociáltsági térképünk, amelyet a 16.3. ábra mutat. Itt az látható, hogy az első ekvivalencia-osztály egyetlen eleme a nullelem, a következő osztályban foglalnak helyet az egységek, a további osztályokban pedig egy-egy reprezentánselem egységszeresei szerepelnek. Mint ahogyan azt a 16.8. Tétel utáni megjegyzésben már említettük, testek esetén csak az első kettő ekvivalencia-osztály létezik.
16.4Felbonthatatlanok és prímek
Az oszthatóságról szóló 16.1. szakaszban az volt a feladatunk, hogy egy szorzás bemenetét és kimenetét ismerve keressünk egy elemet a másik bemenetre. Akkor mondtuk, hogy teljesül az oszthatóság, ha létezik ilyen elem a gyűrűben. Most ennél egy fokkal nehezebb a feladatunk. Képzeljük el azt a szituációt, hogy csak a szorzás kimenetét ismerjük, és mindkét bemenetre keresnünk kell egy-egy elemet, amelyek szorzata épp a kimenet. Ezt mutatja a 16.4. ábra.
Ezt képlettel kifejezve:
Itt tehát nem adott és elemek közötti oszthatóság ellenőrzése a feladat, hanem az, hogy a elemnek megtaláljuk valamely osztóját. Algoritmikus szempontból ez egy roppant nehéz feladat, és – mint látni fogjuk a későbbiekben – épp ez biztosítja azt, hogy a modern kriptográfiai eljárások gyakorlatilag feltörhetetlenek. Most azonban tegyük félre az algoritmikus nehézséget, és vizsgáljuk meg ezt a feladatot elméleti szempontból. Egy gyűrűben egy elemet adott esetben sokféleképpen felbonthatunk két másik elem szorzatára.
Az alábbi példában – a tényezők sorrendjétől eltekintve – felsoroltuk az egész szám összes lehetséges felbontását a gyűrűben:
De vajon mi a helyzet akkor, ha például a -at szeretnénk felbontani? Érdekes módon ezt – a tényezők sorrendjétől eltekintve – csak kétféleképpen tehetjük meg:
Látható, hogy mindkét felbontásban az egyik tényező egy egység, a másik tényező pedig az eredeti szám valamely asszociáltja. Ez jelen esetben csak saját maga vagy az ellentettje lehet, mivel a 16.10. Tétel utáni megjegyzés alapján a gyűrűben egy egész számhoz csak ez a két asszociált létezik. Amennyiben az a célunk, hogy az oszthatósággal kapcsolatban újabb információt nyerjünk a felbontandó elemről, úgy az ilyen jellegű felbontásokkal nem sokra megyünk. Az egységtényezőből azért nem tudunk meg semmi újat, mert egy egységnek bármely osztója maga is egység, hiszen az oszthatóság tranzitivitásán keresztül örökli ezt a tulajdonságot. A másik tényezőből pedig azért nem derül ki semmi új, mert neki meg pontosan ugyanazok az osztói, mint a eredeti elemnek.
A gyűrűben a egész szám emiatt egyfajta "építőkockaként" funkcionál: résztvesz más egész számok felépítésében, ám ő maga már nem bontható tovább értelmes módon. Az általános iskolában "prímszámoknak" neveztük azokat a számokat, amelyeknek "olyan kevés osztójuk van, amilyen kevés csak lehet". Elsőre talán zavart okozhat, hogy egyrészt a most következő definícióban teljesen más megnevezést használunk ezekre a kitüntetett elemekre a gyűrűk szintjén, másrészt pedig a "prím" kifejezést látszólag teljesen másra fogjuk használni. Ennek oka azonban hamarosan világossá válik.
A páros számok gyűrűjében például felbonthatatlanok a , , , ..., , ..., illetve ezek ellentettjei is. Ezeknek ugyanis egyáltalán nem létezik felbontása ebben a gyűrűben, mivel nem bonthatók fel páros számok szorzatára.
Az egész számok gyűrűjében például felbonthatatlanok a , , , , , ..., , ..., , ..., illetve ezek ellentettjei is. Ezeknek létezik ugyan felbontásuk, ám azok mind triviális felbontások a 16.11. Definíció szerinti értelemben.
Látható, hogy az oszthatósághoz hasonlóan nagyon nem mindegy, hogy melyik gyűrűben beszélünk felbonthatatlanságról. A például felbonthatatlan a gyűrűben – hiszen nincs két olyan páros szám, amelyeknek szorzata lenne –, viszont összetett a gyűrűben – hiszen nem egység, és a egy nemtriviális felbontás.
Az és a egységek, így a 16.11. Definíció szerint ők nem számítanak felbonthatatlannak. Látszólag semmi nem indokolja, hogy az egységeket önkényesen kizárjuk a felbonthatatlanok közül. Ennek pusztán – mint azt a 16.5. szakaszban látni fogjuk – praktikussági okai vannak a számelmélet alaptételének megfogalmazásakor. A nullelemet azért nem kellett külön kizárni a definícióban a felbonthatatlanok közül, mivel az amúgyis felbontható nemtriviálisan. Például a bármilyen esetén egy nemtriviális felbontás, amennyiben nem egység és nem a nullelem.
A továbbiakban elsősorban integritástartományokat fogunk vizsgálni, amelyekben a szorzás kommutativitás kívül a nullosztómentesség is teljesül – azaz két nemnulla elem szorzata nem lehet –, továbbá létezik bennük egységelem. Ezeket a gyűrűket tekintettük "normálisan" viselkedő gyűrűknek sok szempontból. Az alábbi tétel alapján például integritástartományok esetén a "triviális felbontás" fogalma némiképp egyszerűbben fogalmazható meg a 16.11. Definícióhoz képest.
Azt tehát már tudjuk, hogy amiket általános iskolában "prímeknek" neveztünk, azok a gyűrűk absztrakciós szintjén a felbonthatatlan elemeknek felelnek meg. Jogos lehet a kérdés, hogy akkor ugyanezen az absztrakciós szinten mégis mire használjuk a "prím" kifejezést, ha nem erre.
Ennek a fogalomnak látszólag semmi köze nincs ahhoz, ahogyan az általános iskolában a "prímeket" szokták meghatározni, ezért talán némi magyarázatra szorul.
Emlékeztetnénk az Olvasót az oszthatóság tulajdonságairól szóló a 16.2. Tétel 7. pontjára. Ez ugye azt mondja ki, hogyha egy elem osztója egy szorzat valamely tényezőjének, akkor osztója magának a szorzatnak is. Például az egész számok gyűrűjében , ezért nyilván is teljesül.
Ennek megfordítása azonban általánosságban nem igaz! Ha egy elem osztója egy szorzatnak, abból még nem feltétlenül következik, hogy osztója valamelyik tényezőnek is. Például , ugyanakkor sem a , sem pedig a oszthatóság nem teljesül. A prímek éppen azok az elemek egy gyűrűben, amelyeknél a megfordítás is érvényes minden esetben.
A nullelemet a 16.11. Definícióban nem kellett külön kizárni a felbonthatatlan elemek közül, mert az amúgysem teljesíti a definíció követelményeit. Ezzel szemben az általunk többnyire vizsgált kommutatív és nullosztómentes gyűrűkben teljesíti viszont a 16.13. Definíció követelményeit, ezért ebben a definícióban külön ki kellett kötnünk, hogy őt mégsem tekintjük prímnek. Ha ugyanis valamely és elemekre teljesülne, hogy , akkor ebből az oszthatóság tulajdonságairól szóló 16.2. Tétel 4. pontja miatt következne. Ez viszont a nullosztómentesség miatt csak úgy lehetne, ha és közül legalább az egyik lenne. Ebből viszont következne, hogy a illetve oszthatóságok közül legalább az egyik teljesülne. Azaz végsősoron a prím lenne, ha nem kötnénk ki a definícióban explicit, hogy mégsem az.
Jogosan merülhet fel a kérdés az Olvasóban, hogy vajon miért nevezik az általános iskolában "prímnek" azt, amit mi itt felbonthatatlannak neveztünk. És vajon miért definiáltuk teljesen másként a prím fogalmát? Nem lehetséges-e, hogy valójában ugyanarról a fogalomról van szó? Általánosságban sajnos nem ennyire egyszerű a helyzet. Például a páros számok gyűrűjében a felbonthatatlan, hiszen nem bontható fel két páros szám szorzatára. Ugyanakkor nem prím, hiszen osztója a szorzatnak, de nem osztója sem a -nek, sem pedig a -nak. Méghozzá azért nem, mert nem léteznek olyan páros számok, amelyeket -tal szorozva -t vagy -at kapnánk eredményül.
Általánosságban tehát ez a két fogalom nem ugyanaz. Az imént például láthattuk, hogy bizonyos gyűrűkben létezhetnek olyan elemek, amelyek felbonthatatlanok, de nem prímek. De vajon létezhetnek-e olyan prímek, amik viszont nem felbonthatatlanok? Az alábbi tétel erre a kérdésre ad választ integritástartományok esetén.
Az integritástartományok esetén a prímek és a felbonthatatlan elemek egymáshoz való – az imént bizonyított tétel szerinti – viszonyát mutatja a 16.5. ábra.
Érdekes kérdés, hogy mi a helyzet az olyan kommutatív és nullosztómentes gyűrűk esetén, amelyek – az integritástartományokkal ellentétben – nem egységelemes gyűrűk. Ilyen volt a példaként felhozott gyűrű, amelyben már láttuk, hogy a felbonthatatlan, de nem prím. Egyáltalán léteznek-e prímek az ilyen gyűrűkben? Erre a kérdésre adunk most választ.
A továbbiakban tehát főként integritástartományokat érdemes vizsgálnunk, hiszen az imént bizonyított tétel alapján csak ezekben létezhetnek egyáltalán prímek is a felbonthatatlanok mellett. Azt már láttuk, hogy minden prím egyben felbonthatatlan is. Számunkra főként az olyan integritástartományok lesznek érdekesek, amelyekben ez visszafelé is teljesül, azaz amelyekben minden felbonthatatlan elem prímtulajdonságú. Ezekben tehát ez a két fogalom egy és ugyanaz, és emiatt teljesülni fog rájuk egy olyan tulajdonság, amely kriptográfiai szempontból alapvető fontosságú.
16.5A számelmélet alaptétele
A 16.4. szakaszban láttuk, hogy a gyűrűben egy egész szám adott esetben többféleképpen bontható fel két egész szám szorzatára. Most képzeljük el, hogy az így kapott egész számokat további egész számokra bontjuk, és ezt a felbontást mindaddig folytatjuk minden ágon, ameddig felbonthatatlan számba nem ütközünk. Azt mondtuk, hogy innen már nem érdemes tovább folytatni a felbontást – ha egyáltalán lehetséges –, hiszen oszthatóságra vonatkozó újabb információt már nem fogunk kapni. A 16.6. ábrán a egész szám néhány felbontását láthatjuk a gyűrűben.
Nagyon úgy tűnik, hogy furcsamód minden így kapott felbontás – amennyiben a tényezők sorrendjétől és egymással való asszociáltságától eltekintünk – megegyezik. A következő fejezetben látni fogjuk, a gyűrűben történetesen valóban teljesül, hogy minden -tól és egységtől különböző elem ilyen értelemben "egyértelműen" írható fel felbonthatatlanok szorzataként. Ez azonban egyáltalán nem magától értetődő tulajdonsága egy gyűrűnek. Például a páros számok gyűrűjében a egyrészt felírható -ként, másrészt pedig -ként, és ez a két felbontás "lényegesen különbözik" egymástól a fenti értelemben.
Az "egyértelmű felbonthatóság" teljesülése vagy nem teljesülése egy adott gyűrűben szoros összefüggésben van a prímek és a felbonthatatlanok közötti viszonnyal. Még mielőtt ezt részletesen megvizsgálnánk, először is fogalmazzuk meg mostmár precízen, hogy mikor mondjuk egy integritástartományra azt, hogy teljesül benne ez a tulajdonság.
A számelmélet alaptétele tehát tulajdonképpen két dolgot állít. Egyrészt azt állítja, hogy minden nemnulla és nem egység elemnek létezik felbontása. Másrészt pedig azt, hogy ez a felbontás "néhány apróságtól eltekintve" egyértelmű.
Most adunk egy szükséges – de nem elégséges – feltételt ahhoz, hogy egy integritástartományban teljesüljön a számelmélet alaptétele. A szükségesség azt jelenti, hogy ha ez a feltétel nem teljesül, akkor az alaptétel sem. Az, hogy a feltétel nem elégséges azt jelenti, hogy önmagában ebből a feltételből még nem következik, hogy alaptételes.
Megjegyezzük azonban, hogy igaz ugyan, hogy az imént bizonyított feltétel csak szükséges, de nem elégséges az alaptételhez, azonban "nem hiányzik sok" hozzá, hogy elégséges legyen. Ugyanis a feltétel csak a felbontások létezését nem garantálja. Az alábbi tétel szerint viszont ha létezik felbontás, akkor annak egyértelműségét már garantálja.
Így már nagyjából van egy képünk azzal kapcsolatban, hogy mikor teljesülhet a számelmélet alaptétele egy integritástartományban. Erre adtunk ebben a szakaszban egy szükséges feltételt. Ez a feltétel a teljes alaptételhez ugyan nem volt elégséges, azonban az egyértelműségi részhez már igen. Létezik olyan feltétel is az alaptétel teljesüléséhez, amely szükséges és egyben elégséges is. Ez azonban túlmutat ennek a fejezetnek a keretein, és az úgynevezett ideálok elméletéhez vezet, így azt a 19. fejezetben fogjuk bemutatni.
Ebben a fejezetben tehát megismerkedtünk a legfontosabb számelméleti fogalommal, azaz az oszthatósággal, illetve annak alapvető tulajdonságaival. Ezután bevezettük az egység, asszociáltság, felbonthatatlan és prím fogalmát, amelyek segítségével a számelmélet alaptételét precízen meg tudtuk fogalmazni. Végül szükséges, de nem elégséges feltételt mutattunk ahhoz, hogy egy integritástartományban teljesülhessen az alaptétel.
A következő fejezetben ugyanerre egy elégséges, de nem szükséges feltételt is mutatunk. Ennek keretében integritástartományok egy speciális osztályával fogunk megismerkedni, amelybe – nagy szerencsénkre – az egész számok gyűrűje is beletartozik. Itt fogjuk óriási hasznát venni az erre a gyűrűre az előző fejezetben kiterjesztett, szimbólummal jelölt rendezési relációnak.