youproof.orgDeep Math. Human Access.
Euler és Fermat portréja egymás mellett

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 \varphi-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:

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 \Z 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 \Z is – főideálgyűrű.

Ez a 19.14. Definíció szerint azt jelenti, hogy \Z összes ideálja egy-egy elemmel generálható. Ha tehát kiválasztunk egy tetszőleges m egész számot, akkor az m-et tartalmazó legszűkebb \Z-beli ideált úgy kapjuk meg, hogy képezzük m összes többszörösét. Ezt a halmazt a 19.11. Definíció alapján az m egész szám által generált főideálnak nevezzük, és (m)-mel jelöljük.

Ha például m=3, akkor az ehhez tartozó főideál – a 19.1. szakaszban tanult halmazjelölésekkel – az alábbi halmaz lesz:

(3)=\{\ldots;-9;-6;-3;0;3;6;9;\ldots\}

Ezután a 18.20. Definíciót szó szerint követve már könnyedén megmondhatjuk bármely a és b egész számokról, hogy vajon kongruensek-e a (3) főideál szerint vagy nem. Az említett definíció alapján ez a kongruencia pontosan akkor teljesül, ha az a-b különbség eleme ennek az ideálnak, azaz – szintén a 19.1. szakaszban tanult halmazjelölésekkel – (a-b)\in (3). Például a 13 és a 7 között fennál a (3) főideál szerinti kongruencia, mivel 13-7=6\in (3). Ezzel szemben a 18 és a 13 egész számok inkongruensek a (3) főideál szerint, hiszen 18-13=5\notin (3).

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 m\neq 0 egész szám, amelyet az említett definícióban modulusnak neveztünk. A Gauss-féle értelmezésben két tetszőleges a és b egész számot akkor nevezünk "kongruensnek" az m modulus szerint, ha ugyanazt a nemnegatív maradékot adják m-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\equiv b\pmod m

A fentebbi példák ugyanúgy igazak maradnak ebben az értelmezésben is. Például a 13 és a 7 között fennál a "kongruencia" a 3 modulus szerint, mivel mindkettőnek 1 lesz a nemnegatív maradéka 3-mal osztva:

13\equiv 7\pmod m

Ezzel szemben a 18 és a 13 egész számok "inkongruensek" modulo 3, hiszen a 18-nak 0, míg a 13-nak 1 lesz a nemnegatív maradéka 3-mal osztva:

18\ \cancel{\equiv}\ 13\pmod m

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 13 kétféle maradékot is adhatna 3-mal osztva:

\begin{aligned} 13&=4\cdot 3+1 \\ 13&=5\cdot 3-2 \end{aligned}

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 1, mind pedig a -2 maradékok abszolút értéke kisebb 3-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.1. Tétel (Egész számok közötti kongruencia):

Legyen a és b két tetszőleges, valamint m\geq 0 egy nemnegatív egész szám. Jelöljük továbbá I-vel az m által generált főideált, azaz I=(m). Ekkor teljesülnek az alábbiak:

1.
Amennyiben m\gt 0, úgy a 18.20. Definíció szerinti a\equiv b\pod I kongruencia akkor és csak akkor teljesül, ha a és b ugyanazt a nemnegatív maradékot adja m-mel osztva.
2.
Amennyiben m=0, úgy az a\equiv b\pod I kongruencia akkor és csak akkor teljesül, ha a=b.
3.
Általánosságban az a\equiv b\pod I kongruencia akkor és csak akkor teljesül, ha fennáll az m|a-b oszthatóság.
4.
Speciálisan amennyiben m=1, úgy az a\equiv b\pod I kongruencia mindig teljesül.

Az a és b egész számok közötti, I=(m) főideál szerinti kongruenciát illetve inkongruenciát speciálisan így jelöljük:

\begin{aligned} &a\equiv b\pmod m \\ &a\ \cancel{\equiv}\ b\pmod m \end{aligned}

Ilyenkor azt mondjuk, hogy a kongruens illetve inkongruens b-vel az m modulus szerint (vagy "modulo m").

Megnézem a tudásbázisban

♣

Bizonyítás:

Az 1. állítás: Minthogy I egy ideál az egész számok \Z gyűrűjében, ezért a 18.24. Következmény miatt ő biztosan magja egy valamilyen \Z-ből kiinduló f gyűrűhomomorfizmusnak. Ugyanezen tétel, valamint a 18.12. Definíció utáni megjegyzés miatt azonban a 18.20. Definícióban bevezetett I ideál szerinti kongruencia és a 18.9. Definícióban bevezetett f gyűrűhomomorfizmus szerinti kongruencia két egymással teljesen ekvivalens reláció. Ez azt jelenti, hogy az alábbiak egyszerre teljesülnek, vagy nem teljesülnek:

\begin{aligned} a&\equiv b\pod I\\ a&\equiv b\pod f \end{aligned}

Azaz nincs más dolgunk, mint találni egy olyan f gyűrűhomomorfizmust, amelynek a magja éppen az I ideál. Vegyük észre, hogy mivel most m\neq 0, ezért a 18.3. Definícióban bevezetett \bmod_m-mel jelölt modulo m maradékképző függvény értelmezhető, és épp megfelel erre a célra. Ez a függvény ugyanis a 18.7. Tétel alapján egy szürjektív gyűrűhomomorfizmus az egész számok \Z és a modulo m maradékok Z_m gyűrűje között. Ennek magja ráadásul épp az I=(m) főideál, hiszen ez pontosan az m egész szám többszöröseit tartalmazza. Márpedig ezekhez – és csak ezekhez – a \bmod_m maradékképző függvény a 0 maradékot rendeli hozzá.

Eszerint tehát az a\equiv b\pod I ideál szerinti kongruencia pontosan akkor teljesül, amikor teljesül az a\equiv b\pod{\bmod_m} gyűrűhomomorfizmus szerinti kongruencia. Ez utóbbi viszont pontosan akkor teljesül, ha a \bmod_m maradékképző függvény a-hoz és b-hez ugyanazt a maradékot rendeli hozzá.

A 2. állítás: Amennyiben m=0, akkor nem értelmezett a \bmod_m maradékképző függvény, így ebben az esetben a 18.20. Definícióban bevezetett ideál szerinti kongruenciából kell kiindulnunk. Eszerint az a\equiv b\pod I kongruencia pontosan akkor teljesül, ha az a-b különbség benne van az I ideálban. Ez az ideál azonban nem más, mint az m=0 által generált főideál. Minthogy a 16.2. Tétel 4. pontja alapján a 0-nak önmagán kívül nincs más többszöröse, ezért a (0) főideál mindössze a 0 egész számból fog állni.

Eszerint tehát az a\equiv b\pod I kongruencia pontosan akkor teljesül, ha a-b=0, vagy másként fogalmazva a=b.

A 3. állítás az 1. és a 2. állítások általánosítása. Az I=(m) főideál ugyanis pontosan az m egész szám többszöröseit tartalmazza. Emiatt az a-b különbség pontosan akkor van benne ebben az ideálban – azaz teljesül az a\equiv b\pod I kongruencia –, ha fennáll az m|a-b oszthatóság.

A 4. állítás a 3. állítás speciális esete. Ebben az esetben I=(1), de mivel az 1 egész szám a \Z gyűrű egységeleme, ezért a 16.3. Definíció utáni megjegyzés miatt egyúttal egység is. Minthogy egy egységnek minden elem többszöröse, ezért az I=(1) főideál valójában a teljes \Z gyűrű lesz. Azaz ebben az esetben valóban mindig teljesül az a\equiv b\pod I kongruencia.

Megnézem a tudásbázisban

∎

Megjegyzés:

Az a\equiv b\pmod m jelölés némiképp eltér az ideál szerinti kongruencia 18.20. Definíciójában szereplő jelöléstől. Történelmileg az előbbi volt hamarabb, és ekkor még kizárólag az osztási maradékokkal kapcsolatos jelentést értették alatta, amelyet épp a tétel 1. állítása fogalmaz meg. Ennek bizonyításában a \bmod_m gyűrűhomomorfizmus szerinti kongruenciához jutottunk, amelynek a\equiv b\pod{\bmod_m} jelölése nagyban hasonlít a Gauss-féle a\equiv b\pmod m jelölésre.

Megjegyezzük még, hogy a modulusról látszólag feleslegesen kötöttük ki, hogy nemnegatív, hiszen a fenti bizonyításban ezt egyáltalán nem használjuk ki. A 18.3. Definíció utáni megjegyzés 3. pontja alapján azonban bármilyen egész szám modulo m maradéka megegyezik a modulo -m maradékával, így tehát a modulo m kongruencia pontosan ugyanaz a reláció lenne, mint a modulo -m kongruencia. Ez az oka annak, hogy negatív modulusokat nem használunk, hiszen azok helyettesíthetők a pozitív párjukkal.

Megnézem a tudásbázisban

♣

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.

20.2. Tétel (A kongruencia alapvető tulajdonságai):

Legyen a, b, c és d tetszőleges, továbbá m\geq 0 nemnegatív egész szám. Ekkor teljesülnek az alábbiak:

1.
Teljesül a reflexivitás, azaz:
a\equiv a\pmod m
2.
Teljesül a szimmetria, azaz ha a\equiv b\pmod m, akkor:
b\equiv a\pmod m
3.
Teljesül a tranzitivitás, azaz ha a\equiv b\pmod m és b\equiv c\pmod m, akkor:
a\equiv c\pmod m
4.
Ha a\equiv b\pmod m és c\equiv d\pmod m, akkor teljesülnek az alábbiak:
\begin{aligned} a+c&\equiv b+d\pmod m \\ a-c&\equiv b-d\pmod m \\ ac&\equiv bd\pmod m \end{aligned}
5.
Ha a\equiv b\pmod m, akkor tetszőleges k egész szám esetén teljesülnek az alábbiak:
\begin{aligned} a+k&\equiv b+k\pmod m \\ a-k&\equiv b-k\pmod m \\ ak&\equiv bk\pmod m \end{aligned}
6.
Ha a\equiv b\pmod m, akkor tetszőleges 0\lt n egész szám esetén:
a^n\equiv b^n\pmod m

Itt az a^n és a b^n hatványkifejezéseket a 18.8. Tétel szerinti értelemben értjük.

7.
Ha a\equiv b\pmod m, akkor minden olyan 0\leq k egész szám esetén, amelyre teljesül a k|m oszthatóság, teljesül az alábbi kongruencia is:
a\equiv b\pmod k

Megnézem a tudásbázisban

♣

Bizonyítás:

A 20.1. Tétel alapján az egész számok közötti modulo m kongruencia teljesen ekvivalens az (m) főideál szerinti kongruenciával, ezért minden olyan tétel vonatkozik rá, amelyet az ideál szerinti kongruenciával kapcsolatban már bizonyítottunk.

Az 1., 2. és 3. állítás arról szól, hogy az egész számok közötti kongruencia reflexív, szimmetrikus és tranzitív, azaz a 13.5. Definíció alapján ekvivalenciareláció. Ezt az ideál szerinti kongruenciára a 18.21. Tételben már igazoltuk.

A 4. állítás a 18.22. Tételből következik, aminek a segítségével az ideál szerinti maradékosztályok közötti műveletek jóldefiniáltságát igazoltuk. Minthogy a kivonás tulajdonképpen ellentettel való összeadás, ezért a kivonásra vonatkozó állítás is teljesül.

Az 5. állítás a 4. állítás speciális esete, amikoris c=d=k.

A 6. állítás a 4. állítás speciális esetéből adódik, amikoris c=a és d=b. Itt a szorzásra vonatkozó sor n-szeri alkalmazásával kapjuk az állítást.

Végül a 7. állítás: Az (m) főideál szerinti kongruencia a 18.20. Definíció alapján azt jelenti, hogy a-b\in (m). Mármost ha k|m, akkor a 19.12. Tétel 1. pontja alapján teljesül az (m)\sube (k) tartalmazási reláció, és így a-b\in (k). Ez ismételten a 18.20. Definíció alapján azt jelenti, hogy a és b a (k) főideál szerint is kongruens egymással. Mivel k-ról azt mondtuk, hogy nemnegatív, ezért a 20.1. Tétel szerinti jelölést alkalmazva:

a\equiv b\pmod k

Megnézem a tudásbázisban

∎

Megjegyzés:

A tétel bizonyításához kizárólag néhány, ideál szerinti kongruenciákra vonatkozó korábbi állítást, valamint – a 7. állítás esetében – egy főideálok közötti tartalmazási relációt használtunk fel. Emiatt az összes most bizonyított azonosság automatikusan teljesül erre az általánosabb kongruencia-fogalomra is. Így tehát legyenek a, b, c és d egy tetszőleges R gyűrű elemei, valamint I és J tetszőleges ideálok R-ben. Ekkor teljesülnek az alábbiak:

1.
a\equiv a\pod I
2.
Ha a\equiv b\pod I, akkor b\equiv a\pod I.
3.
Ha a\equiv b\pod I és b\equiv c\pod I, akkor a\equiv c\pod I.
4.
Ha a\equiv b\pod I és c\equiv d\pod I, akkor:
\begin{aligned} a+c&\equiv b+d\pod I \\ a-c&\equiv b-d\pod I \\ ac&\equiv bd\pod I \end{aligned}
5.
Ha a\equiv b\pod I, akkor tetszőleges k\in R esetén:
\begin{aligned} a+k&\equiv b+k\pod I \\ a-k&\equiv b-k\pod I \\ ak&\equiv bk\pod I \end{aligned}
6.
Ha a\equiv b\pod I, akkor tetszőleges 0\lt n egész szám esetén:
a^n\equiv b^n\pod I
7.
Ha a\equiv b\pod I, továbbá I és J főideálok, és I\sube J is teljesül, akkor:
a\equiv b\pod J

Megnézem a tudásbázisban

♣

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 m modulus szerint vele kongruens kifejezéssel, akkor az így kapott kifejezés is kongruens lesz az eredetivel az m modulus szerint. Tekintsük például az alábbi kifejezést:

3^{3n+1}\cdot 5^{2n+1}+2^{5n+1}\cdot 11^n

Tegyük fel, hogy valamilyen okból kifolyólag azt kell bizonyítanunk, hogy ez a kifejezés tetszőleges 0\lt n egész szám esetén osztható 17-tel – legyen bármi is ez az ok. Ez kongruenciával kifejezve az alábbit jelenti:

3^{3n+1}\cdot 5^{2n+1}+2^{5n+1}\cdot 11^n \equiv 0 \pmod{17}

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:

27^n\cdot 25^n\cdot 15 + 32^n\cdot 11^n\cdot 2 \equiv 0 \pmod{17}

Nézzük először a baloldal első tagját, azaz a 27^n\cdot 25^n\cdot 15 kifejezést. A 15\equiv 15\pmod{17} kongurencia nyilván teljesül a 20.2. Tétel 1. pontja miatt. Továbbá, mivel teljesülnek a 27\equiv -7\pmod{17} és a 25\equiv 8\pmod{17} kongurenciák, ezért ugyanezen tétel 6. pontja miatt teljesülnek a 27^n\equiv (-7)^n\pmod{17} és a 25^n\equiv 8^n\pmod{17} 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:

27^n\cdot 25^n\cdot 15 \equiv (-7)^n\cdot 8^n\cdot 15 \pmod{17}

Ugyanígy az eredeti kongurencia baloldalának második tagját is lecserélhetjük egy vele kongruens kifejezéssel:

32^n\cdot 11^n\cdot 2 \equiv (-2)^n\cdot (-6)^n\cdot 2 \pmod{17}

Az így kapott két kongurenciát a 4. pont miatt összeadhatjuk, így az alábbi kongurenciát kapjuk:

\begin{aligned} &27^n\cdot 25^n\cdot 15 + 32^n\cdot 11^n\cdot 2 \equiv \\ \equiv \ &(-7)^n\cdot 8^n\cdot 15 + (-2)^n\cdot (-6)^n\cdot 2 \pmod{17}\end{aligned}

E kongurencia jobboldala ismét a hatványozás azonosságairól szóló 18.8. Tétel 1. pontja miatt így írható fel:

(-56)^n\cdot 15 + 12^n\cdot 2

Mivel (-56)\equiv (-5)\pmod{17}, valamint 12\equiv (-5)\pmod{17}, ezért ismételten alkalmazva a 20.2. Tétel 4. és 6. pontját ezt kapjuk:

\begin{aligned} &(-56)^n\cdot 15 + 12^n\cdot 2 \equiv \\ \equiv \ &(-5)^n\cdot 15 + (-5)^n\cdot 2 \pmod{17} \end{aligned}

Erre már alkalmazhatjuk a gyűrűkre érvényes disztributivitási szabályt:

(-5)^n\cdot 15 + (-5)^n\cdot 2 \equiv (-5)^n\cdot 17 \pmod{17}

Végül, mivel 17\equiv 0\pmod{17}, ezért teljesül az alábbi kongurencia is:

(-5)^n\cdot 17\equiv 0\pmod{17}

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 0\lt n egész szám esetén osztható 17-tel:

3^{3n+1}\cdot 5^{2n+1}+2^{5n+1}\cdot 11^n

Valljuk be, hogy kongurenciák nélkül egy ehhez hasonló kérdés megválaszolása sokkal nehezebb lenne. Kénytelenek lennénk n-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:

\begin{aligned} 3^{3n+1}\cdot 5^{2n+1}+2^{5n+1}\cdot 11^n &= \\ = 27^n\cdot 25^n\cdot 15 + 32^n\cdot 11^n\cdot 2 &\equiv \\ \equiv \ (-7)^n\cdot 8^n\cdot 15 + (-2)^n\cdot (-6)^n\cdot 2 &= \\ = (-56)^n\cdot 15 + 12^n\cdot 2 &\equiv \\ \equiv (-5)^n\cdot 15 + (-5)^n\cdot 2 &= \\ = (-5)^n\cdot 17 &\equiv 0\pmod{17} \end{aligned}

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 c\neq 0 elemmel "elosztani". Feltéve persze, hogy a megfelelő oszthatóságok fennállnak a c 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 \Z 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 a\equiv b\pmod m kongruencia, akkor mindkét oldalt megszorozhatjuk valamilyen k egész számmal, azaz teljesül az ak\equiv bk\pmod m 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 ak\equiv bk\pmod m kongruencia, még nem következik, hogy az a\equiv b\pmod m kongruencia is teljesül. Tekintsük az alábbi egyszerű példát:

28\equiv 46\pmod 6

Ez a kongruencia teljesül, hiszen mindkét oldal 4-et ad maradékul 6-tal osztva. Ráadásul a kongruencia mindkét oldala osztható 2-vel, azaz felírható az alábbi alakban:

14\cdot 2\equiv 23\cdot 2\pmod 6

Ha most könnyelműen azt gondoljuk, hogy ezt a kongruenciát 2-vel egyszerűsíthetjük – ahogy mondjuk egy egyenlet esetén minden további nélkül megtehetnénk, hiszen \Z nullosztómentes –, akkor egy végzetes logikai hibát ejtenénk. Az alábbi kongruencia ugyanis nem teljesül:

14\equiv 23\pmod 6

Nyilván, hiszen a 14 és a 23 nem ugyanazt a maradékot adja 6-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 m\gt 0 modulusra nézve:

ak\equiv bk\pmod m

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 \bmod_m maradékképző függvény, mint gyűrűhomomorfizmus szerinti alábbi kongruencia:

ak\equiv bk\pod{\bmod_m}

A \bmod_m az egész számok \Z gyűrűjéből a 18.3. Definíció szerinti Z_m gyűrűbe képez. A fenti kongruencia tehát azt jelenti, hogy teljesül az alábbi egyenlet a Z_m gyűrűben:

\bmod_m(ak)=\bmod_m(bk)

Ha a Z_m gyűrű szorzását az \odot szimbólummal jelöljük, akkor \bmod_m művelettartó tulajdonsága miatt ez az egyenlet így írható fel:

\bmod_m(a)\odot \bmod_m(k)=\bmod_m(b)\odot \bmod_m(k)

Ha most itt lehetne az egyenlet mindkét oldalát \bmod_m(k)-val egyszerűsíteni, akkor azt kapnánk, hogy teljesül a \bmod_m(a)=\bmod_m(b) egyenlőség. Ez más szavakkal valóban az a\equiv b\pmod m 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 Z_m gyűrű a 18.5. Tétel alapján csak bizonyos esetekben nullosztómentes, nevezetesen: ha m prím, vagy egység. A Z_6 gyűrűre ez nem teljesül.

Összefoglalva tehát a gondot itt az okozza, hogy ugyan maga a 14\cdot 2\equiv 23\cdot 2\pmod 6 kongruencia az egész számok \Z gyűrűjének elemein van értelmezve, azonban ez tulajdonképpen az alábbi, Z_6 gyűrűben felírt egyenletnek felel meg:

\bmod_6(14)\odot \bmod_6(2)=\bmod_6(23)\odot \bmod_6(2)

Elvégezve a 18.3. Definíció szerinti maradékképzéseket ezt kapjuk:

2\odot 2=5\odot 2

Ez az egyenlet valóban teljesül, hiszen a Z_6 gyűrűben mindkét oldal 4. 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 2-vel –, hiszen a 6 nem prímszám, és nem is egység. Emiatt a Z_6 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.

20.3. Tétel:

Legyen a, b, és k tetszőleges, m\gt 0 pozitív egész szám, d pedig a k és m egész számok kitüntetett közös osztója, azaz d=(k,m). Jelöljük továbbá \frac{m}{d}-vel azt az egész számot, amelyet ezzel a d kitüntetett közös osztóval megszorozva az m modulust kapjuk eredményül. Ebben az esetben az alábbi két kongruencia egyszerre teljesül, vagy nem teljesül:

\begin{aligned} ak &\equiv bk\pmod m \\ a &\equiv b\pmod{\frac{m}{d}} \end{aligned}

Megnézem a tudásbázisban

♣

Megjegyzés:

E tétel egy egyszerű következménye, hogy ha a k szorzó tényező relatív prím az m modulushoz, akkor a k-val való egyszerűsítés után a kongruencia változatlan modulus mellett érvényben marad. Azaz ebben az esetben az ak\equiv bk\pmod m kongruenciából következik az a\equiv b\pmod m kongruencia. Ekkor ugyanis a 17.10. Definíció utáni megjegyzés miatt d=(k,m)\sim 1, és így az egyszerűsített \frac{m}{d} modulus meg fog egyezni az eredeti m modulussal – vagy annak ellentettjével, ami teljesen mindegy a 20.1. Tétel bizonyításához fűzött megjegyzés miatt.

Megnézem a tudásbázisban

♣

A fentebbi példára vonatkoztatva ez azt jelenti, hogy a 28\equiv 46\pmod 6 kongruenciát lehet egyszerűsíteni 2-vel, ám ekkor a 6 modulust is egyszerűsíteni kell a (2,6)=2 kitüntetett közös osztóval. Valóban, a 14\equiv 23\pmod 3 kongruencia már tényleg teljesül, hiszen mindkét oldal 2-t ad maradékul 3-mal osztva.

Bizonyítás:

Az ak\equiv bk\pmod m kongruencia a 20.1. Tétel 3. pontja alapján akkor és csak akkor teljesül, ha fennáll az m|ak-bk, azaz a disztributivitási szabály miatt az alábbi oszthatóság:

m|(a-b)c

Ugye \frac{m}{d}-vel jelöltük azt az egész számot, amelyet a d kitüntetett közös osztóval megszorozva az m modulust kapjuk. Ehhez hasonlóan jelöljük \frac{k}{d}-vel azt az egész számot, amelyet ugyancsak d-vel megszorozva a k egész számot kapjuk. Azaz:

\begin{aligned} m&=\frac{m}{d}\cdot d \\ k&=\frac{k}{d}\cdot d \end{aligned}

Nyilván az \frac{m}{d} és a \frac{k}{d} egész számok léteznek, hiszen d osztója m-nek is és k-nak is, mivel ő épp kettejük kitüntetett közös osztója. Ezek után a fenti oszthatóság így néz ki:

\underbrace{\frac{m}{d}\cdot d}_{=m}|(a-b)\underbrace{\frac{k}{d}\cdot d}_{=k}

A 17.8. Tétel alapján egy integritástartományban – mint amilyen a 15.6. Tétel alapján az egész számok \Z gyűrűje is – egy oszthatóság mindkét oldalát szabad egyszerűsíteni bármilyen nemnulla elemmel. A d\neq 0 feltétel teljesül, hiszen ő nem más, mint k és m kitüntetett közös osztója, amely az m\neq 0 feltétel és a 16.2. Tétel 4. pontja miatt biztosan nem lehet 0. A fenti oszthatóság tehát az egyszerűsítési szabály miatt pontosan akkor teljesül, amikor teljesül az alábbi oszthatóság:

\frac{m}{d}|(a-b)\frac{k}{d}

Nézzük most meg, hogy mit tudunk elmondani a (\frac{k}{d},\frac{m}{d}) kitüntetett közös osztóról. Azt ugye tudjuk, hogy (k,m)=d, így tehát igaz az alábbi:

(\underbrace{\frac{k}{d}\cdot d}_{=k},\underbrace{\frac{m}{d}\cdot d}_{=m})=d

A 17.9. Tétel miatt teljesül az alábbi asszociáltság:

\underbrace{(\frac{k}{d}\cdot d,\frac{m}{d}\cdot d)}_{=d}\sim d\cdot (\frac{k}{d},\frac{m}{d})

Minthogy a 16.10. Tétel alapján egy integritástartományban egy elem asszociáltjai pontosan az egységszeresei, emiatt a (\frac{k}{d},\frac{m}{d}) kitüntetett közös osztó szükségképpen egység kell legyen. Ez a 17.10. Definíció utáni megjegyzés alapján pontosan azt jelenti, hogy a \frac{k}{d} és az \frac{m}{d} egész számok egymáshoz relatív prímek. Mindeközben azonban – ahogyan fentebb már láttuk – teljesül az alábbi oszthatóság:

\frac{m}{d}|(a-b)\frac{k}{d}

Mármost ez az oszthatóság egyrészt a 16.2. Tétel 7. pontja miatt akkor, másrészt pedig – mivel \frac{m}{d} relatív prím \frac{k}{d}-hez – a 17.11. Tétel miatt csak akkor teljesül, amikor teljesül az alábbi oszthatóság is:

\frac{m}{d}|(a-b)

Ez viszont a 20.1. Tétel 3. pontja alapján pontosan azt jelenti, hogy – a tétel állításának megfelelően – teljesül az alábbi kongruencia:

a\equiv b\pmod{\frac{m}{d}}

A bizonyítás során minden lépésben "akkor és csak akkor"-típusú állításokat használtunk, ezért a teljes gondolatmenet megfordítható. A tételben szereplő két kongruencia tehát egyszerre teljesül, vagy nem teljesül.

Megnézem a tudásbázisban

∎

20.4Egész számok maradékosztályai és maradékosztálygyűrűi

Ebben a szakaszban a \Z gyűrű maradékosztályait vizsgáljuk meg. Általánosságban egy R 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 I ideál R-ben, úgy az I ideál szerinti a\equiv b\pod I kongruencia pontosan akkor teljesül, ha az a-b különbség benne van az I ideálban. A 18.21. Tétel alapján ez egy ekvivalenciareláció R elemei között, amely tehát az R gyűrűt páronként diszjunkt, nemüres halmazok úniójára bontja. Ezeket a halmazokat neveztük modulo I maradékosztályoknak. Az R gyűrű minden eleme tehát pontosan egy modulo I maradékosztályba kerül bele.

Most vizsgáljuk meg ezt a fogalmat a \Z gyűrűre vonatkoztatva. Mivel a 19.15. Tétel alapján \Z egy főideálgyűrű, ezért annak minden I ideáljához található olyan m egész szám, amely egymaga generálja I-t, azaz I=(m). A 20.1. Tételben épp az ilyen I=(m) főideál szerinti kongruenciákra használtuk az a\equiv b\pmod m 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.

20.4. Tétel (Egész számok maradékosztályai):

Legyen adva egy tetszőleges 0\leq m nemnegatív egész szám. A 20.1. Tételben bevezetett modulo m kongruencia egy ekvivalenciareláció \Z gyűrűben. Az ehhez tartozó ekvivalencia-osztályokat modulo m kongruenciaosztályoknak vagy modulo m maradékosztályoknak nevezzük.

Ha 0\lt m, akkor pontosan m darab modulo m maradékosztály létezik. Legyen a egy tetszőleges egész szám. Ekkor az a-t tartalmazó modulo m maradékosztály bármely eleme felírható km + a alakban valamilyen alkalmas k egész számmal.

Visszafelé: Minden k egész szám esetén a km + a egész szám benne van az a-t tartalmazó modulo m maradékosztályban.

Ha m=0, akkor végtelen sok modulo m maradékosztály létezik, és minden ilyen maradékosztályban pontosan egy egész szám van.

Megnézem a tudásbázisban

♣

Megjegyzés:

A 20.1. Tétel bizonyítása utáni megjegyzésben szereplő okok miatt negatív modulus szerinti maradékosztályokról sem szoktunk beszélni. Ugyanis a modulo m kongruencia pontosan ugyanaz a reláció, mint a modulo -m kongruencia, és így az általuk meghatározott maradékosztályok is megegyeznek.

Megnézem a tudásbázisban

♣

Bizonyítás:

A 20.1. Tételben bevezetett modulo m kongruencia ekvivalens az I=(m) 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 m kongruencia is az, továbbá pontosan ugyanazok lesznek a maradékosztályaik.

Ha a egy tetszőleges egész szám, akkor az a-t tartalmazó modulo I maradékosztály szintén a 18.21. Tétel alapján épp az a+I 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 a-t tartalmazó modulo m maradékosztállyal, ezért elég meghatároznunk az a+I halmazt. Minthogy az I=(m) főideál épp m többszöröseit tartalmazza, ezért az a+I halmaz valóban éppen a km + a alakban felírható egész számokból áll. Speciálisan ha m=0, 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 m\gt 0, akkor az I=(m) szerinti kongruencia ekvivalens a 18.3. Definícióban bevezetett \bmod_m maradékképző függvény, mint gyűrűhomomorfizmus szerinti kongruenciával, hiszen az I=(m) 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 I=(m) főideál szerinti és így a modulo m maradékosztályokkal – a 18.9. Definíció alapján épp azok a halmazok lesznek \Z-ben, amelyeknek az elemeihez a \bmod_m maradékképző függvény azonos elemet rendel hozzá a 18.3. Definíció szerinti Z_m halmazból. Ez látható a 20.1. ábrán.

Maradékképző függvény és maradékosztályok
20.1. ábra: Maradékképző függvény és maradékosztályok

Következésképp m\gt 0 esetben a modulo m maradékosztályok száma épp meg fog egyezni a Z_m gyűrű elemszámával, amely valóban m.

Megnézem a tudásbázisban

∎

Például modulo 8 maradékosztályból pontosan 8 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 13-at tartalmazó maradékosztályt. A tétel szerint ennek elemei pontosan a 8k+13 alakban felírható egész számok.

Modulo 8 maradékosztályok
20.2. ábra: Modulo 8 maradékosztályok

Valóban, az ábrán megjelenített elemek például így írhatók fel ebben az alakban:

\begin{aligned} -11&=8\cdot (-3)+13 \\ -3&=8\cdot (-2)+13 \\ 5&=8\cdot (-1)+13 \\ 13&=8\cdot 0+13 \\ 21&=8\cdot 1+13 \end{aligned}

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 A és egy B maradékosztály A\oplus B összege szintén egy maradékosztály lesz. Ezt úgy kapjuk meg, hogy veszünk egy-egy tetszőleges a\in A és b\in B elemet a bemeneti maradékosztályokból, képezzük ezek a+b összegét az eredeti gyűrűben, és azt a maradékosztályt választjuk végeredményként, amelybe ez az a+b összeg esik. Az A\odot B 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 m maradékosztályokból ugyanígy a 18.23. Tételben leírt módon alkothatunk egy gyűrűt.

20.5. Tétel (Egész számok maradékosztálygyűrűi):

Legyen 0\leq m egy tetszőleges nemnegatív egész szám, és jelöljük \Z/m\Z-vel azt a halmazt, amelynek elemei a 20.4. Tételben definiált modulo m maradékosztályok. Ha a valamilyen egész szám, akkor jelöljük [a]_m-mel az a-t tartalmazó modulo m maradékosztályt. Ilyenkor az a egész számot az [a]_m maradékosztály reprezentánsának (vagy reprezentáns elemének) nevezzük, és azt mondjuk, hogy a reprezentálja az [a]_m maradékosztályt.

Most bevezetünk két műveletet a \Z/m\Z halmazon. Ha [a]_m és [b]_m két maradékosztály \Z/m\Z-ben, akkor ezek \oplus-szal jelölt összege illetve \odot-tal jelölt szorzata legyen rendre az alábbi két maradékosztály:

\begin{aligned} [a]_m\oplus [b]_m&=[a+b]_m \\ [a]_m\odot [b]_m&=[a\cdot b]_m \end{aligned}

Ekkor a \Z/m\Z halmaz ezzel a két művelettel egy kommutatív és egységelemes gyűrűt alkot, amelyet modulo m maradékosztálygyűrűnek nevezünk. E gyűrű nulleleme a [0]_m, egységeleme pedig az [1]_m maradékosztály.

Tekintsük továbbá azt az f:\Z\to \Z/m\Z függvényt, amely minden a egész számhoz az [a]_m maradékosztályt rendeli hozzá. Ekkor f egy szürjektív gyűrűhomomorfizmus \Z és \Z/m\Z között, melynek magja az m egész szám többszöröseinek halmaza.

Megnézem a tudásbázisban

♣

Bizonyítás:

A modulo m maradékosztályok pontosan az (m) főideál szerinti maradékosztályokkal egyeznek meg. Emiatt a \Z/m\Z halmaz a tételben bevezetett \oplus és \odot műveletekkel nem más, mint a \Z gyűrűnek az (m) főideál szerinti faktorgyűrűje, azaz a 18.23. Tételben bevezetett jelölésekkel \Z/(m). Innentől kezdve a bizonyítás teljesen megegyezik a 18.23. Tétel bizonyításával.

Mivel \Z kommutatív és egységelemes, ezért a 18.23. Tétel 4. és 3. pontja alapján a \Z/(m)=\Z/m\Z faktorgyűrű is az, amelynek egységeleme az 1+(m) maradékosztály, ami épp az [1]_m modulo m maradékosztálynak felel meg. Ehhez hasonlóan a 18.23. Tétel 1. pontja alapján a nullelem a 0+(m) maradékosztály, ami pedig épp a [0]_m modulo m maradékosztálynak felel meg.

Végül a tételben szereplő f függvény a 18.23. Tétel 5. pontja alapján épp a természetes gyűrűhomomorfizmus, amelynek magja az (m) főideál, és amely valóban az m egész szám többszöröseit tartalmazza.

Megnézem a tudásbázisban

∎

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 8 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 \Z-beli összege mindenképp a kimeneti maradékosztályt fogja reprezentálni. Például a -14+19=5 és a 10+11=21 összegek ugyanazt a maradékosztályt reprezentálják a fenti tétel miatt.

Modulo 8 maradékosztályok összeadása
20.3. ábra: Modulo 8 maradékosztályok összeadása

Tegyük fel most, hogy adva van egy m\gt 0 egész szám, és tekintsük a 20.5. Tétel szerinti modulo m maradékosztálygyűrűt. Ebben a gyűrűben ugyanúgy kell számolni, mint a 18.3. Definícióban bevezetett Z_m 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 8 maradékosztálygyűrű műveleti táblái emiatt megegyeznek a Z_8 gyűrű műveleti tábláival. A Z_8 gyűrű szorzótáblája például így néz ki:

\begin{array}{c|cccccccc}\odot &0&1&2&3&4&5&6&7 \\ \hline 0&0&0&0&0&0&0&0&0 \\ 1&0&1&2&3&4&5&6&7 \\ 2&0&2&4&6&0&2&4&6 \\ 3&0&3&6&1&4&7&2&5 \\ 4&0&4&0&4&0&4&0&4 \\ 5&0&5&2&7&4&1&6&3 \\ 6&0&6&4&2&0&6&4&2 \\ 7&0&7&6&5&4&3&2&1 \end{array}

A 18.25. Tétel miatt a Z_8 gyűrű izomorf a \Z/8\Z maradékosztálygyűrűvel, amelynek emiatt a szorzótáblája gyakorlatilag megegyezik Z_8 szorzótáblájával. Az egyetlen különbség az elemek jelölésében van, mint az látható:

\begin{array}{c|cccccccc}\odot & [0]_8 & [1]_8 & [2]_8 & [3]_8 & [4]_8 & [5]_8 & [6]_8 & [7]_8 \\ \hline [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 \\ [1]_8 & [0]_8 & [1]_8 & [2]_8 & [3]_8 & [4]_8 & [5]_8 & [6]_8 & [7]_8 \\ [2]_8 & [0]_8 & [2]_8 & [4]_8 & [6]_8 & [0]_8 & [2]_8 & [4]_8 & [6]_8 \\ [3]_8 & [0]_8 & [3]_8 & [6]_8 & [1]_8 & [4]_8 & [7]_8 & [2]_8 & [5]_8 \\ [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 \\ [5]_8 & [0]_8 & [5]_8 & [2]_8 & [7]_8 & [4]_8 & [1]_8 & [6]_8 & [3]_8 \\ [6]_8 & [0]_8 & [6]_8 & [4]_8 & [2]_8 & [0]_8 & [6]_8 & [4]_8 & [2]_8 \\ [7]_8 & [0]_8 & [7]_8 & [6]_8 & [5]_8 & [4]_8 & [3]_8 & [2]_8 & [1]_8 \end{array}

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 \Z gyűrűben mindössze az 1-hez és a -1-hez létezik inverz. Mindkettő inverze önmaga, hiszen 1\cdot 1=1 és (-1)\cdot (-1)=1.

Ezzel szemben a modulo 8 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:

[1]_8, [3]_8, [5]_8, [7]_8

Például a [3]_8 inverze szintén önmaga, mivel [3]_8\odot [3]_8 = [1]_8. Ezzel ellentétben a [0]_8, a [2]_8, a [4]_8 és a [6]_8 maradékosztályok nem invertálhatók, mivel a szorzótáblában a nekik megfelelő sorokban sehol nem szerepel az [1]_8 maradékosztály. Azaz nincs olyan maradékosztály, amellyel őket megszorozva [1]_8-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 10 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 [3]_{10} maradékosztály inverze a [7]_{10} maradékosztály, hiszen őket összeszorozva a 21 egész szám által reprezentált maradékosztályt kapjuk, ami megegyezik az [1]_{10} maradékosztállyal.

Az invertálható maradékosztályoknak – fontosságuk miatt – külön nevük is van.

20.6. Definíció (Redukált maradékosztály):

Legyen m\gt 0 egy tetszőleges pozitív egész szám. Ekkor a 20.5. Tétel szerinti \Z/m\Z maradékosztálygyűrű invertálható elemeit modulo m redukált maradékosztályoknak nevezzük.

Megnézem a tudásbázisban

♣

A 20.4. Tételben már láttuk, hogy amennyiben a modulus egy m\gt 0 pozitív egész szám, akkor a modulo m maradékosztálygyűrű elemszáma pontosan m, vagy más szavakkal pontosan m darab modulo m 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.

20.7. Definíció (Az Euler-függvény):

Legyen m\gt 0 tetszőleges pozitív egész szám. Ekkor a modulo m redukált maradékosztályok számát a \varphi(m)-mel jelölt függvény értéke adja meg. Ezt a függvényt Euler-féle \varphi-függvénynek (ejtsd: "fi") nevezzük.

Megnézem a tudásbázisban

♣

Az alábbiakban megadjuk a \varphi-függvény értékét az első néhány pozitív egész számra:

\begin{aligned} \varphi(1)&=1 \\ \varphi(2)&=1 \\ \varphi(3)&=2 \\ \varphi(4)&=2 \\ \varphi(5)&=4 \\ \varphi(6)&=2 \\ \varphi(7)&=6 \\ \varphi(8)&=4 \\ \varphi(9)&=6 \\ \varphi(10)&=4 \\ &\vdots \end{aligned}

A 20.4. ábrán a \varphi-függvény grafikonja látható az első ezer pozitív egész számig bezárólag.

Az Euler-függvény grafikonja
20.4. ábra: Az Euler-függvény grafikonja

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 m\gt 0 pozitív egész számra? Ehhez ugye a modulo m 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 m 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 a egész számmal reprezentált [a]_m maradékosztály, és azt kell eldöntenünk, hogy létezik-e olyan X maradékosztály, amelyre teljesül az alábbi egyenlet a maradékosztálygyűrűben:

[a]_m\odot X=[1]_m

Itt [1]_m jelöli a maradékosztálygyűrű egységelemét, azaz azt a maradékosztályt, amelyben benne van az 1 egész szám. Ekkor a keresett X maradékosztály lesz az [a]_m maradékosztály inverze – amennyiben létezik. A 20.4. Tétel alapján elegendő X egyetlen elemét megtalálni, hiszen ebből könnyedén megkapható az összes többi. Jelöljük ezt a keresett elemet x-szel, azaz X=[x]_m. Ekkor a fenti egyenlet – követve a \odot művelet 20.5. Tétel szerinti definícióját – így módosul:

[a]_m\odot [x]_m=[ax]_m=[1]_m

Szavakkal megfogalmazva tehát kell keresnünk egy olyan x egész számot, amely esetén az ax szorzat ugyanabban a maradékosztályban van, mint az 1 egész szám. A kongruenciák nyelvén ez épp az alábbit jelenti:

ax\equiv 1\pmod m

Az [a]_m maradékosztály inverzének létezése tehát azon áll vagy bukik, hogy létezik-e olyan x 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ő ax\equiv b\pmod m 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.

20.8. Definíció (Lineáris kongruenciák):

Legyen a és b tetszőleges, m\gt 0 pedig valamilyen pozitív egész szám. Ekkor az alábbi kongruenciaegyenletet lineáris kongruenciának nevezzük:

ax\equiv b\pmod m

Egy lineáris kongruencia egy megoldása alatt egy olyan modulo m maradékosztályt értünk, amelynek tetszőleges elemét x helyére behelyettesítve a kongruencia teljesül.

Egy lineáris kongurencia megoldásszáma alatt azon modulo m maradékosztályok számát értjük, amelyek megoldásai az adott lineáris kongruenciának.

Megnézem a tudásbázisban

♣

Megjegyzés:

Nyilvánvaló, hogyha egy s egész számot x helyére behelyettesítve a kongruencia teljesül – azaz as\equiv b\pmod m –, akkor ez igaz lesz az s által reprezentált [s]_m maradékosztály összes többi elemére is. Ha ugyanis egy t egész szám benne van ebben a maradékosztályban, az pontosan azt jelenti, hogy teljesül az alábbi kongruencia:

s\equiv t\pmod m

Ekkor azonban a 20.2. Tétel 5. pontja miatt teljesül az alábbi kongruencia is:

as\equiv at\pmod m

Ha tehát as\equiv b\pmod m fennáll, akkor ugyanezen tétel 2. és 3. pontja miatt

at\equiv b\pmod m

is fennáll. Ez az oka annak, hogy egy lineáris kongruencia megoldása alatt nem egy-egy egész számot, hanem teljes maradékosztályokat értünk.

Megnézem a tudásbázisban

♣

Egy lineáris kongruencia esetén – hasonlóan egy hagyományos egyenlethez – az alábbi kérdésekre keressük a választ:

  1. Mi a megoldhatóság szükséges és elégséges feltétele?
  2. Hány megoldás létezik (a 20.8. Definíció szerinti értelemben)?
  3. 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.

20.9. Tétel:

Legyen R egy tetszőleges kommutatív, egységelemes gyűrű, továbbá legyenek a_1, a_2, ..., a_n az R gyűrű tetszőleges elemei. Ekkor az ezen elemek által generált I ideál pontosan azokból az r\in R elemekből áll, amelyek felírhatók

r=r_1a_1+r_2a_2+\ldots +r_na_n

alakban az R gyűrű alkalmasan választott r_1, r_2, ..., r_n elemeinek, valamint az a_1, a_2, ..., a_n generátorelemeknek a segítségével.

Egy ilyen felírást az a_1, a_2, ..., a_n generátorelemek lineáris kombinációjának nevezzük.

Megnézem a tudásbázisban

♣

Bizonyítás:

Jelöljük tehát I-vel azt a halmazt, amely pontosan az

r_1a_1+r_2a_2+\ldots +r_na_n

alakban felírható elemeket tartalmazza. Azt kell tehát bizonyítani, hogy I a legszűkebb olyan ideál, amely tartalmazza az a_1, a_2, ..., a_n elemeket.

Kezdjük annak igazolásával, hogy I ideál. Ehhez a 18.18. Definíció alapján azt kell megmutatni, hogy I részgyűrű – amihez a 18.15. Tétel feltételeit fogjuk ellenőrizni –, valamint, hogy I tetszőleges elemét megszorozva bármelyik R-beli elemmel az eredmény benne van I-ben. Ellenőrizzük ezeket a feltételeket sorban.

Összeadásra való zártság

Legyen r és s az I halmaz két tetszőleges eleme. Mivel ők I elemei, ezért felírhatók a tételben szereplő alakban:

\begin{aligned} r &= r_1a_1+r_2a_2+\ldots +r_na_n \\ s &= s_1a_1+s_2a_2+\ldots +s_na_n \end{aligned}

Ekkor ezek összege szintén a tételben szereplő alakban írható fel a disztributivitási szabályok miatt:

r+s = (r_1+s_1)a_1+(r_2+s_2)a_2+\ldots +(r_n+s_n)a_n

Emiatt az r+s összeg szintén benne van I-ben, amely tehát valóban zárt az összeadásra nézve.

Szorzásra való zártság

Legyen s az I halmaz tetszőleges eleme. Mivel s\in I, ezért ő felírható a tételben szereplő alakban:

s = s_1a_1+s_2a_2+\ldots +s_na_n

Ezt megszorozva tetszőleges r\in R elemmel az így kapott szorzat szintén a tételben szereplő alakban írható fel a disztributivitási szabályok és a szorzás asszociativitása miatt:

\begin{aligned} rs&=r\cdot (s_1a_1+s_2a_2+\ldots +s_na_n)= \\ &=r(s_1a_1)+r(s_2a_2)+\ldots +r(s_na_n)= \\ &=(rs_1)a_1+(rs_2)a_2+\ldots +(rs_n)a_n \end{aligned}

Emiatt az rs szorzat szintén benne van I-ben. Mivel r tetszőleges R-beli elem lehet – beleértve persze az I-beli elemeket is –, ezért I nemcsak az önmagán belüli szorzásra nézve zárt, hanem a tetszőleges R-beli elemekkel való szorzásokra nézve is.

Tartalmazza a nullelemet

Ez nyilvánvaló, hiszen a nullelem felírható a tételben szereplő alakban:

0=0a_1+0a_2+\ldots +0a_n
Ellentettképzésre való zártság

Legyen r az I halmaz tetszőleges eleme. Mivel r\in I, ezért ő felírható a tételben szereplő alakban:

r=r_1a_1+r_2a_2+\ldots +r_na_n

De ekkor ennek ellentettje a 15.1. Tétel 5. és 3. pontja miatt szintén felírható ilyen alakban:

\begin{aligned} -r&=-(r_1a_1+r_2a_2+\ldots +r_na_n)= \\ &=(-(r_1a_1))+(-(r_2a_2))\ldots (-(r_na_n)) \\ &=(-r_1)a_1+(-r_2)a_2+\ldots +(-r_n)a_n= \\ \end{aligned}

Emiatt (-r) szintén benne van I-ben, amely tehát zárt az ellentettképzésre is.

Az I halmaz tehát valóban ideál, ráadásul ő tartalmazza az a_1, a_2, ..., a_n generátorelemeket. Nyilván, hiszen R egységelemes, és így az egységelemet 1-gyel jelölve mindegyikük felírható a tételben szereplő alakban:

\begin{aligned} a_1&=1a_1 + 0a_2 + 0a_3 +\ldots +0a_n \\ a_2&=0a_1 + 1a_2 + 0a_3 +\ldots +0a_n \\ a_3&=0a_1 + 0a_2 + 1a_3 +\ldots +0a_n \\ &\vdots \\ a_n&=0a_1 + 0a_2 + 0a_3 +\ldots +1a_n \end{aligned}

Azt tehát már tudjuk, hogy I egy olyan ideál, amely tartalmazza az a_1, a_2, ..., a_n generátorelemeket. Annyit kell még igazolni, hogy ő a legszűkebb ilyen ideál.

A 19.7. Definíció és az utána lévő megjegyzés értelmében ez azt jelenti, hogy ha J egy tetszőleges ideál, amely szintén tartalmazza a generátorelemeket, akkor I\sube J-nek kellene teljesülnie.

Tekintsünk tehát egy tetszőleges t\in I elemet, és mutassuk meg, hogy ekkor t\in J is teljesül. Mivel t\in I, ezért ő felírható a tételben szereplő alakban:

t=t_1a_1+t_2a_2+\ldots +t_na_n

Azt ugye tudjuk, hogy J tartalmazza az a_1, a_2, ..., a_n generátorelemeket. Tekintve, hogy J ideál, ezért a 18.18. Definíció miatt tartalmazza a t_1a_1, t_2a_2, ..., t_na_n szorzatokat is. Továbbá ideál lévén ő egyúttal részgyűrű is, ami a 18.15. Tétel 1. pontja alapján zárt az összeadásra nézve, azaz tartalmazza a

t=t_1a_1+t_2a_2+\ldots +t_na_n

összeget is, és így valóban t\in J.

Megnézem a tudásbázisban

∎

Például tekintsük a (8,6) ideált az egész számok gyűrűjében. A tétel alapján ennek összes elemét megkapjuk, ha a

8x+6y

kifejezésbe az x és y 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 (8,6) ideál épp a páros számokat tartalmazza, azaz mintha megegyezne a (2) főideállal. A 2 ráadásul épp a 8 és a 6 kitüntetett közös osztója.

A (8,6) ideál elemei
20.5. ábra: A (8,6) ideál elemei

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 (a,b) és (d) ideálok között halmazegyenlőség áll fenn, akkor d kitüntetett közös osztója a-nak és b-nek.

Vigyázzunk azonban! Visszafelé ugyanis általánosságban nem igaz az összefüggés. Vagyis abból, hogy d kitüntetett közös osztója a-nak és b-nek még nem következik, hogy az (a,b) és a (d) ideálok megegyeznek. Ennek a megfordításnak a pontos feltételeit az alábbi tétel fogalmazza meg.

20.10. Tétel:

Legyen R tetszőleges integritástartomány, továbbá a, b és d az R tetszőleges elemei. Ekkor teljesülnek az alábbiak:

1.
Ha d kitüntetett közös osztója a-nak és b-nek, akkor (a,b)\sube (d).
2.
Az (a,b)=(d) halmazegyenlőség akkor és csak akkor teljesül, ha d kitüntetett közös osztója a-nak és b-nek, és felírható az a és b elemek lineáris kombinációjaként az R gyűrű alkalmasan választott u és v elemeinek segítségével az alábbi alakban:
d=ua+vb

Megnézem a tudásbázisban

♣

Bizonyítás:

Az 1. állítás: Legyen d kitüntetett közös osztója a-nak és b-nek. Azt kell bizonyítani, hogy ekkor fennáll az (a,b)\sube (d) tartalmazási reláció, azaz az (a,b) ideál bármely eleme egyúttal a (d) ideálnak is eleme.

Legyen tehát x az (a,b) ideál egy tetszőleges eleme. Mivel R kommutatív és egységelemes – hiszen integritástartomány –, ezért a 20.9. Tétel értelmében x kifejezhető az a és b generátorelemek lineáris kombinációjaként:

x=ua + vb

Mivel fennállnak a d|a és d|b oszthatóságok – hiszen d közös osztója a-nak és b-nek –, ezért a 16.2. Tétel 7. és 6. pontja miatt fennáll az alábbi oszthatóság is:

d|\underbrace{ua+vb}_{=x}

Azaz x többszöröse d-nek, ami azt jelenti, hogy benne van a (d) ideál, tehát valóban teljesül az (a,b)\sube (d) tartalmazási reláció.

A 2. állítás: Azt már a 19.18. Tételben igazoltuk, hogy az (a,b)=(d) halmazegyenlőség esetén d kitüntetett közös osztója a-nak és b-nek. Így most csak annyit kell megmutatni, hogy felírható ua+vb alakban. Mivel nyilván d\in (d), ezért az (a,b)=(d) halmazegyenlőség miatt d\in (a,b). Ám ekkor d a 20.9. Tétel alapján valóban felírható a kívánt alakban.

Visszafelé: Legyen most d kitüntetett közös osztója a-nak és b-nek, és tegyük fel, hogy d felírható ua+vb alakban. Azt kell megmutatni, hogy ebben az esetben teljesül az (a,b)=(d) halmazegyenlőség. Mivel d kitüntetett közös osztó, ezért az 1. állítás miatt fennáll az (a,b)\sube (d) tartalmazási reláció, így már csak a másik irányú tartalmazást – vagyis azt, hogy (d)\sube (a,b) – kell bizonyítani.

Ha x a (d) ideál tetszőleges eleme, akkor az azt jelenti, hogy ő d-nek többszöröse, azaz teljesül a d|x oszthatóság. Ez a 16.1. Definíció alapján azt jelenti, hogy létezik olyan k\in R, amelyre

x=kd

De mivel d-ről azt mondtuk, hogy felírható ua+vb alakban, ezért ugyanez igaz lesz x-re is:

x=k\cdot (\underbrace{ua+vb}_{=d})=(ku)\cdot a+(kv)\cdot b

Így x a 20.9. Tétel alapján benne van az (a,b) ideálban, tehát valóban teljesül a (d)\sube (a,b) tartalmazási reláció is. Minthogy (d) és (a,b) között mindkét irányban fennáll a tartalmazási reláció, ezért a 19.2. Definíció utáni megjegyzés 5. pontja miatt a két halmaz megegyezik.

Megnézem a tudásbázisban

∎

Most alkalmazzuk ezt a tételt a fentebbi példára. Mivel a 2 a 8 és 6 kitüntetett közös osztója, továbbá felírható

2=1\cdot 8 + (-1)\cdot 6

alakban, ezért a (8,6) ideál nem csak látszólag, hanem valóban megegyezik a (2) 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.

20.11. Tétel (Bézout-lemma):

Legyen R főideálgyűrű, továbbá legyenek a és b az R tetszőleges elemei. Ekkor az a és b elemek kitüntetett közös osztója kifejezhető a kettejük lineáris kombinációjaként

ua+vb

alakban az R alkalmasan választott u és v elemeinek a segítségével.

Megnézem a tudásbázisban

♣

Megjegyzés:

Teljesül az állítás megfordítása is. Nevezetesen, ha d közös osztó, és R-ben léteznek olyan u és v elemek, hogy ua+vb=d, akkor d egyúttal kitüntetett közös osztó.

Legyen ugyanis e egy tetszőleges közös osztó, azaz e|a és e|b. Ekkor azonban a 16.2. Tétel 7. és 6. pontja alapján teljesül az alábbi oszthatóság is:

e|\underbrace{ua+vb}_{=d}

Azaz a d közös osztó többszöröse bármelyik e közös osztónak. Ez a 17.4. Definíció alapján azt jelenti, hogy d valóban kitüntetett közös osztó.

Megnézem a tudásbázisban

♣

Bizonyítás:

Jelöljük d-vel az a és b kitüntetett közös osztóját. Mivel R főideálgyűrű, ezért az (a,b) ideál is szükségképpen főideál, azaz generálható egyetlen elemmel is. Létezik tehát olyan e\in R, hogy

(a,b)=(e)

Ekkor azonban a 20.10. Tétel 2. pontja alapján e is kitüntetett közös osztója a-nak és b-nek.

A kitüntetett közös osztó a 17.5. Tétel szerint asszociáltság erejéig egyértelmű, azaz e\sim d. Ez viszont a 16.6. Definíció alapján azt jelenti, hogy e-nek és d-nek pontosan ugyanazok a többszöröseik, vagyis az általuk generált ideálok megegyeznek, azaz

(d)=\underbrace{(a,b)}_{=(e)}

Ebből viszont a 20.10. Tétel 2. pontja miatt következik, hogy d valóban kifejezhető

ua+vb

alakban R valamilyen alkalmas u és v elemeinek a segítségével.

Megnézem a tudásbázisban

∎

Most megmutatjuk a Bézout-lemma – és megfordítása – egy egyszerű következményét, amely a későbbiekben is hasznunkra lesz.

20.12. Következmény:

Legyen R főideálgyűrű, továbbá legyenek a és b az R tetszőleges elemei. Ekkor bármelyik R-beli elem akkor és csak akkor relatív prím ab-hez, ha relatív prím a-hoz is és b-hez is.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tegyük fel ugyanis indirekt, hogy egy valamilyen c elem relatív prím ab-hez, de nem relatív prím a-hoz. Ez a 17.10. Definíció alapján azt jelentené, hogy létezik olyan n elem, amely közös osztója a-nak és c-nek, de nem egység. Ekkor a 16.2. Tétel 7. pontja miatt n közös osztója lenne ab-nek és c-nek, és mivel nem egység, ezért – szintén a 17.10. Definíció alapján – c nem lehetne relatív prím az ab szorzathoz. Ilyen n közös osztó tehát nem létezhet, következésképp minden ab-hez relatív prím elem egyben relatív prím a-hoz. Ehhez hasonlóan igazolható, hogy minden ab-hez relatív prím elem egyben relatív prím b-hez is.

Visszafelé: Tegyük fel, hogy egy valamilyen c elem relatív prím a-hoz is és b-hez is. Ez a 17.10. Definíció utáni megjegyzés alapján az alábbiakat jelenti:

\begin{aligned} (c,a)\sim 1 \\ (c,b)\sim 1 \end{aligned}

Ekkor a 20.11. Tételben megfogalmazott Bézout-lemma miatt felírhatók az alábbi lineáris kombinációk:

\begin{aligned} u_1c+v_1a=1 \\ u_2c+v_2b=1 \end{aligned}

A két egyenletet összeszorozhatjuk:

(u_1c+v_1a)(u_2c+v_2b)=1

Bontsuk fel a zárójeleket:

u_1u_2cc+u_1v_2bc+v_1u_2ac+v_1v_2ab=1

Végül emeljük ki c-t és ab-t a baloldali tagokból, és jelöljük az így kapott együtthatókat U-val és V-vel:

\underbrace{(u_1u_2c+u_1v_2b+v_1u_2a)}_{=U}\cdot c + \underbrace{(v_1v_2)}_{=V}\cdot ab=1

Azaz lényegében előállítottuk az egységelemet c és ab lineáris kombinációjaként az U és V együtthatók segítségével. Mivel az egységelem a 16.3. Definíció utáni megjegyzés alapján mindig egység, ezért ő osztója minden elemnek, tehát közös osztója c-nek és ab-nek. Ekkor azonban alkalmazható a 20.11. Tétel utáni megjegyzésben szereplő állítás – a Bézout-lemma megfordítása –, amely szerint tehát (c,ab)\sim 1, és így c valóban relatív prím az ab szorzathoz.

Megnézem a tudásbázisban

∎

Most térjünk vissza az ax\equiv b\pmod m 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.

20.13. Tétel:

Legyen a és b tetszőleges, 0\lt m pedig valamilyen pozitív egész szám. Ekkor az ax\equiv b\pmod m lineáris kongruencia akkor és csak akkor oldható meg, ha megoldható az alábbi úgynevezett lineáris diofantoszi egyenlet:

ax+my=b

Itt megoldás egy olyan egész számpárt értünk, amelyeket az egyenletbe x és y helyére behelyettesítve teljesül az egyenlőség.

Egy tetszőleges s egész szám által reprezentált [s]_m maradékosztály akkor és csak akkor megoldása az ax\equiv b\pmod m lineáris kongruenciának, ha létezik olyan t egész szám, hogy az (s;t) számpár megoldása a fenti egyenletnek, azaz fennáll az

as+mt=b

egyenlőség.

Jelöljük (a,m)-mel az a és m egész számok kitüntetett közös osztóját. A fenti lineáris diofantoszi egyenletnek – és így a neki megfelelő ax\equiv b\pmod m lineáris kongruenciának – akkor és csak akkor létezik megoldása, ha teljesül az (a,m)|b oszthatóság.

Megnézem a tudásbázisban

♣

Bizonyítás:

Az ax\equiv b\pmod m megoldhatósága azt jelenti, hogy létezik olyan [s]_m maradékosztály, amely megoldása ennek a kongruenciának. Az [s]_m maradékosztályt tehát az s egész számmal reprezentáltuk, azaz teljesül az as\equiv b\pmod m kongruencia. Ez viszont a 20.1. Tétel 3. pontja alapján pontosan akkor teljesül, ha fennáll az m|b-as oszthatóság. A 16.1. Definíció alapján ez pontosan akkor teljesül, ha létezik olyan t egész szám, amelyre teljesül az mt=b-as egyenlet.

Mindkét oldalhoz as-t hozzáadva azt kaptuk tehát, hogy az ax\equiv b\pmod m kongruencia akkor és csak akkor oldható meg, ha létezik olyan (s;t) egész számpár, amely megoldása lineáris diofantoszi egyenletnek:

ax+my=b

A fentiekből továbbá kiderült, hogy ekkor – és csakis ekkor – az [s]_m maradékosztály valóban megoldása az ax\equiv b\pmod m lineáris kongruenciának.

Végül azt igazoljuk, hogy az ax+my=b egyenlet – és az eddigiek miatt az ax\equiv b\pmod m kongruencia – megoldhatóságának szükséges és elégséges feltétele az (a,m)|b oszthatóság. Tegyük ezért fel, hogy az x_0, y_0 számpár egy megoldása ennek az egyenletnek, azaz:

ax_0+my_0=b

Mivel az (a,m) az a és m közös osztója, ezért nyilván fennállnak az (a,m)|a és (a,m)|m oszthatóságok. Emiatt a 16.2. Tétel 7. és 6. pontja alapján valóban fennáll az alábbi oszthatóság is:

(a,m)|\underbrace{ax_0 +my_0}_{=b}

Visszafelé: Ha fennáll az (a,m)|b oszthatóság, az azt jelenti, hogy létezik olyan t egész szám, amelyre teljesül az alábbi egyenlet:

(a,m)\cdot t=b

Mivel \Z a 19.15. Tétel alapján főideálgyűrű, ezért alkalmazható a 20.11. Tétel. Ez alapján az (a,m) kitüntetett közös osztóhoz léteznek olyan u és v egész számok, hogy teljesül az alábbi:

(a,m)=au+mv

Ezt behelyettesíthetjük az előző egyenletbe:

(\underbrace{au+mv}_{(a,m)})\cdot t=b

A zárójelet felbontva végül ezt kapjuk:

a\cdot (ut) + m\cdot (vt)=b

Azaz lényegében megkaptuk az ax+my=b lineáris diofantoszi egyenlet egy megoldását, nevezetesen az x=ut, y=vt számpárt.

Megnézem a tudásbázisban

∎

Ez tehát azt jelenti, hogy az ax\equiv b\pmod m alakban felírt lineáris kongruenciák és az ax+my=b 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 m 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 (x;y) megoldását. Ekkor a 20.13. Tétel alapján az x által reprezentált [x]_m 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.

20.14. Tétel:

Legyen a és b tetszőleges, 0\lt m pedig pozitív egész szám. Jelöljük továbbá az a és m pozitív kitüntetett közös osztóját d-vel, azaz d=(a,m). Ekkor igazak az alábbi állítások:

1.
Ha az ax\equiv b\pmod m lineáris kongruencia megoldható, akkor a 20.8. Definíció szerinti értelemben vett megoldások száma d.
2.
Ha egy valamilyen s egész szám által reprezentált [s]_m maradékosztály megoldása az ax\equiv b\pmod m lineáris kongruenciának, akkor pontosan az alábbi – egymástól páronként különböző – maradékosztályok alkotják az összes megoldást:
\begin{aligned} &[s+0\cdot \frac{m}{d}]_m \\ &[s+1\cdot \frac{m}{d}]_m \\ &[s+2\cdot \frac{m}{d}]_m \\ &[s+3\cdot \frac{m}{d}]_m \\ &\vdots \\ &[s+(d-1)\cdot \frac{m}{d}]_m \end{aligned}

Itt \frac{m}{d} alatt azt az egész számot értjük, amelyet a d=(a,m) kitüntetett közös osztóval megszorozva az m modulust kapjuk eredményül, azaz amelyre teljesül, hogy

\frac{m}{d}\cdot d = m

Megnézem a tudásbázisban

♣

Bizonyítás:

Elegendő a 2. állítást igazolni, abból ugyanis automatikusan következik a megoldásszámra vonatkozó 1. állítás.

Azt mondtuk, hogy az s egész szám által reprezentált [s]_m maradékosztály megoldása a kongruenciának, azaz:

as\equiv b\pmod m

Válasszunk most egy tetszőleges t egész számot. Az általa reprezentált [t]_m maradékosztály akkor és csak akkor lesz megoldása a kongruenciának, ha teljesül

at\equiv b\pmod m

Mivel a kongruencia a 20.2. Tétel 2. és 3. pontja alapján szimmetrikus és tranzitív, ezért ez ekvivalens az alábbival:

as\equiv at\pmod m

A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük a-val, ám eközben az m modulust is "el kell osztanunk" az (a,m) kitüntetett közös osztóval, azaz jelen esetben d-vel. Az előző kongruencia tehát ekvivalens az alábbival:

s\equiv t\pmod{\frac{m}{d}}

Vagyis a t által reprezentált [t]_m maradékosztály akkor és csak akkor lesz megoldás, ha t ugyanabba a modulo \frac{m}{d} maradékosztályba esik, mint s, azaz:

[s]_{\frac{m}{d}}=[t]_{\frac{m}{d}}

Ez a 20.4. Tétel alapján akkor és csak akkor teljesül, ha t felírható az alábbi alakban valamilyen alkalmasan választott k egész számmal:

t=s+k\cdot \frac{m}{d}

Azt kaptuk tehát, hogy amennyiben ismerünk egy [s]_m megoldást, akkor az összes többi megoldást előállíthatjuk

[s+k\cdot \frac{m}{d}]_m

alakban. Így már csak azt kell igazolni, hogy k-val végigfutva az összes egész számon épp a tétel 2. állításában szereplő d darab modulo m maradékosztály reprezentánselemeit kapjuk.

Nézzük meg ezért, hogy két tetszőleges k_1 és k_2 esetén az s+k_1\frac{m}{d} és s+k_2\frac{m}{d} kifejezések mikor fogják ugyanazt a maradékosztályt reprezentálni, azaz mikor fog teljesülni az alábbi:

[s+k_1\frac{m}{d}]_m=[s+k_2\frac{m}{d}]_m

Ez ugye pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

s+k_1\frac{m}{d}\equiv s+k_2\frac{m}{d} \pmod m

A 20.2. Tétel 5. pontja miatt mindkét oldalból kivonhatunk s-t:

k_1\frac{m}{d}\equiv k_2\frac{m}{d} \pmod m

A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük \frac{m}{d}-vel. Vigyázat! A tétel szerint ilyenkor ugyanis a modulust is egyszerűsíteni kell \frac{m}{d} és m kitüntetett közös osztójával. Azaz az előbbi kongruencia akkor és csak akkor akkor teljesül, amikor az alábbi kongruencia is:

k_1\equiv k_2 \pmod{\frac{m}{(\frac{m}{d}, m)}}

Most vizsgáljuk meg, hogy tulajdonképpen mivel egyezik meg az itt szereplő modulus. Ne feledjük, hogy itt nem törtekről van szó, hiszen jelenleg a \Z gyűrűben vagyunk, ahol nem értelmezhető az "osztás". Ehelyett például az \frac{m}{d} csak egy jelölés, amely azt az egész számot jelöli, amellyel a d egész számot megszorozva az m egész számot kapjuk eredményül. Azaz:

\frac{m}{d} \cdot d = m

Feltéve persze, ha ilyen létezik, aminek ugye a feltétele az d|m oszthatóság. Ez jelen esetben nyilván fennáll, mivel azt mondtuk, hogy d az a és m kitüntetett közös osztója. Ám ekkor teljesül az \frac{m}{d}|m oszthatóság is, így az (\frac{m}{d},m) kitüntetett közös osztó a 17.6. Tétel 2. pontja miatt \frac{m}{d} asszociáltja, és emiatt lecserélhető vele. A fenti kongruenciában szereplő modulus tehát így hozható egyszerűbb formára:

\frac{m}{(\frac{m}{d}, m)}=\frac{m}{(\frac{m}{d})}

Ez tehát azt az egész számot jelöli, amelyet az \frac{m}{d} egész számmal megszorozva az m egész számot kapjuk eredményül. A fentebbi \frac{m}{d} \cdot d = m összefüggés alapján ez épp d-vel egyezik meg. A fenti kongruencia tehát tulajdonképpen így néz ki:

k_1\equiv k_2\pmod d

Azt kaptuk tehát, hogy az [s+k_1\frac{m}{d}]_m és [s+k_2\frac{m}{d}]_m modulo m maradékosztályok akkor és csak akkor egyeznek meg, amikor a [k_1]_d és [k_2]_d modulo d maradékosztályok is megegyeznek. Az ax\equiv b\pmod m lineáris kongruenciának tehát pontosan annyi megoldása van, ahány modulo d maradékosztály létezik.

Ezek száma viszont a 20.4. Tétel alapján d. Így tehát ha k végigfut a 0, 1, 2, ..., d-1 egész számokon, akkor épp a tétel 2. állításában szereplő maradékosztályokat kapjuk megoldásként.

Megnézem a tudásbázisban

∎

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 Z_m gyűrűben akarunk egyenleteket megoldani. Példaként a Z_8 gyűrűben írtuk fel az alábbi egyenletet:

(2\odot x)\oplus 3=7

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 3 ellentettjét, majd mindkét oldalt "elosztjuk" 2-vel, akkor megkapjuk ugyan az x=2 megoldást, ám elveszítjük az x=6 megoldást. Ennek az oka az volt, hogy a Z_8 gyűrű nem nullosztómentes – hiszen például 2\odot 4=0, holott egyik tényező sem 0. 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 Z_8 gyűrű izomorf a \Z/8\Z maradékosztálygyűrűvel, tehát pontosan ugyanúgy kell benne számolni. Emiatt a Z_8 gyűrűben felírt eredeti (2\odot x)\oplus 3=7 egyenletet áttranszformálhatjuk \Z/8\Z-ba:

([2]_8\odot X)\oplus [3]_8=[7]_8

A [3]_8 maradékosztály ellentettje az [5]_8 maradékosztály, mivel ezek összege épp a [0]_8 maradékosztály. Így mindkét oldalhoz [5]_8-öt hozzáadva ezt kapjuk:

[2]_8\odot X=[4]_8

Keressük tehát azt az X maradékosztályt, amelyet a [2]_8 maradékosztállyal megszorozva a [4]_8 maradékosztályt kapjuk eredményül. Ha megnézzük a \Z/8\Z maradékosztálygyűrű alábbi szorzótábláját, akkor látszik, hogy két megoldás van – nevezetesen az X=[2]_8 és az X=[6]_8 maradékosztályok:

\begin{array}{c|cccccccc}\odot & [0]_8 & [1]_8 & [2]_8 & [3]_8 & [4]_8 & [5]_8 & [6]_8 & [7]_8 \\ \hline [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 & [0]_8 \\ [1]_8 & [0]_8 & [1]_8 & [2]_8 & [3]_8 & [4]_8 & [5]_8 & [6]_8 & [7]_8 \\ [2]_8 & [0]_8 & [2]_8 & [4]_8 & [6]_8 & [0]_8 & [2]_8 & [4]_8 & [6]_8 \\ [3]_8 & [0]_8 & [3]_8 & [6]_8 & [1]_8 & [4]_8 & [7]_8 & [2]_8 & [5]_8 \\ [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 & [0]_8 & [4]_8 \\ [5]_8 & [0]_8 & [5]_8 & [2]_8 & [7]_8 & [4]_8 & [1]_8 & [6]_8 & [3]_8 \\ [6]_8 & [0]_8 & [6]_8 & [4]_8 & [2]_8 & [0]_8 & [6]_8 & [4]_8 & [2]_8 \\ [7]_8 & [0]_8 & [7]_8 & [6]_8 & [5]_8 & [4]_8 & [3]_8 & [2]_8 & [1]_8 \end{array}

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 X 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 x-szel, azaz X=[x]_m. Ekkor a fenti egyenlet – követve a \odot művelet 20.5. Tétel szerinti definícióját – így módosul:

[2]_8\odot [x]_8=[2\cdot x]_8=[4]_8

Szavakkal megfogalmazva tehát kell keresnünk egy olyan x egész számot, amely esetén a 2x szorzat ugyanabban a maradékosztályban van, mint a 4 egész szám. Ez épp az alábbi lineáris kongruencia megoldásainak megkeresését jelenti:

2x\equiv 4\pmod 8

A 20.13. Tétel alapján ez a kongruencia megoldható, mivel a (2,8)=2 kitüntetett közös osztónak többszöröse a kongruencia jobboldalán szereplő 4 egész szám. A 20.14. Tétel 1. pontja alapján a megoldások száma tehát valóban 2.

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 [2]_8 megoldást. Ekkor a 20.14. Tétel 2. pontja miatt pontosan az alábbi maradékosztályok lesznek a megoldások:

\begin{aligned} [2+0\cdot \frac{8}{(2,8)}]_8&=[2]_8 \\ [2+1\cdot\frac{8}{(2,8)}]_8&=[2+4]_8=[6]_8 \end{aligned}

Végül a Z_8\simeq \Z/8\Z izomorfia miatt az eredeti (2\odot x)\oplus 3=7 egyenlet megoldásai az x=2 és x=6 elemek lesznek a Z_8 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 \varphi-függvény kiszámításához, ami ugye a 20.7. Definíció alapján épp a modulo m 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 \Z/m\Z maradékosztálygyűrű szorzására nézve vagy nem. Ennek pontos feltételét az alábbi tételben adjuk meg.

20.15. Tétel:

Legyen m\gt 0 tetszőleges pozitív egész szám. Egy a egész szám által reprezentált [a]_m maradékosztály akkor és csak akkor redukált – azaz invertálható –, ha a relatív prím m-hez.

Ha [a]_m=[b]_m, akkor az (a,m) és (b,m) kitüntetett közös osztók egymás asszociáltjai, azaz (a,m)\sim (b,m). Emiatt teljesen mindegy, hogy a vizsgált maradékosztályt melyik elemével reprezentáljuk, ugyanis vagy mindegyik eleme relatív prím lesz a modulushoz, vagy egyik sem.

Megnézem a tudásbázisban

♣

Bizonyítás:

Az [a]_m maradékosztály a 20.6. Definíció alapján pontosan akkor redukált, ha invertálható, azaz létezik pontosan egy olyan X=[x]_m maradékosztály, amelyre teljesül az alábbi:

[a]_m\odot X=[a]_m\odot [x]_m=[a\cdot x]_m=[1]_m

Ez pontosan az alábbi lineáris kongruencia egyértelmű megoldhatóságát jelenti:

ax\equiv 1\pmod m

Ez viszont a 20.13. Tétel szerint akkor és csak akkor oldható meg, ha teljesül az (a,m)|1 oszthatóság. Ez a 16.5. Tétel alapján azt jelenti, hogy az (a,m) kitüntetett közös osztó egység, ami a 17.10. Definíció utáni megjegyzés szerint épp azt jelenti, hogy a relatív prím az m modulushoz, azaz

(a,m)\sim 1

Válasszuk a pozitív egységet kitüntetett közös osztónak, azaz legyen (a,m)=1. Ebben az esetben a lineáris kongruencia megoldásainak száma a 20.14. Tétel értelmében 1, azaz a megoldás egyértelmű.

Most igazoljuk a tétel másik állítását, miszerint bármely maradékosztály összes elemének asszociáltság erejéig ugyanaz az m modulussal vett kitüntetett közös osztója. Az [a]_m=[b]_m egyenlőség azt jelenti, hogy a ugyanabban a maradékosztályban van, mint b. Így tehát a 20.4. Tétel alapján a b egész szám felírható az alábbi alakban valamilyen alkalmas k_1 egész szám segítségével:

b=k_1m+a

Mivel az (a,m) kitüntetett közös osztó osztója a-nak és m-nek, ezért a 16.2. Tétel 7. és 6. pontja miatt osztója k_1m+a=b-nek is. Így tehát (a,m) közös osztója b-nek és m-nek, vagyis a 17.4. Definíció alapján osztója ezek kitüntetett közös osztójának, azaz teljesül az (a,m)|(b,m) oszthatóság.

Ugyanígy a 20.4. Tétel alapján az a egész szám is felírható az alábbi alakban valamilyen alkalmas k_2 egész szám segítségével:

a=k_2m+b

Ebből az előző gondolatmenetet megismételve azt fogjuk kapni, hogy teljesül a (b,m)|(a,m) oszthatóság. Minthogy mindkét irányban fennáll az oszthatóság (a,m) és (b,m) között, ezért a 16.9. Tétel miatt:

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

Speciálisan ha a relatív prím m-hez, akkor (a,m) egység, és így az asszociáltság miatt (b,m) is egység, azaz b is relatív prím m-hez.

Megnézem a tudásbázisban

∎

Az Euler-féle \varphi-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.

20.16. Definíció (Teljes és redukált maradékrendszerek):

Legyen m\gt 0 egy pozitív egész szám. Ha minden modulo m maradékosztályból pontosan egy elemet kiválasztunk, akkor az így kapott számhalmazt modulo m teljes maradékrendszernek nevezzük.

Ehhez hasonlóan ha minden modulo m redukált maradékosztályból pontosan egy elemet kiválasztunk, akkor az így kapott számhalmazt modulo m redukált maradékrendszernek nevezzük.

Megnézem a tudásbázisban

♣

A 20.6. ábrán a \Z/8\Z-ben lévő modulo 8 maradékosztályok láthatók, illetve egy-egy belőlük képzett teljes és redukált maradékrendszer. Előbbit T-vel, utóbbit pedig R-rel jelöltük. Látható, hogy a T halmaz minden maradékosztályból, az R halmaz pedig minden redukált maradékosztályból pontosan egy elemet tartalmaz.

Modulo 8 teljes és redukált maradékrendszerek
20.6. ábra: Modulo 8 teljes és redukált maradékrendszerek

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.

20.17. Tétel:

Legyen m\gt 0 tetszőleges pozitív egész szám. Ekkor teljesülnek az alábbiak:

1.
Egy egész számokból álló S halmaz akkor és csak akkor alkot modulo m teljes maradékrendszert, ha elemeinek száma m, és tetszőleges a,b\in S elemek esetén
a\ \cancel{\equiv}\ b\pmod m
2.
Az S halmaz akkor és csak akkor alkot modulo m redukált maradékrendszert, ha elemeinek száma \varphi(m), minden a\in S relatív prím m-hez, továbbá tetszőleges a,b\in S elemek esetén
a\ \cancel{\equiv}\ b\pmod m

Megnézem a tudásbázisban

♣

Bizonyítás:

Az 1. állítás: Tegyük fel, hogy S egy modulo m teljes maradékrendszer. Mivel a modulo m maradékosztályok száma a 20.4. Tétel alapján m, és S minden maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen m. Továbbá S elemei páronként inkongruensek modulo m, hiszen mindegyik különböző maradékosztályból származik.

Visszafelé: Tegyük fel, hogy az S halmaz m darab páronként inkongruens számot tartalmaz. Ekkor a páronkénti inkongruencia miatt ezek mindegyike különböző maradékosztályokba tartozik. Továbbá mivel a számuk m, ezért m darab maradékosztályt reprezentálnak, azaz a 20.4. Tétel alapján az összeset. Az S halmaz tehát valóban egy modulo m teljes maradékrendszer.

A 2. állítás: Tegyük fel, hogy S egy modulo m redukált maradékrendszer. Mivel a modulo m redukált maradékosztályok száma a 20.7. Definíció alapján \varphi(m), és S minden redukált maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen \varphi(m). Továbbá S elemei páronként inkongruensek modulo m, hiszen mindegyik különböző redukált maradékosztályból származik. Végül S minden eleme relatív prím m-hez, hiszen ezeket redukált maradékosztályokból választottuk ki, márpedig a 20.15. Tétel alapján egy redukált maradékosztálynak minden eleme relatív prím m-hez.

Visszafelé: Tegyük fel, hogy az S halmaz \varphi(m) darab páronként inkongruens számot tartalmaz, amelyek mindegyike relatív prím m-hez. Ekkor a páronkénti inkongruencia miatt ezek mindegyike különböző maradékosztályokba tartozik, amelyek mindegyike az m-hez való relatív prímség miatt redukált maradékosztály. Továbbá mivel a számuk \varphi(m), ezért \varphi(m) darab redukált maradékosztályt reprezentálnak, azaz a 20.7. Definíció alapján az összeset. Az S halmaz tehát valóban egy modulo m redukált maradékrendszer.

Megnézem a tudásbázisban

∎

E tétel egyik alkalmazásaként most egy alternatív definíciót is adunk az Euler-féle \varphi-függvényre.

20.18. Következmény:

Legyen m\gt 0 tetszőleges pozitív egész szám. Ekkor az Euler-féle \varphi-függvény a 0, 1, 2, ..., m-1 egész számok közül az m-hez relatív prímek számát adja meg.

Megnézem a tudásbázisban

♣

Bizonyítás:

A 18.3. Definíció utáni megjegyzés 5. pontja alapján a \bmod_m maradékképző függvény a 0, 1, 2, ..., m-1 egész számokhoz mind különböző modulo m maradékot rendel. Így a 20.1. Tétel 1. pontja alapján ezek a számok páronként inkongruensek. Továbbá, mivel a számuk épp m, ezért a 20.17. Tétel 1. pontja alapján ők egy modulo m teljes maradékrendszert alkotnak.

Mivel ez egy teljes maradékrendszer, ezért tartalmazza egy-egy reprezentánsát minden modulo m maradékosztálynak, így a redukált maradékosztályoknak is. Ez utóbbiak viszont biztosan mind relatív prímek m-hez, hiszen az általuk reprezentált redukált maradékosztályok a 20.17. Tétel 2. pontja alapján csupa m-hez relatív prím elemekből állnak.

A 20.7. Definíció szerint az Euler-féle \varphi-függvény a modulo m redukált maradékosztályok számát adja meg. A fentiek alapján ez a szám valóban meg fog egyezni azon egészek számával, amelyek 0, 1, 2, ..., m-1 teljes maradékrendszer elemei közül relatív prímek m-hez.

Megnézem a tudásbázisban

∎

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.19. Tétel:

Legyen b tetszőleges, m\gt 0 valamilyen pozitív, a pedig egy m-hez relatív prím egész szám. Ekkor teljesülnek az alábbiak:

1.
Amennyiben az r_1, r_2, ..., r_{m} egész számok egy modulo m teljes maradékrendszert alkotnak, akkor az alábbi számok is:
ar_1+b,\ ar_2+b,\ \ldots,\ ar_{m}+b
2.
Amennyiben az s_1, s_2, ..., s_{\varphi(m)} egész számok egy modulo m redukált maradékrendszert alkotnak, akkor az alábbi számok is:
as_1,\ as_2,\ \ldots,\ as_{\varphi(m)}

Megnézem a tudásbázisban

♣

Bizonyítás:

Az 1. állítás: Mivel az új számhalmaz elemszáma is m, ezért a 20.17. Tétel 1. pontja alapján elegendő a páronkénti inkongruenciát ellenőrizni. Legyen tehát ar_i+b és ar_j+b az új számhalmaz két tetszőleges, egymástól különböző eleme, és tegyük fel indirekt, hogy ezek között mégis fennáll az alábbi kongruencia:

ar_i+b\equiv ar_j+b\pmod m

A 20.2. Tétel 5. pontja alapján mindkét oldalból kivonhatunk b-t. Így az alábbit kapjuk:

ar_i\equiv ar_j\pmod m

Mivel a-ról azt mondtuk, hogy relatív prím m-hez, így a 20.3. Tétel utáni megjegyzés alapján a-val egyszerűsíthetjük mindkét oldalt a modulus változatlanul hagyása mellett:

r_i\equiv r_j\pmod m

Mivel az eredeti teljes maradékrendszer elemei páronként inkongruensek modulo m, így ez csak akkor lehetséges, ha r_i=r_j. Ebből viszont az következik, hogy az ar_i+b=ar_j+b egyenlőség is szükségképpen fennáll, vagyis indirekt feltételezésünkkel ellentétben az új számhalmaz két kiválasztott eleme mégis megegyezik.

A 2. állítás: Mivel az új számhalmaz elemszáma is \varphi(m), ezért a 20.17. Tétel 2. pontja alapján elegendő a páronkénti inkongruenciát, valamint az m-hez való relatív prímséget ellenőrizni. Kezdjük az előbbivel. Legyen tehát as_i és as_j az új számhalmaz két tetszőleges, egymástól különböző eleme, és tegyük fel indirekt, hogy ezek között mégis fennáll az alábbi kongruencia:

as_i\equiv as_j\pmod m

Innentől a páronkénti inkongruencia az előzővel szinte teljesen megegyező gondolatmenet alapján adódik.

Azt kell még megmutatni, hogy az új számhalmaz minden as_i eleme relatív prím m-hez. Azt ugye a tétel szövegéből tudjuk, hogy a relatív prím m-hez. Továbbá s_i is relatív prím m-hez, mivel ő az eredeti redukált maradékrendszer egyik eleme. Azt kell igazolni, hogy ekkor az as_i szorzat is relatív prím m-hez.

Tegyük fel indirekt, hogy nem ez a helyzet, ami a 17.10. Definíció alapján azt jelenti, hogy as_i-nek és m-nek létezik olyan d közös osztója, ami nem egység. Továbbá a 0 sem lehet, hiszen ez azt jelentené, hogy teljesül a 0|m oszthatóság, vagyis a 16.2. Tétel 4. pontja miatt m=0 lenne, ami ellentmond a tétel szövegének, miszerint m\gt 0.

Mármost ha a d közös osztó, ami nem 0 és nem is egység, akkor – mivel a 17.23. Tétel alapján \Z-ben teljesül a számelmélet alaptétele – ő a 16.16. Definíció alapján felbontható prímtényezők szorzatára. Létezik tehát olyan p prím, amely osztója d-nek, és így az oszthatóság tranzitivitása miatt as_i-nek és m-nek is. Azaz létezik olyan p prím, hogy:

\begin{aligned} p&|as_i \\ p&|m \end{aligned}

Mivel p prím, ezért a 16.13. Definíció alapján két eset lehetséges. Első esetben teljesül a p|a oszthatóság is, ami lehetetlen, hiszen p|m miatt ekkor p közös osztója a-nak és m-nek, ami ellentmond a tétel szövegének, miszerint a relatív prím m-hez. Második esetben pedig teljesül a p|s_i oszthatóság, ami ugyancsak lehetetlen, hiszen p|m miatt ekkor p közös osztója s_i-nek és m-nek. Ez viszont ellentmond annak a fentebb már bizonyított ténynek, hogy s_i relatív prím m-hez.

Megnézem a tudásbázisban

∎

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.

20.20. Tétel:

Legyen m\gt 0 tetszőleges pozitív, a pedig egy m-hez relatív prím egész szám. Ekkor teljesül az alábbi kongruencia:

a^{\varphi(m)} \equiv 1\pmod m

Itt \varphi a 20.7. Definíció szerinti Euler-féle \varphi-függvényt jelöli, az a^{\varphi(m)} kifejezés alatt pedig a 18.8. Tétel szerinti hatványozást értjük.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tekintsünk egy tetszőleges R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} modulo m redukált maradékrendszert. Mivel a relatív prím m-hez, ezért a 20.19. Tétel 2. pontja alapján az S=\{ar_1; ar_2; \ldots; ar_{\varphi(m)}\} számhalmaz is egy modulo m redukált maradékrendszer.

Ez a 20.16. Definíció szerint azt jelenti, hogy mindkét számhalmaz tartalmaz egy-egy reprezentánselemet az összes létező redukált maradékosztályból. Tehát az S halmazban minden ar_i elemnek van egy r_j párja az R halmazban, amely ugyanannak a redukált maradékosztálynak a reprezentánseleme, vagyis vele kongruens modulo m. Most átmenetileg nevezzük át az R elemeit úgy, hogy az ar_i ilyen értelemben vett párját jelöljük s_i-vel.

Ebből tehát \varphi(m) darab kongruenciát lehet felírni, ahol a baloldalon az S, míg a jobboldalon – a most bevezetett jelölésekkel – az R halmaz elemei szerepelnek:

\begin{aligned} ar_1&\equiv s_1\pmod m \\ ar_2&\equiv s_2\pmod m \\ ar_3&\equiv s_3\pmod m \\ &\vdots \\ ar_{\varphi(m)}&\equiv s_{\varphi(m)}\pmod m \end{aligned}

A 20.2. Tétel 4. alapján ez a \varphi(m) darab kongruencia összeszorozható egymással:

\underbrace{aa \ldots a}_{\varphi(m)\ \text{darab}} \cdot r_1r_2\ldots r_{\varphi(m)} \equiv s_1s_2\ldots s_{\varphi(m)} \pmod m

A jobboldalon tehát az R halmaz elemei szerepelnek, csak épp átmenetileg az s_1, s_2, ..., s_{\varphi(m)} nevekkel láttuk el őket. Az eredeti neveikkel szerepeltetve és az eszerinti indexelés alapján sorbarendezve őket az előbbi kongruencia tulajdonképpen így néz ki:

a^{\varphi(m)} \cdot r_1r_2\ldots r_{\varphi(m)} \equiv r_1r_2\ldots r_{\varphi(m)} \pmod m

Mivel az R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} számhalmaz egy modulo m redukált maradékrendszer, ezért a 20.17. Tétel 2. pontja alapján minden eleme relatív prím m-hez. Emiatt a fenti kongruenciát a 20.3. Tétel utáni megjegyzés alapján ezekkel az elemekkel mind egyszerűsíthetjük, megkapva így a tétel állítását:

a^{\varphi(m)} \equiv 1\pmod m

Megnézem a tudásbázisban

∎

Alkalmazzuk az iménti tételt például az m=8 modulusra és hozzá relatív prím a=5-re. Ekkor a kongruencia baloldala így néz ki:

a^{\varphi(m)}=5^{\varphi(8)}=5^4=625

Ez 8-cal osztva valóban 1-et ad maradékul.

Az, hogy a tételben szereplő a relatív prím az m modulushoz a 20.15. Tétel alapján egyben azt is jelenti, hogy ő egy modulo m redukált maradékosztály reprezentánseleme. Emiatt az a^{\varphi(m)}\equiv 1\pmod m kongruencia a 20.5. szakasz végén leírtakhoz hasonló gondolatmenetet követve az alábbi egyenletnek felel meg a \Z/m\Z maradékosztálygyűrűben:

([a]_m)^{\varphi(m)} = [1]_m

Az Euler-Fermat tétel tehát tulajdonképpen azt mondja, hogy a \Z/m\Z 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 \varphi(m)-edik hatványra emelve mindig az [1]_m maradékosztályt, vagyis a \Z/m\Z 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 a relatív prím az m 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.

20.21. Tétel:

Legyen m\gt 0 tetszőleges pozitív, a pedig egy tetszőleges egész szám. Tegyük fel továbbá, hogy létezik olyan k\gt 0 szintén pozitív kitevő, amelyre teljesül az alábbi kongruencia:

a^k\equiv 1\pmod m

Ekkor a relatív prím m-hez.

Itt az a^k kifejezés alatt a 18.8. Tétel szerinti hatványozást értjük.

Megnézem a tudásbázisban

♣

Megjegyzés:

A tétel tehát bármilyen pozitív k kitevő esetén működik, annak nem kell kimondottan \varphi(m)-nek lennie. Amennyiben ilyen pozitív k kitevő létezik, akkor abból már következik, hogy a relatív prím m-hez. Ezért ez az Euler-Fermat tétel megfordításánál valóban egy erősebb állítás.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tekintsük az alábbi lineáris kongruenciát:

ax\equiv 1\pmod m

Amennyiben ennek a lineáris kongruenciának létezne megoldása, akkor a 20.13. Tétel értelmében teljesülne az (a,m)|1 oszthatóság. Minthogy az 1 egész szám a \Z gyűrű egységeleme, így ez az oszthatóság a 16.5. Tétel miatt csak abban az esetben teljesülhetne, ha (a,m) egység lenne. Ez viszont a 17.10. Definíció utáni megjegyzés alapján azt jelentené, hogy a relatív prím m-hez.

Márpedig amennyiben létezik a tételben szereplő pozitív k kitevő, akkor a fenti lineáris kongruenciának létezik megoldása. Ha például k\gt 1, akkor a tételben szereplő kongruencia a 18.8. Tétel 3. pontja miatt így írható fel:

a\cdot \underbrace{a^{k-1}}_{=x}\equiv 1\pmod m

Ebben az esetben tehát x=a^{k-1} lesz a megoldás.

Ha pedig a k=1, akkor pedig a kongruencia így írható fel:

a\cdot \underbrace{1}_{=x}\equiv 1\pmod m

Ebben az esetben tehát x=1 lesz a megoldás.

Minthogy minden pozitív esetet lefedtünk, ezért a bizonyítás elején felvázolt gondolatmenet alapján a valóban relatív prím m-hez, amennyiben a kritériumnak megfelelő k kitevő létezik.

Megnézem a tudásbázisban

∎

Ebben a fejezetben tehát megvizsgáltuk, hogy a 18. fejezetben bevezetett kongruencia fogalma mit jelent az egész számok \Z 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 \varphi-függvénnyel, amely a modulo m 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 \varphi-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.