Alice és Bob alaptétele

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 \cdot műveletre lecserélve ezúttal tehát a következő a feladat: Keressük azt az ismeretlen k elemet, amellyel az a elemet megszorozva a b elemet kapjuk eredményül. A 16.2. ábra mutatja ezt a szituációt.

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ó k "kiszámításához". Ennek ellenére sok esetben adott a és b elemekhez mégis létezik olyan k elem, amelyre teljesül, hogy ak=b. 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 \Z-vel jelölt egész számok gyűrűjében például 2|6, mivel létezik olyan egész szám, amellyel 2-t megszorozva 6-ot kapunk: nevezetesen a 3, hiszen 2\cdot 3=6. Ugyanakkor például 6\nmid2, mivel nem létezik olyan k egész szám, amelyre 6k=2 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 2-vel osztható – egész számok halmazát a szokásos összeadással és szorzással. Ezt a halmazt konvencionálisan 2\Z-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 2\Z 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 1 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 0, akkor ez speciálisan a páros számokra is nyilván igaz.

Most vizsgáljuk meg a 2|6 oszthatóságot a 2\Z gyűrűben is. A \Z 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 2-t megszorozva 6-ot kapnánk. Azaz 2|_{\Z}6, ugyanakkor 2{\nmid}_{2\Z}6.

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 \Z gyűrűben nem szimmetrikus, hiszen a fentebbi példa alapján 2|6, de 6\nmid 2.

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 \Z 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 1|(-1) oszthatóság, hiszen létezik olyan egész szám, amellyel 1-et megszorozva -1-et kapunk: nevezetesen a -1. Másrészt teljesül a (-1)|1 oszthatóság is, hiszen létezik olyan egész szám is, amellyel -1-et megszorozva 1-et kapunk: nevezetesen ismét a -1. A reláció tehát fennáll mindkét irányban az 1 és a -1 között, ugyanakkor 1\neq -1. 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 2\Z 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 1-en és a -1-en kívül nincs más egység, hiszen az 1 egész számnak – mint a \Z 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 \Z gyűrűben az 5 és a (-5) 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 a bemenetét és b kimenetét ismerve keressünk egy elemet a másik bemenetre. Akkor mondtuk, hogy teljesül az a|b 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.

Itt tehát nem adott a és b elemek közötti oszthatóság ellenőrzése a feladat, hanem az, hogy a c 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.

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 \Z 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 \Z gyűrűben a 13 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 2\Z gyűrűjében például felbonthatatlanok a 2, 6, 10, ..., 150, ..., 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 2, 3, 5, 7, 13, ..., 919, ..., 17180131327, ..., 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 6 például felbonthatatlan a 2\Z gyűrűben – hiszen nincs két olyan páros szám, amelyeknek szorzata 6 lenne –, viszont összetett a \Z gyűrűben – hiszen nem egység, és a 2\cdot 3 egy nemtriviális felbontás.

Az 1 és a -1 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 0\cdot a bármilyen a esetén egy nemtriviális felbontás, amennyiben a 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 0 –, 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 3|6, ezért nyilván 3|6\cdot 2 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 8|2\cdot 12, ugyanakkor sem a 8|2, sem pedig a 8|12 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 a és b elemekre teljesülne, hogy 0|ab, akkor ebből az oszthatóság tulajdonságairól szóló 16.2. Tétel 4. pontja miatt ab=0 következne. Ez viszont a nullosztómentesség miatt csak úgy lehetne, ha a és b közül legalább az egyik 0 lenne. Ebből viszont következne, hogy a 0|a illetve 0|b oszthatóságok közül legalább az egyik teljesülne. Azaz végsősoron a 0 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 2\Z gyűrűjében a 6 felbonthatatlan, hiszen nem bontható fel két páros szám szorzatára. Ugyanakkor nem prím, hiszen osztója a 2\cdot 18 szorzatnak, de nem osztója sem a 2-nek, sem pedig a 18-nak. Méghozzá azért nem, mert nem léteznek olyan páros számok, amelyeket 6-tal szorozva 2-t vagy 18-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 2\Z gyűrű, amelyben már láttuk, hogy a 6 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 \Z 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 100 egész szám néhány felbontását láthatjuk a \Z 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 \Z gyűrűben történetesen valóban teljesül, hogy minden 0-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 2\Z gyűrűjében a 100 egyrészt felírható 2\cdot 50-ként, másrészt pedig 10\cdot 10-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 R 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 R 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.