Episode I
Alice és Bob
20. fejezet
Alice, Bob, Euler és Fermat
A 18. fejezetben bevezettük a gyűrűhomomorfizmus és az ehhez szorosan kapcsolódó gyűrűhomomorfizmus szerinti kongruencia fogalmát. Megmutattuk ugyanakkor, hogy egy ilyen reláció nem függ egy konkrét gyűrűhomomorfizmustól, hanem annak csak a magjától. Ezeket a részhalmazokat ideáloknak neveztük el, definiáltuk az ideál szerinti kongruenciát, és igazoltuk, hogy ez a kétféle kongruencia-fogalom valójában egy és ugyanaz. Ennek során ismerkedtünk meg az úgynevezett maradékosztálygyűrű fogalmával, amely ebben a fejezetben kap fontos szerepet. Végül az előző fejezetben az ideálok segítségével megadtunk egy szükséges és elégséges feltételt a számelmélet alaptételének teljesülésére, valamint megismerkedtünk a főideálgyűrűkkel.
De vajon mit jelent a kongruencia és a maradékosztálygyűrű fogalma az egész számok esetén? Mik azok a teljes és redukált maradékrendszerek, és milyen tulajdonságaik vannak? Mit mér az Euler-féle -függvény? Mit nevezünk lineáris kongruenciának és mikor létezik megoldása? Mit állít az Euler-Fermat tétel és miért olyan fontos? Ebben a fejezetben erről lesz szó...
Figyelem! Ez a fejezet erőteljesen épít a 17., 18. és 19. fejezetekben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:
- 17.4. Definíció (Kitüntetett közös osztó)
- 18.3. Definíció (Moduláris összeadás és szorzás)
- 18.9. Definíció (Gyűrűhomomorfizmus szerinti kongruencia)
- 18.18. Definíció (Ideál)
- 18.20. Definíció (Ideál szerinti kongruencia)
- 18.23. Tétel (Maradékosztálygyűrűk)
- 19.11. Definíció (Végesen generált ideálok és főideálok)
- 19.14. Definíció (Főideálgyűrűk)
Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a 17., 18. és 19. fejezeteket, mivel gyakran hivatkozni fogunk rájuk.
Első körben azt fogjuk megvizsgálni, hogy az egész számok gyűrűjén pontosan mit jelent a 18.20. Definícióban bevezetett, meglehetősen absztrakt ideál szerinti kongruencia. Ehhez előszöris meg kell találnunk e gyűrű ideáljait. A 19.15. Tétel alapján minden euklidészi gyűrű – és így speciálisan maga is – főideálgyűrű.
Ez a 19.14. Definíció szerint azt jelenti, hogy összes ideálja egy-egy elemmel generálható. Ha tehát kiválasztunk egy tetszőleges egész számot, akkor az -et tartalmazó legszűkebb -beli ideált úgy kapjuk meg, hogy képezzük összes többszörösét. Ezt a halmazt a 19.11. Definíció alapján az egész szám által generált főideálnak nevezzük, és -mel jelöljük.
Ha például , akkor az ehhez tartozó főideál – a 19.1. szakaszban tanult halmazjelölésekkel – az alábbi halmaz lesz:
Ezután a 18.20. Definíciót szó szerint követve már könnyedén megmondhatjuk bármely és egész számokról, hogy vajon kongruensek-e a főideál szerint vagy nem. Az említett definíció alapján ez a kongruencia pontosan akkor teljesül, ha az különbség eleme ennek az ideálnak, azaz – szintén a 19.1. szakaszban tanult halmazjelölésekkel – . Például a és a között fennál a főideál szerinti kongruencia, mivel . Ezzel szemben a és a egész számok inkongruensek a főideál szerint, hiszen .
Ez persze nem túl intuitív, és nem is ez volt a "kongruencia" fogalmának eredeti jelentése. Ezt a relációt Carl Friedrich Gauss német matematikus vezette be a Disquisitiones Arithmeticae című művében, és kizárólag az egész számok között volt értelmezve. Ehhez képest az ideál fogalmának alapjait Ernst Kummer, szintén német matematikus fektette le jó 50 évvel később, amikor a mintegy 350 évig megoldatlan nagy Fermat-sejtést akarta bizonyítani. Ez ugyan végül nem sikerült neki, de jelentős előrehaladást sikerült elérnie, és felfedezései a 20. században kifejlesztett számelméleti eszközöket is megalapozták.
Először tehát azt fogjuk megvizsgálni, hogy mi volt a "kongruencia" fogalmának eredeti jelentése, és hogyan kapcsolódik ez a 18.20. Definícióban bevezetett ideál szerinti kongruenciákhoz.
20.1Kongruencia az egész számok között
Gauss eredetileg a 18.3. Definícióban bevezetett osztási maradékokkal kapcsolatban használta a "kongruencia" fogalmát. Tegyük fel, hogy adva van egy egész szám, amelyet az említett definícióban modulusnak neveztünk. A Gauss-féle értelmezésben két tetszőleges és egész számot akkor nevezünk "kongruensnek" az modulus szerint, ha ugyanazt a nemnegatív maradékot adják -mel osztva. Ezt – némiképp eltérve a 18.20. Definícióban szereplő általános jelöléstől – így jelöljük:
A fentebbi példák ugyanúgy igazak maradnak ebben az értelmezésben is. Például a és a között fennál a "kongruencia" a modulus szerint, mivel mindkettőnek lesz a nemnegatív maradéka -mal osztva:
Ezzel szemben a és a egész számok "inkongruensek" modulo , hiszen a -nak , míg a -nak lesz a nemnegatív maradéka -mal osztva:
Megjegyezzük, hogy a maradék nemnegativitását azért fontos megkövetelni, mivel a 18.2. Tétel csak ebben az esetben garantálja a maradék egyértelműségét. Ha ezt nem követelnénk meg, akkor például a kétféle maradékot is adhatna -mal osztva:
Látható, hogy mindkét maradék teljesíti a 17.17. Definícióban szereplő maradékos osztásra vonatkozó kritériumokat, hiszen mind az , mind pedig a maradékok abszolút értéke kisebb -nál. Ha viszont a negatív maradékokat kizárjuk, akkor a 18.2. Tétel szerint a maradékos osztás már csak egyféleképpen végezhető el.
Visszatérve tehát a "kongruencia" fogalmának Gauss-féle értelmezésére, az látszólag megegyezik a 18.20. Definícióban szereplő ideál szerinti kongruencia fogalmával. Legalábbis bármely két egész szám vagy mindkét értelmezés szerint "kongruens" lesz egymással, vagy egyik szerint sem. Az alábbi tételben ezt általánosságban is igazoljuk.
20.2Kongruenciák alapvető tulajdonságai
Az egész számok közötti kongruencia tehát az ideál szerinti kongruencia egy speciális esete, amelynek a 20.1. szakaszban egy intuitív, osztási maradékokkal kapcsolatos értelmezését kaptuk. Az alábbi tételben összegyűjtöttük ennek a relációnak az alapvető tulajdonságait. Ezek mindegyikét valamilyen általános formában már igazoltuk a 18. fejezetben.
Eszerint tehát az összeadásra, a kivonásra és a szorzásra vonatkozóan a kongruenciák ugyanúgy viselkednek, mint az egyenlőségek. Ha például adva van egy szorzásokból, összeadásokból és kivonásokból felépített kifejezés, és ennek bármilyen összetevőjét lecseréljük egy modulus szerint vele kongruens kifejezéssel, akkor az így kapott kifejezés is kongruens lesz az eredetivel az modulus szerint. Tekintsük például az alábbi kifejezést:
Tegyük fel, hogy valamilyen okból kifolyólag azt kell bizonyítanunk, hogy ez a kifejezés tetszőleges egész szám esetén osztható -tel – legyen bármi is ez az ok. Ez kongruenciával kifejezve az alábbit jelenti:
A hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján a baloldali kifejezést átalakítva az alábbit kapjuk:
Nézzük először a baloldal első tagját, azaz a kifejezést. A kongurencia nyilván teljesül a 20.2. Tétel 1. pontja miatt. Továbbá, mivel teljesülnek a és a kongurenciák, ezért ugyanezen tétel 6. pontja miatt teljesülnek a és a kongurenciák is. De ekkor az így kapott három kongurenciát a 4. pont miatt összeszorozhatjuk, azaz teljesül az alábbi kongurencia is:
Ugyanígy az eredeti kongurencia baloldalának második tagját is lecserélhetjük egy vele kongruens kifejezéssel:
Az így kapott két kongurenciát a 4. pont miatt összeadhatjuk, így az alábbi kongurenciát kapjuk:
E kongurencia jobboldala ismét a hatványozás azonosságairól szóló 18.8. Tétel 1. pontja miatt így írható fel:
Mivel , valamint , ezért ismételten alkalmazva a 20.2. Tétel 4. és 6. pontját ezt kapjuk:
Erre már alkalmazhatjuk a gyűrűkre érvényes disztributivitási szabályt:
Végül, mivel , ezért teljesül az alábbi kongurencia is:
Végeredményben tehát a sorozatos átalakításokat elvégezve, és az így kapott kifejezések részeit velük kongruens részkifejezésekkel helyettesítve az alábbi kifejezés valóban tetszőleges egész szám esetén osztható -tel:
Valljuk be, hogy kongurenciák nélkül egy ehhez hasonló kérdés megválaszolása sokkal nehezebb lenne. Kénytelenek lennénk -re vonatkozó teljes indukciót alkalmazni, amiből persze a oszthatóságról szóló 16.2. Tétel állításait használva ugyanezt az eredményt kapnánk, csak épp egy sokkal kényelmetlenebb úton. Ehelyett azonos átalakításokat és a kongurenciák tulajdonságait használva egy ilyen kérdés megválaszolása pár sorban megoldható. Most gyakorlásképpen vegyük át mégegyszer a fenti levezetést egyben:
20.3Kongruenciák osztása
Ahogyan az előző szakaszban láttuk, kongruenciákkal számolni hasonlóan egyszerű, mintha egyenletekkel volna dolgunk. Nagyjából minden ugyanúgy működik. A 18.2. szakaszban azonban már láttuk, hogy az ilyen "nagyjából"-jellegű helyzetekben érhetik az embert kellemetlen meglepetések, ha nem kellő odafigyeléssel jár el. Ez a kongruenciák esetén sincs másként. Az összeadás, kivonás és szorzás esetén – mint láttuk – nincs gond. Az "osztással" azonban vigyázni kell!
Az "osztás" szót azért tettük idézőjelbe, mivel osztani általánosságban amúgy sem lehet egy gyűrűben, kivéve persze ha az adott gyűrű egyben test is. Amikor egy általános gyűrűben beszélünk "osztásról", akkor ezalatt mindig a 15.4. Tétel szerinti egyszerűsítést értjük.
E tétel alapján tehát nullosztómentes gyűrűkben – és csak ezekben – bármilyen egyenlet mindkét oldalát lehet tetszőleges elemmel "elosztani". Feltéve persze, hogy a megfelelő oszthatóságok fennállnak a elem és az egyenlet két oldalán lévő kifejezések között. Semmi gond – mondhatnánk –, egyszer már a 18.2. szakaszban beleszaladtunk ebbe a hibába, így most majd nagyon oda fogunk figyelni. Le is ellenőrizzük, hogy az egész számok gyűrűje a 15.6. Tétel alapján egy integritástartomány – amely tehát nullosztómentes –, így könnyelműen azt gondoljuk, hogy semmi gond nem lehet a kongruenciákkal.
Jól vigyázzunk azonban! Az egyszerűsíthetőségről szóló 15.4. Tétel ugyanis egyenletekről, nem pedig kongruenciákról szól. A 20.2. Tétel 5. pontja ugyan kimondja, hogy ha teljesül az kongruencia, akkor mindkét oldalt megszorozhatjuk valamilyen egész számmal, azaz teljesül az kongruencia is. Ez tehát ugyanúgy működik, mint az egyenlőségeknél. A kongruenciák esetén azonban ennek megfordítása nem feltétlenül igaz még nullosztómentes gyűrűk esetén sem.
Tehát abból, hogy teljesül az kongruencia, még nem következik, hogy az kongruencia is teljesül. Tekintsük az alábbi egyszerű példát:
Ez a kongruencia teljesül, hiszen mindkét oldal -et ad maradékul -tal osztva. Ráadásul a kongruencia mindkét oldala osztható -vel, azaz felírható az alábbi alakban:
Ha most könnyelműen azt gondoljuk, hogy ezt a kongruenciát -vel egyszerűsíthetjük – ahogy mondjuk egy egyenlet esetén minden további nélkül megtehetnénk, hiszen nullosztómentes –, akkor egy végzetes logikai hibát ejtenénk. Az alábbi kongruencia ugyanis nem teljesül:
Nyilván, hiszen a és a nem ugyanazt a maradékot adja -tal osztva.
De mi is volt itt a gond?! Vizsgáljuk meg általánosságban ezt a kérdést! Tegyük fel, hogy teljesül az alábbi, egész számok közötti kongruencia valamilyen modulusra nézve:
Ez ugye a 20.1. Tétel 1. pontja, és az ugyanezen tétel bizonyításához kapcsolódó megjegyzés alapján pontosan azt jelenti, hogy teljesül a 18.3. Definíció szerinti maradékképző függvény, mint gyűrűhomomorfizmus szerinti alábbi kongruencia:
A az egész számok gyűrűjéből a 18.3. Definíció szerinti gyűrűbe képez. A fenti kongruencia tehát azt jelenti, hogy teljesül az alábbi egyenlet a gyűrűben:
Ha a gyűrű szorzását az szimbólummal jelöljük, akkor művelettartó tulajdonsága miatt ez az egyenlet így írható fel:
Ha most itt lehetne az egyenlet mindkét oldalát -val egyszerűsíteni, akkor azt kapnánk, hogy teljesül a egyenlőség. Ez más szavakkal valóban az egész számok közötti kongruencia teljesülését jelentené. De sajnos általában nem ez a helyzet, hiszen ezt az egyszerűsítést a 15.4. Tétel alapján csak nullosztómentes gyűrűkben lehet elvégezni büntetlenül. Márpedig a gyűrű a 18.5. Tétel alapján csak bizonyos esetekben nullosztómentes, nevezetesen: ha prím, vagy egység. A gyűrűre ez nem teljesül.
Összefoglalva tehát a gondot itt az okozza, hogy ugyan maga a kongruencia az egész számok gyűrűjének elemein van értelmezve, azonban ez tulajdonképpen az alábbi, gyűrűben felírt egyenletnek felel meg:
Elvégezve a 18.3. Definíció szerinti maradékképzéseket ezt kapjuk:
Ez az egyenlet valóban teljesül, hiszen a gyűrűben mindkét oldal . Ebben a gyűrűben azonban általánosságban nem szabad egyszerűsíteni egy egyenlet mindkét oldalát ugyanazzal a nemnulla elemmel – jelen esetben -vel –, hiszen a nem prímszám, és nem is egység. Emiatt a gyűrű a 18.5. Tétel alapján nem nullosztómentes.
Ebből ugyanakkor az is következik, hogyha viszont a modulus prímszám lett volna, akkor egy hasonló szituációban minden további nélkül lehetne egyszerűsíteni a kongruenciákat is. Az alábbi tétel általánosan is megfogalmazza, hogy pontosan mikor és milyen körülmények szerint végezhető el az egyszerűsítés.
A fentebbi példára vonatkoztatva ez azt jelenti, hogy a kongruenciát lehet egyszerűsíteni -vel, ám ekkor a modulust is egyszerűsíteni kell a kitüntetett közös osztóval. Valóban, a kongruencia már tényleg teljesül, hiszen mindkét oldal -t ad maradékul -mal osztva.
20.4Egész számok maradékosztályai és maradékosztálygyűrűi
Ebben a szakaszban a gyűrű maradékosztályait vizsgáljuk meg. Általánosságban egy gyűrűben a 18.20. Definíció szerinti értelemben vezettük be az ideál szerinti kongruencia fogalmát.
E definíció szerint amennyiben adva van egy ideál -ben, úgy az ideál szerinti kongruencia pontosan akkor teljesül, ha az különbség benne van az ideálban. A 18.21. Tétel alapján ez egy ekvivalenciareláció elemei között, amely tehát az gyűrűt páronként diszjunkt, nemüres halmazok úniójára bontja. Ezeket a halmazokat neveztük modulo maradékosztályoknak. Az gyűrű minden eleme tehát pontosan egy modulo maradékosztályba kerül bele.
Most vizsgáljuk meg ezt a fogalmat a gyűrűre vonatkoztatva. Mivel a 19.15. Tétel alapján egy főideálgyűrű, ezért annak minden ideáljához található olyan egész szám, amely egymaga generálja -t, azaz . A 20.1. Tételben épp az ilyen főideál szerinti kongruenciákra használtuk az jelölést. Kérdés tehát, hogy vajon mik lesznek egy ilyen kongruencia által meghatározott maradékosztályok? Erre ad választ az alábbi tétel.
Bizonyítás:
A 20.1. Tételben bevezetett modulo kongruencia ekvivalens az főideál szerinti kongruenciával. Ez utóbbi a 18.21. Tétel alapján valóban egy ekvivalenciareláció, így tehát a modulo kongruencia is az, továbbá pontosan ugyanazok lesznek a maradékosztályaik.
Ha egy tetszőleges egész szám, akkor az -t tartalmazó modulo maradékosztály szintén a 18.21. Tétel alapján épp az halmaz lesz, ahol a szimbólum a 18.19. Definícióban bevezetett komplexusösszeadást jelöli. Ez a halmaz tehát meg fog egyezni az -t tartalmazó modulo maradékosztállyal, ezért elég meghatároznunk az halmazt. Minthogy az főideál épp többszöröseit tartalmazza, ezért az halmaz valóban éppen a alakban felírható egész számokból áll. Speciálisan ha , akkor ilymódon minden egész szám külön maradékosztályba kerül, így ezek száma valóban végtelen.
Ha , akkor az szerinti kongruencia ekvivalens a 18.3. Definícióban bevezetett maradékképző függvény, mint gyűrűhomomorfizmus szerinti kongruenciával, hiszen az főideál épp ennek a gyűrűhomomorfizmusnak a magja. Mármost ennek a kongruenciának a maradékosztályai – amelyek tehát megegyeznek az főideál szerinti és így a modulo maradékosztályokkal – a 18.9. Definíció alapján épp azok a halmazok lesznek -ben, amelyeknek az elemeihez a maradékképző függvény azonos elemet rendel hozzá a 18.3. Definíció szerinti halmazból. Ez látható a 20.1. ábrán.
Következésképp esetben a modulo maradékosztályok száma épp meg fog egyezni a gyűrű elemszámával, amely valóban .
Például modulo maradékosztályból pontosan darab van. Ezeket, illetve ezek néhány elemét mutatja a 20.2. ábra. Nézzük meg például a nyíllal jelölt -at tartalmazó maradékosztályt. A tétel szerint ennek elemei pontosan a alakban felírható egész számok.
Valóban, az ábrán megjelenített elemek például így írhatók fel ebben az alakban:
A 18.23. Tételben vezettük be a maradékosztálygyűrű – vagy faktorgyűrű – fogalmát. Ezek olyan gyűrűk, amelyeknek az ideál szerinti maradékosztályok voltak az elemei, és ezek között értelmeztünk két műveletet. Eszerint egy és egy maradékosztály összege szintén egy maradékosztály lesz. Ezt úgy kapjuk meg, hogy veszünk egy-egy tetszőleges és elemet a bemeneti maradékosztályokból, képezzük ezek összegét az eredeti gyűrűben, és azt a maradékosztályt választjuk végeredményként, amelybe ez az összeg esik. Az szorzatot ehhez hasonlóan értelmeztük az eredeti gyűrű szorzásának segítségével.
Az egész számokon imént bevezetett modulo maradékosztályokból ugyanígy a 18.23. Tételben leírt módon alkothatunk egy gyűrűt.
Eszerint tehát ha két maradékosztályt szeretnénk "összeadni" vagy "összeszorozni" egymással a fenti értelemben, akkor teljesen mindegy, hogy a művelet elvégzéséhez mely reprezentánselemeket használjuk.
Tekintsük ismét a modulo maradékosztályokat. A 20.3. ábrán megjelöltünk két maradékosztályt, illetve ezek összegét is, amely egy harmadik maradékosztály. Látható, hogy bármely reprezentánselemeket választjuk a két bemeneti maradékosztályból, e reprezentánselemek -beli összege mindenképp a kimeneti maradékosztályt fogja reprezentálni. Például a és a összegek ugyanazt a maradékosztályt reprezentálják a fenti tétel miatt.
Tegyük fel most, hogy adva van egy egész szám, és tekintsük a 20.5. Tétel szerinti modulo maradékosztálygyűrűt. Ebben a gyűrűben ugyanúgy kell számolni, mint a 18.3. Definícióban bevezetett gyűrűben. Ez a gyűrűk homomorfizmustételének következménye, amelyről a 18.9. szakaszban volt szó bővebben. A példában szereplő modulo maradékosztálygyűrű műveleti táblái emiatt megegyeznek a gyűrű műveleti tábláival. A gyűrű szorzótáblája például így néz ki:
A 18.25. Tétel miatt a gyűrű izomorf a maradékosztálygyűrűvel, amelynek emiatt a szorzótáblája gyakorlatilag megegyezik szorzótáblájával. Az egyetlen különbség az elemek jelölésében van, mint az látható:
A 14.12. Definíció alapján egy gyűrűben a szorzás általában nem invertálható. Ez azonban nem jelenti azt, hogy egyáltalán ne létezhetne olyan nemnulla elem a gyűrűben, amely a szorzásra nézve invertálható – csupán azt, hogy nem mindegyik elem ilyen. Például a gyűrűben mindössze az -hez és a -hez létezik inverz. Mindkettő inverze önmaga, hiszen és .
Ezzel szemben a modulo maradékosztálygyűrűben több invertálható elem is van. A fenti szorzótábla alapján ezek a következő maradékosztályok:
Például a inverze szintén önmaga, mivel . Ezzel ellentétben a , a , a és a maradékosztályok nem invertálhatók, mivel a szorzótáblában a nekik megfelelő sorokban sehol nem szerepel az maradékosztály. Azaz nincs olyan maradékosztály, amellyel őket megszorozva -et kapnánk.
A fenti példákban csupa olyan invertálható elem szerepelt, amelyek mindegyikének az inverze önmaga volt. Ez nem feltétlenül van mindig így. Ha például a modulo maradékosztálygyűrűt vizsgáljuk, akkor ebben a gyűrűben olyan invertálható elem is van, amelynek inverze nem önmaga. Például a maradékosztály inverze a maradékosztály, hiszen őket összeszorozva a egész szám által reprezentált maradékosztályt kapjuk, ami megegyezik az maradékosztállyal.
Az invertálható maradékosztályoknak – fontosságuk miatt – külön nevük is van.
A 20.4. Tételben már láttuk, hogy amennyiben a modulus egy pozitív egész szám, akkor a modulo maradékosztálygyűrű elemszáma pontosan , vagy más szavakkal pontosan darab modulo maradékosztály létezik. Felmerül a kérdés, hogy vajon mi lesz az ugyanezen modulus szerinti redukált maradékosztályok száma? Pontosan ezt méri a számelmélet egyik legfontosabb függvénye, amelyet az alábbi definícióban vezetünk be, és amely Leonhard Euler svájci matematikusról kapta a nevét.
Az alábbiakban megadjuk a -függvény értékét az első néhány pozitív egész számra:
A 20.4. ábrán a -függvény grafikonja látható az első ezer pozitív egész számig bezárólag.
Látható, hogy a függvény bizonyos szempontból meglehetősen hektikusan viselkedik. Felmerül a kérdés, hogy vajon hogyan számítható ki az értéke tetszőleges pozitív egész számra? Ehhez ugye a modulo redukált maradékosztályokat kéne tudnunk megszámolni. Ennek viszont előfeltétele, hogy egy adott maradékosztályról egyáltalán el tudjuk dönteni, hogy redukált-e vagy nem, azaz létezik-e inverze a modulo maradékosztálygyűrű szorzására nézve vagy nem. Ezért most vizsgáljuk meg, hogy ennek mi a feltétele.
Tegyük fel, hogy elénk kerül egy valamilyen egész számmal reprezentált maradékosztály, és azt kell eldöntenünk, hogy létezik-e olyan maradékosztály, amelyre teljesül az alábbi egyenlet a maradékosztálygyűrűben:
Itt jelöli a maradékosztálygyűrű egységelemét, azaz azt a maradékosztályt, amelyben benne van az egész szám. Ekkor a keresett maradékosztály lesz az maradékosztály inverze – amennyiben létezik. A 20.4. Tétel alapján elegendő egyetlen elemét megtalálni, hiszen ebből könnyedén megkapható az összes többi. Jelöljük ezt a keresett elemet -szel, azaz . Ekkor a fenti egyenlet – követve a művelet 20.5. Tétel szerinti definícióját – így módosul:
Szavakkal megfogalmazva tehát kell keresnünk egy olyan egész számot, amely esetén az szorzat ugyanabban a maradékosztályban van, mint az egész szám. A kongruenciák nyelvén ez épp az alábbit jelenti:
Az maradékosztály inverzének létezése tehát azon áll vagy bukik, hogy létezik-e olyan egész szám, amely kielégíti a fenti kongruenciaegyenletet. A következő szakaszban ennek feltételeit tekintjük át.
20.5Lineáris kongruenciák
A kongruenciaegyenletek legegyszerűbb képviselői az úgynevezett "lineáris kongruenciák", mint amilyen a 20.4. szakasz végén szereplő kongruenciaegyenlet is. Ezeknek kulcsszerepe van a kriptográfiai eljárásokban, ezért ebben a szakaszban fontos tételeket mondunk ki velük kapcsolatban. Előszöris definiáljuk pontosan, hogy mit is értünk "lineáris kongruencia", illetve annak "megoldásai" és "megoldásszáma" alatt.
Egy lineáris kongruencia esetén – hasonlóan egy hagyományos egyenlethez – az alábbi kérdésekre keressük a választ:
- Mi a megoldhatóság szükséges és elégséges feltétele?
- Hány megoldás létezik (a 20.8. Definíció szerinti értelemben)?
- Hogyan kaphatjuk meg ezeket a megoldásokat?
Ahhoz, hogy ezeket a kérdéseket megválaszoljuk, először is szükségünk van egy fontos állításra a 19.4. szakaszban tárgyalt végesen generált ideálok elemeivel kapcsolatban. Az alábbi tétel a kommutatív, egységelemes gyűrűk esetére szorítkozik, és arról szól, hogy hogyan tudjuk megkapni egy ideál összes elemét a generátorelemek segítségével. Általános esetben a helyzet némiképp bonyolultabb, és jelenleg nincs is rá szükségünk, így ennek részleteit most mellőzzük.
Például tekintsük a ideált az egész számok gyűrűjében. A tétel alapján ennek összes elemét megkapjuk, ha a
kifejezésbe az és helyére behelyettesítjük az összes lehetséges egész számpárt.
A 20.5. ábrán néhány nemnegatív számpárra számítottuk ki az eredményt, de a táblázat természetesen folytatható lenne a negatív számtartományokban is. A kapott eredmények az ábrán feltüntetett nyilak mentén kettesével követik egymást. Úgy tűnik tehát, hogy a ideál épp a páros számokat tartalmazza, azaz mintha megegyezne a főideállal. A ráadásul épp a és a kitüntetett közös osztója.
A 19.7. szakaszban mutattunk már egy fontos összefüggést – nevezetesen a 19.18. Tételt – egy integritástartomány ideáljai és a kitüntetett közös osztók között. Eszerint ha az és ideálok között halmazegyenlőség áll fenn, akkor kitüntetett közös osztója -nak és -nek.
Vigyázzunk azonban! Visszafelé ugyanis általánosságban nem igaz az összefüggés. Vagyis abból, hogy kitüntetett közös osztója -nak és -nek még nem következik, hogy az és a ideálok megegyeznek. Ennek a megfordításnak a pontos feltételeit az alábbi tétel fogalmazza meg.
Most alkalmazzuk ezt a tételt a fentebbi példára. Mivel a a és kitüntetett közös osztója, továbbá felírható
alakban, ezért a ideál nem csak látszólag, hanem valóban megegyezik a ideállal.
Az imént bizonyított tételnek van egy egyszerű következménye a 19.7. szakaszban tárgyalt főideálgyűrűkre nézve, amely "Bézout-lemma" néven ismeretes. Ez Étienne Bézout 18. századi francia matematikusról kapta a nevét, és eredetileg az egész számok körében volt ismeretes, ám az ennél általánosabb főideálgyűrűkre is érvényes.
Most megmutatjuk a Bézout-lemma – és megfordítása – egy egyszerű következményét, amely a későbbiekben is hasznunkra lesz.
Most térjünk vissza az lineáris kongruencia megoldhatóságának kérdésére. Az alábbi tételben megmutatjuk, hogy ez szoros összefüggésben van bizonyos egész számokon értelmezett egyenletek – az úgynevezett "lineáris diofantoszi egyenletek" – megoldhatóságával.
Ez tehát azt jelenti, hogy az alakban felírt lineáris kongruenciák és az alakban felírt lineáris diofantoszi egyenletek kölcsönösen visszavezethetők egymásra. Azaz bármely, lineáris kongruenciákkal kapcsolatos eredmény felhasználható lineáris diofantoszi egyenletek vizsgálatánál és viszont.
Felhívjuk azonban a figyelmet, hogy jelentős eltérés van a kettő között! Egy lineáris kongruencia megoldásai modulo maradékosztályok, és így a megoldások száma véges. Ezzel szemben egy lineáris diofantoszi egyenlet megoldásai egész számpárok, és ezekből végtelen sok lehet.
Amikor egy lineáris kongruenciát kell megoldanunk, akkor általában az iménti tétel alapján visszavezetjük azt egy lineáris diofantoszi egyenletre. Egy ilyen egyenlet megoldására a 21.1. szakaszban fogunk mutatni egy roppant hatékony módszert, amely tulajdonképpen a 17. fejezetben bemutatott euklidészi algoritmusnak egy kibővített változata. Ennek az eljárásnak a segítségével kiszámítjuk az egyenlet egy megoldását. Ekkor a 20.13. Tétel alapján az által reprezentált maradékosztály épp az eredeti lineáris kongruencia egyik megoldása lesz.
Jogosan merül fel a kérdés, hogy mi van akkor, ha egy lineáris kongruenciának több megoldása is létezik? Vajon összesen hány megoldás van? Hogyan kapható meg egy megoldásból az összes többi? Ezt az alábbi tételben válaszoljuk meg, majd a bizonyítás után egy egyszerű példán demonstráljuk ennek alkalmazását.
Most nézzünk meg egy egyszerű példát az iménti tétel alkalmazására. A 18.2. szakaszban szó volt arról, hogy nagyon óvatosan kell eljárnunk, amikor a 18.3. Definíció szerinti gyűrűben akarunk egyenleteket megoldani. Példaként a gyűrűben írtuk fel az alábbi egyenletet:
Az említett példában megmutattuk, hogyha a "szokásos" módon próbáljuk megoldani ezt az egyenletet, akkor elveszhetnek bizonyos megoldások. Ha például mindkét oldalhoz hozzáadjuk a ellentettjét, majd mindkét oldalt "elosztjuk" -vel, akkor megkapjuk ugyan az megoldást, ám elveszítjük az megoldást. Ennek az oka az volt, hogy a gyűrű nem nullosztómentes – hiszen például , holott egyik tényező sem . Az imént bizonyított, lineáris kongruenciákkal kapcsolatos 20.14. Tétel segítségével azonban már könnyen kezelhetjük az ilyen egyenleteket. Nézzük is meg, hogyan.
Mint már említettük, a 18.25. Tétel miatt a gyűrű izomorf a maradékosztálygyűrűvel, tehát pontosan ugyanúgy kell benne számolni. Emiatt a gyűrűben felírt eredeti egyenletet áttranszformálhatjuk -ba:
A maradékosztály ellentettje az maradékosztály, mivel ezek összege épp a maradékosztály. Így mindkét oldalhoz -öt hozzáadva ezt kapjuk:
Keressük tehát azt az maradékosztályt, amelyet a maradékosztállyal megszorozva a maradékosztályt kapjuk eredményül. Ha megnézzük a maradékosztálygyűrű alábbi szorzótábláját, akkor látszik, hogy két megoldás van – nevezetesen az és az maradékosztályok:
Igenám, csakhogy egy sokkal nagyobb – például a kriptográfiai gyakorlatban előforduló többszázjegyű – modulus esetén nem írhatjuk fel a szorzótáblát, mivel az ehhez használt papírlap sokszorosan beborítaná az egész bolygót. Ehelyett a megoldáshoz az imént bizonyított 20.14. Tételt fogjuk alkalmazni.
A 20.4. Tétel alapján elegendő a keresett maradékosztály egyetlen elemét megtalálni, hiszen ebből könnyedén megkapható az összes többi elem. Jelöljük ezt a keresett elemet -szel, azaz . Ekkor a fenti egyenlet – követve a művelet 20.5. Tétel szerinti definícióját – így módosul:
Szavakkal megfogalmazva tehát kell keresnünk egy olyan egész számot, amely esetén a szorzat ugyanabban a maradékosztályban van, mint a egész szám. Ez épp az alábbi lineáris kongruencia megoldásainak megkeresését jelenti:
A 20.13. Tétel alapján ez a kongruencia megoldható, mivel a kitüntetett közös osztónak többszöröse a kongruencia jobboldalán szereplő egész szám. A 20.14. Tétel 1. pontja alapján a megoldások száma tehát valóban .
Tegyük fel, hogy valahogyan – például a 21.1. szakaszban ismertetett kibővített euklidészi algoritmus segítségével – megtaláltuk a megoldást. Ekkor a 20.14. Tétel 2. pontja miatt pontosan az alábbi maradékosztályok lesznek a megoldások:
Végül a izomorfia miatt az eredeti egyenlet megoldásai az és elemek lesznek a gyűrűben.
20.6Teljes és redukált maradékrendszerek
Most tehát egy lépéssel közelebb kerültünk Euler-féle -függvény kiszámításához, ami ugye a 20.7. Definíció alapján épp a modulo redukált maradékosztályok számát adja meg. Az előző szakaszban tanultak felhasználásával ugyanis egy adott maradékosztályról könnyedén el fogjuk tudni dönteni, hogy redukált-e vagy nem, azaz létezik-e inverze a maradékosztálygyűrű szorzására nézve vagy nem. Ennek pontos feltételét az alábbi tételben adjuk meg.
Az Euler-féle -függvény tehát az imént bizonyított feltételnek eleget tevő maradékosztályok számát adja meg. Mi azonban szeretnénk egy olyan alternatív definíciót adni ennek a függvénynek, amely könnyebben kiszámítható. Ehhez szükségünk van néhány további fogalomra és összefüggésre.
A 20.6. ábrán a -ben lévő modulo maradékosztályok láthatók, illetve egy-egy belőlük képzett teljes és redukált maradékrendszer. Előbbit -vel, utóbbit pedig -rel jelöltük. Látható, hogy a halmaz minden maradékosztályból, az halmaz pedig minden redukált maradékosztályból pontosan egy elemet tartalmaz.
Az alábbi tétel abban nyújt segítséget, hogy egy tetszőleges egész számokból álló halmazról könnyen el tudjuk dönteni, hogy az egy teljes illetve egy redukált maradékrendszer-e vagy sem.
E tétel egyik alkalmazásaként most egy alternatív definíciót is adunk az Euler-féle -függvényre.
Egy másik alkalmazásként megmutatjuk, hogy egy teljes (illetve redukált) maradékrendszerből hogyan kaphatunk egy újabb teljes (illetve redukált) maradékrendszert. Ennek rettentő fontos következménye lesz számunkra az úgynevezett Euler-Fermat tétel, amelyet a 20.7. szakaszban mutatunk be.
20.7Az Euler-Fermat tétel
Végül ebben a szakaszban megismerjük az RSA kriptográfiai eljárás alapját képező Euler-Fermat tételt. Ezt a tételt 1763-ban publikálta Leonhard Euler egy másik hasonlóan fontos tétel, az úgynevezett kis Fermat-tétel általánosításaként, amelyet a 22.1. szakaszban fogunk ismertetni. Ez utóbbi Pierre de Fermat francia műkedvelő matematikustól származik több, mint 100 évvel korábbról, és majd a prímtesztelő eljárások kapcsán lesz róla szó bővebben a 22. fejezetben.
Alkalmazzuk az iménti tételt például az modulusra és hozzá relatív prím -re. Ekkor a kongruencia baloldala így néz ki:
Ez -cal osztva valóban -et ad maradékul.
Az, hogy a tételben szereplő relatív prím az modulushoz a 20.15. Tétel alapján egyben azt is jelenti, hogy ő egy modulo redukált maradékosztály reprezentánseleme. Emiatt az kongruencia a 20.5. szakasz végén leírtakhoz hasonló gondolatmenetet követve az alábbi egyenletnek felel meg a maradékosztálygyűrűben:
Az Euler-Fermat tétel tehát tulajdonképpen azt mondja, hogy a maradékosztálygyűrűben a redukált maradékosztályok – amelyek a 20.6. Definíció alapján ennek a gyűrűnek épp az invertálható elemei – bármelyikét a -edik hatványra emelve mindig az maradékosztályt, vagyis a gyűrű egységelemét kapjuk eredményül. Ez a tény alapvető fontosságú az RSA kriptográfiai eljárás szempontjából, mint ahogyan azt a 22. fejezetben látni fogjuk.
Végül megjegyezzük, hogy az Euler-Fermat tétel megfordítása is igaz. Vagyis az imént említett feltétel – miszerint relatív prím az modulushoz – az Euler-Fermat tételben szereplő kongruencia teljesülésének nemcsak elégséges, hanem egyben szükséges feltétele is. Sőt, az alábbi tételben egy ennél erősebb állítást igazolunk.
Ebben a fejezetben tehát megvizsgáltuk, hogy a 18. fejezetben bevezetett kongruencia fogalma mit jelent az egész számok gyűrűjére vonatkoztatva. Megmutattuk, hogy a kongruenciaegyenletekkel nagyjából ugyanúgy kell számolni, mint a hagyományos egyenletekkel, de azért bizonyos esetekben vigyázni kell. Ezután megvizsgáltuk, hogy hogyan néznek ki az egész számok maradékosztályai és maradékosztálygyűrűi, majd megismerkedtünk az Euler-féle -függvénnyel, amely a modulo redukált maradékosztályok számát adja meg. A lineáris kongruenciák megoldhatóságának feltételei kapcsán erre a függvényre adtunk egy alternatív definíciót is. Végül megismerkedtünk az RSA eljárás alapját képező Euler-Fermat tétellel.
A következő fejezetben kibővítjük a 17. fejezetben megismert euklidészi algoritmust, amely így már alkalmas lesz a most tanult lineáris kongruenciák megoldására is. Megvizsgáljuk továbbá, hogy hogyan lehet kiszámítani az Euler-féle -függvény értékét egy adott számra annak prímtényezőinek ismeretében. Így már minden számelméleti ismeret rendelkezésünkre fog állni az RSA eljárás részleteinek bemutatásához.