youproof.orgDeep Math. Human Access.
Ókori filozófus márványszobra

Episode I

Alice és Bob

17. fejezet

Alice és Bob ókori haverja

Az előző fejezetben megismerkedtünk a legfontosabb számelméleti fogalmakkal: oszthatóság, egység, asszociált, felbonthatatlan és prímtulajdonságú elemek. Ezután ismertettük a számelmélet alaptételét, amely azt biztosítja egy integritástartományban, hogy annak minden – nemnulla és nem egység – elemét egyértelműen elő lehessen állítani felbonthatatlan elemek szorzataként. Megemlítettük, hogy ez nem minden integritástartományban teljesül. Végül megmutattuk, hogy ha viszont teljesül, akkor a felbonthatatlanok és a prímek fogalma szükségképpen egybe kell essen. Azt is megemlítettük ugyanakkor, hogy ez csupán szükséges, de nem elégséges feltétel az alaptétel teljesüléséhez.

De vajon milyen elégséges feltételt tudunk mutatni erre vonatkozóan? Az egész számok gyűrűje teljesíti-e ezt a kritériumot? Mit jelent a "legnagyobb közös osztó" fogalma és hogyan lehet villámgyorsan kiszámolni az úgynevezett euklidészi algoritmus segítségével? Mit tudunk mondani erről általános integritástartományokra? Mik azok az euklidészi gyűrűk és mi közük a számelmélet alaptételéhez? Ebben a fejezetben erről lesz szó...

Figyelem! Ez a fejezet erőteljesen épít az előző fejezetben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:

Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni az előző fejezetet, mivel gyakran hivatkozni fogunk rájuk.

A modern kriptográfiai eljárások szempontjából alapvető fontosságú, hogy az egész számok gyűrűjében teljesüljön a számelmélet alaptétele. Egyrészt ez teszi lehetővé, hogy minden egész szám egyértelműen előáll az úgynevezett "prímszámok" – amelyek tehát a Z\Z gyűrű felbonthatatlan elemei – szorzataként, és így a számelméleti kapcsolatot biztosítja a publikus és a titkos kulcsok között ezekben az eljárásokban. Másrészt a prímtényezős felbontás feladatának algoritmikus nehézsége biztosítja azt, hogy egy támadó számára beláthatatlanul sok ideig tartson kiszámítani a titkos kulcsot a hozzá tartozó publikus kulcsból. Ezért ebben a fejezetben alapvető célunk annak igazolása, hogy Z\Z gyűrűben valóban teljesül a számelmélet alaptétele.

Ennek keretében meg fogunk ismerkedni egy ókorból származó eljárással, az "euklidészi algoritmussal". Ennek segítségével két egész szám úgynevezett "legnagyobb közös osztóját" fogjuk tudni elképesztően hatékonyan kiszámítani. Ez az eljárás a továbbiakban is fontos lesz számunkra, mivel mind az RSA-ban, mind pedig a nagy prímszámok keresését lehetővé tévő úgynevezett "prímtesztelési eljárásokban" alapvető szerepet játszik. Ezután ezt az eljárást fogjuk általánosítani oly módon, hogy ne csak az egész számok gyűrűjén, hanem minden olyan integritástartományon működjön, amely bizonyos kritériumoknak eleget tesz. Ezeket "euklidészi gyűrűknek" fogjuk nevezni. Végül megmutatjuk, hogy minden euklidészi gyűrűben – és így speciálisan az egész számok gyűrűjében is – teljesül a számelmélet alaptétele.

17.1A legnagyobb közös osztó

Először is tisztázzuk, hogy mit értünk két egész szám "legnagyobb közös osztóján". Tegyük fel, hogy aa és bb valamilyen egész számok. Azt mondjuk, hogy a cc egész szám aa és bb "közös osztója", ha egyidejűleg teljesülnek a c∣ac|a és c∣bc|b oszthatóságok. Például a 1818 és 2424 közös osztói az 11, 22, 33 és 66 egész számok, valamint ezek ellentettjei. A "legnagyobb közös osztó" alatt értelemszerűen ezek közül a legnagyobbat, azaz a 66 egész számot értjük. Általánosságban az aa és bb egész számok "legnagyobb közös osztóját" (a,b)(a,b)-vel szoktuk jelölni. Az iménti példában tehát (18,24)=6(18,24)=6.

A "legnagyobb közös osztó" definícióját a fentiek alapján tehát a következőképpen adjuk meg.

17.1. Definíció (Legnagyobb közös osztó):

Tegyük fel, hogy aa és bb tetszőleges egész számok a Z\Z gyűrűben. Az aa és bb legnagyobb közös osztója a dd egész szám, ha teljesül az alábbi két tulajdonság:

1.
Teljesülnek a d∣ad|a és d∣bd|b oszthatóságok, azaz dd közös osztó.
2.
Tetszőleges cc egész szám esetén ha fennállnak a c∣ac|a és c∣bc|b oszthatóságok, akkor c≤dc\leq d.

Azaz a legnagyobb közös osztónál nincs nagyobb közös osztó. Az aa és bb egész számok legnagyobb közös osztójának jelölése: (a,b)(a,b).

Megnézem a tudásbázisban

♣

Megjegyzés:

A definícióból következik, hogy a=b=0a=b=0 esetén nem létezik az (a,b)(a,b) legnagyobb közös osztó, hiszen a 16.2. Tétel 3. pontja alapján a 00-nak minden egész szám osztója, így közöttük nincs legnagyobb.

Megnézem a tudásbázisban

♣

Kérdés, hogy az iménti megjegyzésben közölt eseten kívül vajon minden más esetben létezik-e a legnagyobb közös osztó. Ennek igazolásához először ismertetünk egy segédtételt.

17.2. Lemma:

Ha aa és 0<b0\lt b tetszőleges egész számok, akkor az a∣ba|b oszthatóságból következik, hogy a≤ba\leq b. Azaz tetszőleges pozitív egész szám legalább akkora, mint bármely osztója.

Megnézem a tudásbázisban

♣

Bizonyítás:

Az biztos, hogy a≠0a\neq 0, hiszen máskülönben b=0b=0 lenne a 16.2. Tétel 4. pontja miatt. A rendezési reláció trichotómiájából, valamint a≠0a\neq 0-ból következően a<0a\lt 0 vagy a>0a\gt 0 közül pontosan az egyik teljesül. Az a<0a\lt 0 esettel nem kell különösebben foglalkoznunk, hiszen ekkor 0<b0\lt b miatt nyilván következik a≤ba\leq b a rendezési reláció tranzitivitása miatt.

Nézzük tehát a 0<a0\lt a esetet. A 16.1. Definíció alapján a a∣ba|b oszthatóság azt jelenti, hogy létezik olyan kk egész szám, amelyre teljesül az alábbi egyenlet:

ak=bak = b

A 13.11. Definíció szerinti pozitív és negatív egész számok, valamint a 00 a 13.10. Tétel értelmében lefedik a teljes Z\Z halmazt. Emiatt az egészek szorzásának 14.3. Definíciója alapján egy szorzat előjele az alábbiak szerint alakulhat a tényezők előjelének függvényében:

+⋅+=++⋅−=−−⋅+=−−⋅−=+\begin{aligned} +\cdot + &= + \\ +\cdot - &= - \\ -\cdot + &= - \\ -\cdot - &= + \end{aligned}

Mivel a fenti egyenletben aa is és bb is pozitív, ezért szükségképpen kk is pozitív kell legyen, azaz 0<k0\lt k. Továbbá az egyenlet a disztributivitási szabályok miatt átalakítható a következőképpen:

ak=a(1+k−1)=a+a(k−1)=bak=a(1+k-1)=a+a(k-1)=b

Itt az a(k−1)a(k-1) szorzatról elmondhatjuk, hogy pozitív, vagy pedig 00, hiszen aa ugye pozitív, k−1k-1 pedig pozitív vagy 00. Létezik tehát olyan nemnegatív egész szám, amelyet aa-hoz adva bb-t kapunk, nevezetesen az a(k−1)a(k-1). Ez viszont a 15.18. Tételben szereplő ≤\leq reláció definíciója miatt épp azt jelenti, hogy a≤ba\leq b.

Megnézem a tudásbázisban

∎

Ennek a segédtételnek a felhasználásával mostmár könnyen meg tudjuk mutatni, hogy a Z\Z gyűrűben mindig létezik aa és bb legnagyobb közös osztója, amennyiben legalább az egyikük nem 00.

17.3. Tétel:

Ha aa és bb tetszőleges egész szám, és közülük legalább az egyik nem 00, akkor létezik az (a,b)(a,b) legnagyobb közös osztó.

Megnézem a tudásbázisban

♣

Bizonyítás:

Először azt mutatjuk meg, hogy egy tetszőleges n≠0n\neq 0 egész számnak mindig véges sok osztója van. Elegendő azt az esetet vizsgálni, amikor nn pozitív. Ha ugyanis nn negatív, akkor egyrészt a 15.9. Lemma 1. pontja miatt az ellentettje pozitív lenne, amely a 16.8. Tétel 1. pontja alapján nn asszociáltja lenne, azaz pontosan ugyanazok lennének az osztói, mint nn-nek.

Az általánosság megsértése nélkül feltehetjük tehát, hogy 0<n0\lt n. A 17.2. Lemma miatt ekkor nn egyetlen osztója sem lehet nagyobb nn-nél. Ebből következik, hogy nn-nek legfeljebb nn darab pozitív osztója lehet. A 16.2. Tétel 8. pontja miatt ekkor azonban ezek ellentettjei is osztók, amelyek a 15.9. Lemma 1. pontja alapján mind negatívak lennének.

Tekintve, hogy a pozitív és negatív egész számok a 00-val együtt lefedik a teljes Z\Z halmazt, valamint a 16.2. Tétel 4. pontja miatt 0∤n0 \nmid n, ezért nn-nek biztosan nincs ezeken kívül több osztója, így azok száma biztosan nem több 2n2n-nél – azaz valóban véges. Ebből azonnal következik, hogy a tételben szereplő aa és bb egész számok közös osztóinak száma is legfeljebb 2n2n, azaz szintén véges.

Igaz továbbá, hogy az 11 minden egész számnak osztója, hiszen ő a Z\Z gyűrű egységeleme, és így a 16.3. Definíció utáni megjegyzés alapján egyúttal egység is. Az aa és bb közös osztóinak halmaza tehát – azonkívül, hogy véges – nem üres, így biztosan van az elemei között legnagyobb. A legnagyobb közös osztó tehát valóban létezik.

Megnézem a tudásbázisban

∎

A legnagyobb közös osztó definíciójával azonban van egy kis probléma. Nevezetesen: felhasználtuk hozzá az egész számok gyűrűjének rendezési relációját. Mi azonban szeretnénk ezt a fogalmat tetszőleges integritástartományokra kiterjeszteni. Ugyanakkor nem szeretnénk csak a definíció kedvéért megkövetelni valamiféle rendezési reláció létezését. Ráadásul a 15.4. szakaszban megemlítettük, hogy bizonyos gyűrűk egyáltalán nem, mások pedig akár végtelen sokféleképpen rendezhetők. Ez utóbbi esetben például nem is lenne egyértelmű, hogy melyik rendezés szerinti legnagyobb közös osztóról beszélünk.

17.2A kitüntetett közös osztó

A most következő definícióban általánosítani fogjuk a legnagyobb közös osztó fogalmát, amely így már tetszőleges integritástartományra átvihető lesz rendezési reláció nélkül is.

17.4. Definíció (Kitüntetett közös osztó):

Tegyük fel, hogy aa és bb egy valamilyen RR integritástartomány tetszőleges elemei. Az aa és bb elemek kitüntetett közös osztója a dd elem, ha teljesül az alábbi két tulajdonság:

1.
Teljesülnek a d∣ad|a és d∣bd|b oszthatóságok, azaz dd közös osztó.
2.
Tetszőleges cc elem esetén ha fennállnak a c∣ac|a és c∣bc|b oszthatóságok, akkor fennáll a c∣dc|d oszthatóság is.

Azaz a kitüntetett közös osztó minden közös osztónak többszöröse. Az aa és bb elemek kitüntetett közös osztójának jelölése: (a,b)(a,b).

Megnézem a tudásbázisban

♣

Felhívjuk a figyelmet, hogy a legnagyobb közös osztóval ellentétben kitüntetett közös osztóból létezhet több is. Például a 17.1. szakasz elején közölt példában szereplő 2424 és 1818 egész számoknak a 66-on kívül a −6-6 is kitüntetett közös osztója. Szerencsére ez nem fog gondot okozni, mivel az alábbi tétel biztosít egyfajta "egyértelműséget" a kitüntetett közös osztóra.

17.5. Tétel (A kitüntetett közös osztó egyértelműsége):

Ha egy RR integritástartományban valamely aa és bb elemeknek létezik kitüntetett közös osztója, akkor az asszociáltságtól eltekintve egyértelmű.

Azaz egyrészt egy kitüntetett közös osztó bármely asszociáltja is kitüntetett közös osztó, másrészt pedig bármely két kitüntetett közös osztó szükségképpen egymás asszociáltja.

Megnézem a tudásbázisban

♣

Megjegyzés:

Emiatt a kitüntetett közös osztók közötti azonosságokat leíró kifejezésekben egyenlőségjel helyett általában a ∼\sim szimbólumot fogjuk használni a továbbiakban, ami a 16.6. Definíció szerinti asszociáltságot jelenti. Ezalól csak azok az esetek képeznek kivételt, amikor két kitüntetett közös osztóról kimondottan azt állítjuk, hogy ténylegesen is megegyeznek.

Megnézem a tudásbázisban

♣

Bizonyítás:

Egyrészt: Tegyük fel, hogy d1d_1 kitüntetett közös osztója aa-nak és bb-nek, valamint d2d_2-re teljesül, hogy d1∼d2d_1 \sim d_2 – azaz d1d_1 és d2d_2 egymás asszociáltjai. Azt kell megmutatni, hogy ekkor d2d_2 is kitüntetett közös osztója aa-nak és bb-nek. Az asszociáltság 16.6. Definíciója alapján d2d_2-nek pontosan ugyanazok az osztói, mint d1d_1-nek. Emiatt, mivel d1d_1-nek osztója az összes közös osztó – hiszen kitüntetett –, ezért d2d_2-nek is, és így ő is kitüntetett.

Másrészt: Most tegyük fel, hogy d1d_1 és d2d_2 is kitüntetett közös osztója aa-nak és bb-nek. Azt kell megmutatni, hogy ekkor d1∼d2d_1 \sim d_2 – azaz d1d_1 és d2d_2 egymás asszociáltjai. Mivel d1d_1 közös osztó, ezért osztója d2d_2-nek, hiszen d2d_2 ugye kitüntetett. Fordítva: mivel d2d_2 közös osztó, ezért osztója d1d_1-nek, hiszen d1d_1 is kitüntetett. A két kitüntetett közös osztó tehát kölcsönösen osztói egymásnak, és így a 16.9. Tétel értelmében ők egymás asszociáltjai.

Megnézem a tudásbázisban

∎

A definícióból azonnal következnek az alábbi egyszerű állítások.

17.6. Tétel (A kitüntetett közös osztó tulajdonságai):

Tegyük fel, hogy aa és bb egy valamilyen RR integritástartomány tetszőleges elemei. Ekkor igazak az alábbiak:

1.
(a,b)∼(b,a)(a,b)\sim (b,a).
2.
(a,b)∼a(a,b)\sim a akkor és csak akkor, ha a∣ba|b.
3.
(a,a)∼a(a,a)\sim a.
4.
(a,0)∼a(a,0)\sim a.
5.
(0,0)=0(0,0)=0.

Megnézem a tudásbázisban

♣

Bizonyítás:

1. tulajdonság: Az aa és bb közös osztóinak halmaza nyilván nem változik, ha a pozíciójukat felcseréljük az (a,b)(a,b) kifejezésben, így a kitüntetett közös osztók halmaza sem.

2. tulajdonság: Tegyük fel, hogy a∣ba|b. Mivel a∣aa|a is teljesül a 16.2. Tétel 1. pontja miatt, így aa közös osztó. Továbbá ha tekintünk egy tetszőleges cc közös osztót, akkor nyilván teljesül a c∣ac|a oszthatóság, és így aa kitüntetett közös osztó. Visszafelé: (a,b)∼a(a,b)\sim a azt jelenti, hogy aa kitüntetett közös osztó, és így közös osztó, azaz teljesül az a∣ba|b oszthatóság.

3. tulajdonság: Tekintve, hogy a 16.2. Tétel 1. pontja alapján minden elem osztója önmagának – beleértve aa-t is –, így ez a 2. tulajdonság speciális esete, amikoris b=ab=a.

4. tulajdonság: Tekintve, hogy a 16.2. Tétel 3. pontja alapján minden elem osztója a nullelemnek – beleértve aa-t is –, így ez a 2. tulajdonság speciális esete, amikoris b=0b=0.

5. tulajdonság: Ez a 4. tulajdonság speciális esete, amikoris a=0a=0. A ∼\sim szimbólum helyetti egyenlőségjel azért indokolt, mivel a 16.8. Tétel 3. pontja alapján a 00 csak önnmagának asszociáltja.

Megnézem a tudásbázisban

∎

Jogosan merülhet fel a kérdés az Olvasóban, hogy miért használtuk ugyanazt a jelölést a kitüntetett és a legnagyobb közös osztó esetén, amikor ezek látszólag teljesen különböző fogalmak. Ennek tisztázása érdekében most megmutatjuk, hogy ha két egész számnak egyáltalán létezik kitüntetett közös osztója, akkor az csak a legnagyobb közös osztó valamelyik asszociáltja lehet.

17.7. Tétel:

Tegyük fel, hogy a dd egész szám valamely aa és bb egész számok legnagyobb közös osztója. Tegyük fel továbbá, hogy aa-nak és bb-nek létezik legalább egy kitüntetett közös osztója, amelyet jelöljünk most ee-vel. Ekkor dd és ee egymás asszociáltjai, és így a 17.5. Tétel értelmében dd is kitüntetett közös osztó.

Megnézem a tudásbázisban

♣

Bizonyítás:

Biztos, hogy aa és bb közül legalább az egyik nem 00, máskülönben a 17.1. Definíció utáni megjegyzés alapján nem létezhetne a dd legnagyobb közös osztó. Ebből viszont következik, hogy a feltételezett ee kitüntetett közös osztó biztosan nem 00, hiszen a 16.2. Tétel 4. pontja miatt a 00 csak saját magának osztója, és így nem lehetne közös osztója aa-nak és bb-nek. Így tehát ee az egész számok rendezésének trichotómiája miatt vagy pozitív, vagy pedig negatív.

Legyen f=ef=e, ha ee pozitív, és f=−ef=-e ha ee negatív. Ekkor egyrészt a 15.9. Lemma 1. pontja miatt ff biztosan pozitív, másrészt pedig ee-nek asszociáltja – vagy azért, mert megegyezik vele, vagy pedig a 16.8. Tétel 1. pontja miatt. Ebből viszont a 17.5. Tétel miatt következik, hogy ff is kitüntetett közös osztó.

Mivel ff közös osztó, és dd a legnagyobb közös osztó, ezért egyrészt teljesül az f≤df\leq d reláció. Másrészt mivel dd szintén közös osztó, és ff kitüntetett, ezért teljesül a d∣fd|f oszthatóság is. Ekkor azonban 0<f0\lt f miatt alkalmazható a 17.2. Lemma, ami alapján teljesül a d≤fd\leq f reláció is.

Minthogy f≤df\leq d és d≤fd\leq f egyszerre teljesül, ezért a ≤\leq reláció antiszimmetriája miatt d=fd=f. Azaz dd valóban asszociáltja a tételben szereplő ee kitüntetett közös osztónak, és így a 17.5. Tétel értelmében ő maga is kitüntetett közös osztó.

Megnézem a tudásbázisban

∎

Ez mind szép és jó, azonban vigyázzunk! Ez a tétel csak annyit garantál, hogy ha valamely egész számoknak létezik kitüntetett közös osztója, akkor e számok legnagyobb közös osztója is rendelkezni fog a 17.4. Definíció szereplő "kitüntetett" tulajdonsággal – azaz, hogy ő többszöröse bármely közös osztónak. A legnagyobb közös osztó a 17.3. Tétel alapján egyetlen esetet leszámítva mindig létezik, ám a kitüntetett közös osztó létezése egyáltalán nem magától értetődő.

Szerencsére a Z\Z gyűrűben valóban mindig létezik a kitüntetett közös osztó, amelyre hamarosan egy úgynevezett "konstruktív bizonyítást" adunk. Ez azt jelenti, hogy a bizonyítás egy meglehetősen hatékony eljárást is fog szolgáltatni a kitüntetett közös osztó kiszámításához. Ez az eljárás az ókorból ered, és "euklidészi algoritmus" néven ismeretes, az alapgondolatát pedig a 17.4. szakaszban fogjuk bemutatni.

Mielőtt azonban erre rátérnénk, vizsgáljuk meg, hogy miért is olyan fontos nekünk a kitüntetett közös osztó létezése egy adott integritástartományban.

17.3A kitüntetett közös osztó jelentősége

Ebben a szakaszban azt fogjuk megmutatni, hogy amennyiben egy RR integritástartományban bármely két elemnek létezik kitüntetett közös osztója, akkor RR minden felbonthatatlan eleme prímtulajdonságú, következésképp a 16.18. Tétel alapján teljesül a számelmélet alaptételének egyértelműségi része.

Ehhez szükségünk lesz három segédtételre. Először az oszthatósági reláció egy újabb egyszerű tulajdonságát igazoljuk, amely nagyon hasonló a 16.2. Tétel 7. pontjában megfogalmazott állításhoz, ám annál egy kicsit többet mond. Ez hasznunkra lesz a továbbiakban is.

17.8. Tétel:

Legyen RR egy tetszőleges kommutatív gyűrű. Ekkor bármely aa, bb és cc elemek esetén az a∣ba|b oszthatóságból következik az ac∣bcac|bc oszthatóság. Ha RR nullosztómentes és c≠0c\neq 0, akkor az állítás megfordítása is igaz, vagyis az ac∣bcac|bc oszthatóságból következik az a∣ba|b oszthatóság.

Egyrészt tehát egy kommutatív gyűrűben egy oszthatóság mindkét oldalát szabad megszorozni bármilyen elemmel. Másrészt – ha a gyűrű nullosztómentes is –, akkor az oszthatóság mindkét oldalát szabad egyszerűsíteni bármilyen nemnulla elemmel.

Megnézem a tudásbázisban

♣

Például az egész számok gyűrűjében teljesül a 6∣186|18 oszthatóság, és így a tétel alapján teljesül a 3∣93|9 oszthatóság is.

Bizonyítás:

Az, hogy fennáll az a∣ba|b oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan kk elem, amelyre teljesül az alábbi egyenlet:

ak=bak = b

Az egyenlet mindkét oldalát a cc elemmel megszorozva ezt kapjuk:

(ak)c=bc(ak)c = bc

Mivel azonban a 14.12. Definíció 4. pontja alapján a szorzás asszociatív, valamint – kommutatív gyűrűről lévén szó – a 6. pont alapján kommutatív is, ezért ennek az egyenletnek a baloldala átzárójelezhető és átrendezhető:

(ac)k=bc(ac)k = bc

Létezik tehát olyan elem, amellyel acac-t megszorozva bcbc-t kapunk, nevezetesen a kk. Ez viszont épp azt jelenti, hogy ac∣bcac|bc. Vegyük észre, hogy ehhez nem használtuk fel a nullosztómentességet, valamint a c=0c=0 esetre is működik.

A megfordítás bizonyítása: ehhez már fel kell használni a nullosztómentességet is. Ebben az esetben az ac∣bcac|bc oszthatóságból az előző lépéseket visszafele eljátszva következik az alábbi egyenlet:

(ak)c=bc(ak)c = bc

Ezt a c≠0c\neq 0 feltétel, valamint a nullosztómentesség miatt a 15.4. Tétel alapján egyszerűsíteni lehet cc-vel, azaz:

ak=bak = b

Ez viszont a 16.1. Definíció alapján épp azt jelenti, hogy a∣ba|b.

Megnézem a tudásbázisban

∎

Az oszthatóságnak ezt a tulajdonságát most fel fogjuk használni egy, a kitüntetett közös osztóval kapcsolatos fontos összefüggés igazolásához.

17.9. Tétel (A kitüntetett közös osztó kiemelési tulajdonsága):

Legyen RR egy tetszőleges integritástartomány, amelyben bármely két elemnek létezik kitüntetett közös osztója. Ekkor tetszőleges aa, bb és cc elemekre érvényes az alábbi összefüggés:

(ac,bc)∼(a,b)c(ac,bc)\sim (a,b)c

Azaz (ac,bc)(ac,bc) és (a,b)c(a,b)c mindig egymás asszociáltjai.

Megnézem a tudásbázisban

♣

Például a Z\Z gyűrűben (6,9)∼3(6,9)\sim 3, és így (18,27)∼(6⋅3,9⋅3)∼(6,9)⋅3∼9(18,27)\sim (6\cdot 3, 9\cdot 3)\sim (6,9)\cdot 3\sim 9.

Bizonyítás:

Ha c=0c=0, akkor nyilván igaz az állítás, hiszen a 17.6. Tétel 5. pontja miatt egyrészt (a0,b0)=(0,0)=0(a0,b0)=(0,0)=0, másrészt a 15.1. Tétel 1. pontja miatt (a,b)0=0(a,b)0 = 0.

Ha a=b=0a=b=0, akkor hasonló okok miatt szintén nyilvánvalóan teljesül a tétel, hiszen egyrészt (0c,0c)=(0,0)=0(0c,0c)=(0,0)=0, másrészt (0,0)c=0c=0(0,0)c=0c=0.

Az általánosság megsértése nélkül feltehetjük tehát, hogy c≠0c\neq 0, valamint aa és bb közül legalább az egyik nem 00, és emiatt a 16.2. Tétel 4. pontja miatt (a,b)≠0(a,b)\neq 0.

Mivel (a,b)(a,b) közös osztó, ezért teljesülnek az alábbi oszthatóságok:

(a,b)∣a(a,b)∣b\begin{aligned} (a,b)&|a \\ (a,b)&|b \end{aligned}

Ekkor azonban a 17.8. Tétel miatt teljesülnek az alábbi oszthatóságok is:

(a,b)c∣ac(a,b)c∣bc\begin{aligned} (a,b)c&|ac \\ (a,b)c&|bc \end{aligned}

Ez viszont azt jelenti, hogy (a,b)c(a,b)c közös osztója acac-nek és bcbc-nek. Mivel feltételeztük, hogy bármely két elemnek létezik kitüntetett közös osztója, ezért nyilván létezik az (ac,bc)(ac,bc) kitüntetett közös osztó is. Ez viszont – kitüntetett lévén – többszöröse bármely más közös osztónak, így (a,b)c(a,b)c-nek is. Azt tehát már tudjuk a tételben szereplő két kifejezésről, hogy teljesül közöttük az alábbi oszthatóság:

(a,b)c∣(ac,bc)(a,b)c|(ac,bc)

Ez viszont a 16.1. Definíció alapján épp azt jelenti, hogy létezik olyan kk elem, amelyre teljesül az alábbi egyenlet:

(a,b)ck=(ac,bc)(a,b)ck = (ac,bc)

Azt fogjuk megmutatni, hogy kk egység, mivel ebből a 16.10. Tétel miatt már következik az (a,b)c∼(ac,bc)(a,b)c\sim (ac,bc) asszociáltság. Vizsgáljuk hát meg a fenti egyenletet.

Ennek jobboldala acac és bcbc közös osztója, így az egyenlet baloldala is. Fennállnak tehát az alábbi oszthatóságok:

(a,b)ck∣ac(a,b)ck∣bc\begin{aligned} (a,b)ck &|ac \\ (a,b)ck &|bc \end{aligned}

Mivel a bizonyítás elején az általánosság megsértése nélkül feltehettük, hogy c≠0c\neq 0, így mindkét oszthatóságot egyszerűsíteni lehet vele a 17.8. Tétel miatt. Ekkor ezt kapjuk:

(a,b)k∣a(a,b)k∣b\begin{aligned} (a,b)k &|a \\ (a,b)k &|b \end{aligned}

Azt kaptuk tehát, hogy (a,b)k(a,b)k közös osztója aa-nak és bb-nek, és így osztója az ő kitüntetett közös osztójuknak. Azaz:

(a,b)k∣(a,b)(a,b)k|(a,b)

Mivel a bizonyítás elején láttuk, hogy (a,b)≠0(a,b)\neq 0, ezért ismét alkalmazható a 17.8. Tétel, amely szerint mindkét oszthatóságot egyszerűsíteni lehet (a,b)(a,b)-vel. Ekkor ezt kapjuk:

k∣1k|1

A kk elem tehát osztója az egységelemnek, emiatt a 16.5. Tétel értelmében valóban egység. Következésképp a 16.10. Tétel miatt (a,b)ck=(ac,bc)(a,b)ck=(ac,bc)-ből következik az (a,b)c∼(ac,bc)(a,b)c\sim (ac,bc) asszociáltság, ahogyan a tétel állítja.

Megnézem a tudásbázisban

∎

Végül igazoljuk az úgynevezett "euklidészi lemmát". Ez arra ad feltételt, hogy egy elem mely esetekben osztója egy adott szorzat valamelyik tényezőjének, ha egyébként magának a szorzatnak osztója. A 16.4. szakaszban már megemlítettük, hogy ez általánosságban nem igaz. Például 8∣2⋅128|2\cdot 12, ugyanakkor sem a 8∣28|2, sem pedig a 8∣128|12 oszthatóság nem teljesül.

A 16.13. Definícióban épp azokat az elemeket neveztük prímeknek, amelyek bármely olyan szorzatra teljesítik ezt a kritériumot, amelynek egyébként osztói. Az euklidészi lemma a prímtulajdonságnál gyengébb feltételt határoz meg erre vonatkozóan. Ez alapján egy elemnek nem feltétlenül kell prímnek lennie ahhoz, hogy egy adott szorzat valamely tényezőjének osztója legyen. Viszont szükséges, hogy a másik tényezőjével a "lehető legkevesebb" közös osztójuk legyen. Először is tisztázzuk, hogy mikor mondjuk két elemről, hogy a "lehető legkevesebb" közös osztójuk van. Ennek az esetnek külön neve is van, amelyet a továbbiakban gyakran fogunk használni.

17.10. Definíció (Relatív prímek):

Legyen RR tetszőleges integritástartomány. Amennyiben valamely aa és bb elemeknek minden közös osztója egység, akkor azt mondjuk, hogy aa és bb relatív prímek egymáshoz.

Megnézem a tudásbázisban

♣

Megjegyzés:

Figyelem! Ez a fogalom nem azonos sem a felbonthatatlanok, sem pedig a prímek fogalmával. Abból ugyanis, hogy két elem egymáshoz relatív prím, még nem következik, hogy közülük bármelyik is akár felbonthatatlan, akár prím lenne. Például a Z\Z gyűrűben a 88 és a 99 egész számoknak a −1-1-en és az 11-en – tehát a gyűrű egységein – kívül nincs más közös osztójuk, így relatív prímek. Ám egyikük sem felbonthatatlan, hiszen a 8=2⋅48=2\cdot 4 és a 9=3⋅39=3\cdot 3 nemtriviális felbontások. És mivel nem felbonthatatlanok, ezért a 16.14. Tétel miatt nem is prímek.

Megjegyezzük még, hogy aa és bb relatív prímsége esetén nem csak az teljesül, hogy minden közös osztó egység, hanem az is, hogy minden egység közös osztó, hiszen az egységek minden elemnek osztói, így nyilván aa-nak is és bb-nek is. Másként fogalmazva relatív prímség esetén pontosan az egységek a közös osztók. Ezért a relatív prímséget gyakran az alábbi asszociáltsággal jelöljük:

(a,b)∼1(a,b)\sim 1

Megnézem a tudásbázisban

♣

Ezek után az euklidészi lemma a következőképpen fogalmazható meg.

17.11. Tétel (Euklidészi lemma):

Legyen RR egy tetszőleges integritástartomány, amelyben bármely két elemnek létezik kitüntetett közös osztója. Ekkor ha valamely aa, bb és cc elemek esetén teljesül az a∣bca|bc oszthatóság, valamint aa és bb relatív prímek, akkor teljesül az a∣ca|c oszthatóság is.

Megnézem a tudásbázisban

♣

Például a Z\Z gyűrűben 4∣9⋅84|9\cdot 8, és mivel 44 és 99 relatív prímek – azaz (4,9)∼1(4,9)\sim 1 –, ezért 4∣84|8.

Bizonyítás:

A tétel szövegének megfelelően tegyük fel, hogy teljesül az a∣bca|bc oszthatóság, valamint aa és bb relatív prímek, azaz a 17.10. Definíció utáni megjegyzés miatt (a,b)∼1(a,b)\sim 1.

Mivel RR egységelemes, ezért a 16.2. Tétel 1. pontja miatt teljesül az a∣aa|a oszthatóság, és így ugyanezen tétel 7. pontja miatt az a∣aca|ac oszthatóság is. Továbbá a tétel szövegéből tudjuk, hogy a∣bca|bc, tehát az aa elem közös osztója acac-nek és bcbc-nek, így osztója ezek kitüntetett közös osztójának. Azaz:

a∣(ac,bc)a|(ac,bc)

A 17.9. Tétel miatt azonban teljesül az (ac,bc)∼(a,b)c(ac,bc)\sim (a,b)c asszociáltság, így:

a∣(a,b)ca|(a,b)c

Végül, mivel (a,b)∼1(a,b)\sim 1 – tehát (a,b)(a,b) egység –, ezért teljesül az (a,b)c∼c(a,b)c\sim c asszociáltság is, azaz valóban a∣ca|c, ahogy a tétel állítja.

Megnézem a tudásbázisban

∎

Az euklidészi lemma felhasználásával mostmár igazolhatjuk a kitüntetett közös osztó létezésének jelentőségét a számelmélet alaptétele kapcsán.

17.12. Tétel:

Legyen RR egy tetszőleges integritástartomány. Ha bármely két elemnek létezik kitüntetett közös osztója, akkor RR-ben minden felbonthatatlan elem prímtulajdonságú.

Megnézem a tudásbázisban

♣

Bizonyítás:

Legyen pp egy tetszőleges felbonthatatlan elem RR-ben. Azt kell megmutatni, hogy prímtulajdonságú, azaz hogy ha valamilyen aa és bb elemek esetén teljesül a p∣abp|ab oszthatóság, de p∤ap\nmid a, akkor szükségképpen teljesül a p∣bp|b oszthatóság is.

Tegyük hát fel, hogy p∤ap\nmid a. Mivel azt mondtuk, hogy bármely két elemnek létezik kitüntetett közös osztója RR-ben, ezért nyilván pp-nek is és aa-nak is létezik a (p,a)(p,a) kitüntetett közös osztója. Mivel (p,a)(p,a) közös osztó, ezért nyilván teljesül a (p,a)∣p(p,a)|p oszthatóság. De mivel pp felbonthatatlan, ezért a 16.11. Definíció miatt az alábbi két eset lehetséges:

(p,a)∼p(p,a)∼1\begin{aligned} (p,a)&\sim p \\ (p,a)&\sim 1 \end{aligned}

Azaz (p,a)(p,a) vagy egység, vagy pedig pp valamely asszociáltja. Ez utóbbi azonban lehetetlen, hiszen ekkor – lévén, hogy (p,a)(p,a) közös osztó – teljesülne a (p,a)∣a(p,a)|a oszthatóság, és így (p,a)∼p(p,a)\sim p miatt teljesülne a p∣ap|a oszthatóság is, ami ellentmond a feltételezésünknek, miszerint p∤ap\nmid a.

Azt kaptuk tehát, hogy (p,a)(p,a) csak egység lehet, azaz pp és aa relatív prímek. Ha tehát teljesül a p∣abp|ab oszthatóság, akkor ebből a 17.11. Tétel miatt következik a p∣bp|b oszthatóság is. Azaz pp valóban prímtulajdonságú, ahogy a tétel állítja.

Megnézem a tudásbázisban

∎

Mostmár tehát tudjuk, hogy ha egy integritástartományban bármely két elemnek létezik a kitüntetett közös osztója, akkor minden felbonthatatlan elem prímtulajdonságú. Ebből viszont a 16.18. Tétel miatt következik, hogy teljesül a számelmélet alaptételének egyértelműségi állítása.

A 17.2. szakasz végén a 17.7. Tételben már láttuk, hogy a kriptográfiai szempontból számunkra fontos Z\Z gyűrűben ha egy elempárnak létezik kitüntetett közös osztója, akkor a legnagyobb közös osztójuk is kitüntetett. Megemlítettük ugyanakkor, hogy ez a tétel még nem garantálja azt, hogy bármely két egész számnak létezik a kitüntetett közös osztója. Ennek igazolására most megismerkedünk egy igen fontos számelméleti algoritmussal.

17.4Az euklidészi algoritmus alapgondolata

Az euklidészi algoritmus az egyik legősibb, igen gyakran használt számelméleti algoritmus. Nevét az ókori görög matematikusról, Euklidészről kapta, aki Kr.e. 300 körül írta le az Elemek című művében. Ez egy rendkívül hatékony módszert határoz meg két egész szám kitüntetett közös osztójának előállítására.

Az általános iskolából nyilván mindenki emlékszik arra a módszerre, amely a két számnak a számelmélet alaptétele szerinti prímtényezős felbontásából indul ki. Mivel a 16.8. Tétel 1. pontja alapján egy egész szám és az ellentettje ugyanúgy viselkedik oszthatóság szempontjából, ezért elegendő csak a pozitív egészekre és a pozitív prímtényezőkre szorítkozni. Ha tehát rendelkezésünkre áll a két szám prímtényezős felbontása, akkor a keresett kitüntetett közös osztó prímtényezős felbontása pontosan azokból a prímtényezőkből fog állni, amelyek mindkét szám felbontásában szerepelnek. Így például a 1818 és a 4545 kitüntetett közös osztója 99, mivel a két eredeti szám felbontása:

18=2⋅3⋅345=3⋅3⋅5\begin{aligned} 18&=2\cdot 3\cdot 3 \\ 45&=3\cdot 3\cdot 5 \end{aligned}

A két felbontás közös prímtényezői adják a kitüntetett közös osztót, azaz 3⋅3=93\cdot 3=9.

Ezzel a módszerrel – bár helyes – két alapvető probléma van. Egyrészt azt még nem bizonyítottuk, hogy a Z\Z gyűrűben valóban teljesül a számelmélet alaptétele, így azt elméletben még nem használhatnánk. Másrészt viszont – és ez egy jóval nagyobb, gyakorlati probléma – ehhez a módszerhez szükségünk van a két szám prímtényezős felbontására. Ennek meghatározására jelenlegi tudásunk szerint azonban nem létezik hatékony eljárás, habár ez még bizonyításra vár. Hogy mit értünk "hatékony eljárás" alatt, arról a 6., 7. és 8. fejezetekben volt szó részletesen, így azt nem ismételnénk meg. Azonban saját bőrünkön is érzékelhetjük a problémát, ha megpróbáljuk megtalálni például a 12 439 705 04912\space 439\space 705\space 049 és a 15 828 713 00315\space 828\space 713\space 003 kitüntetett közös osztóját ezzel a módszerrel.

Az említett "iskolás" módszert követve persze elkezdhetjük a prímtényezőkre bontást. Hamar beletörik azonban a bicskánk, mivel ezt a két számot szándékosan nagy prímtényezőkből állítottam össze. Nevezetesen:

12 439 705 049=2797⋅2999⋅148315 828 713 003=2999⋅1483⋅3559\begin{aligned} 12\space 439\space 705\space 049 &= 2797\cdot 2999\cdot 1483 \\ 15\space 828\space 713\space 003 &= 2999\cdot 1483\cdot 3559 \end{aligned}

Innen persze a közös prímtényezők kiválogatása, és a kitüntetett közös osztó kiszámítása már egyszerű:

2999⋅1483=4 447 5172999\cdot 1483=4\space 447\space 517

Mondhatnánk, hogy számítógéppel pillanatok alatt prímtényezőire bonthatjuk ezt a két számot. Ez minden bizonnyal így is van az ilyen nagyságrendű számok esetén. A problémát az okozza, hogy a bemeneti számjegyek számának növelésével a prímtényezők kiszámításához szükséges idő nagyon meredeken kezd emelkedni. Olyannyira, hogy például egy több száz számjegyből álló szám prímtényezőire bontása még a világ összes számítógépének is beláthatatlanul sok ideig tartana. A kriptográfiában használt RSA eljárás algoritmikus biztonsága épp a prímtényezős felbontás feladatának e roppant nehézségén alapszik.

Az euklidészi algoritmus ezzel szemben egy olyan eljárást ad két egész szám kitüntetett közös osztójának kiszámítására, amelyhez nincs szükség a két szám prímtényezőire. Az algoritmus alapötlete az oszthatóság tulajdonságairól szóló a 16.2. Tétel 6. és 7. pontjainak egy egyszerű következményén alapul. Nézzük is meg ezt az összefüggést.

17.13. Tétel:

Legyen RR egy tetszőleges integritástartomány. Ekkor ha valamely aa és bb elemeknek létezik az (a,b)(a,b) kitüntetett közös osztója, akkor tetszőleges kk elem esetén érvényes az alábbi összefüggés:

(a,b)∼(b,a−kb)(a,b)\sim (b, a-kb)

Megnézem a tudásbázisban

♣

Bizonyítás:

Mivel (a,b)(a,b) közös osztó, ezért teljesülnek az alábbi oszthatóságok:

(a,b)∣a(a,b)∣b\begin{aligned} (a,b)&|a \\ (a,b)&|b \end{aligned}

A második oszthatóság jobboldala a 16.2. Tétel 7. pontja miatt tetszőleges kk elemmel megszorozható:

(a,b)∣kb(a,b)|kb

Az (a,b)(a,b) tehát osztója aa-nak és kbkb-nek, így ugyanezen tétel 6. pontja miatt osztója a különbségüknek is:

(a,b)∣a−kb(a,b)|a-kb

Azt kaptuk, hogy az (a,b)(a,b) elem aa-n és bb-n kívül közös osztója bb-nek és a−kba-kb-nek is. Már csak azt kell megmutatni, hogy ennek az elempárnak szintén kitüntetett közös osztója, azaz bármely más közös osztónak többszöröse. Tegyük fel például, hogy dd egy ilyen közös osztó, azaz:

d∣bd∣a−kb\begin{aligned} d&|b \\ d&|a-kb \end{aligned}

Az első oszthatóság jobboldalát a 16.2. Tétel 7. pontja miatt kk-val megszorozhatjuk:

d∣kbd|kb

A dd elem tehát osztója a−kba-kb-nek és kbkb-nek, így ugyanezen tétel 6. pontja miatt osztója az összegüknek is, amelyben a kbkb és −kb-kb tagok kiejtik egymást:

d∣a−kb+kbd|a-\cancel{kb}+\cancel{kb}

Azt kaptuk tehát, hogy dd közös osztója aa-nak és bb-nek, emiatt osztója az ő kitüntetett közös osztójuknak, azaz (a,b)(a,b)-nek is. Igenám, de fentebb már láttuk, hogy (a,b)(a,b) nem csak az aa és bb elemek közös osztója, hanem a bb és a−kba-kb elemeknek is. Így ő végülis ezeknek az elemeknek is kitüntetett közös osztója, és így a két kitüntetett közös osztó a 17.5. Tétel alapján egymás asszociáltjai, azaz valóban:

(a,b)∼(b,a−kb)(a,b)\sim (b,a-kb)

Megnézem a tudásbázisban

∎

Nézzük is meg, hogy miképpen tudunk profitálni ebből az imént kapott (a,b)∼(b,a−kb)(a,b)\sim (b, a-kb) összefüggésből. Egyelőre tegyük fel, hogy Z\Z gyűrűben vagyunk, mind aa, mind pedig bb pozitív egészek, valamint a>ba\gt b. Később majd általánosítani fogjuk az algoritmust tetszőleges esetre, sőt tetszőleges integritástartományra, most azonban a működés alapelvének megértése a cél.

Rajzoljunk fel két "rudat", amelyek méretarányosan tükrözik e két szám nagyságát. Kezdjünk el lenyesegetni bb-nek megfelelő hosszúságú darabokat az aa-t jelölő rúdból mindaddig, amíg a maradék kisebb nem lesz, mint bb, vagy akár el nem tűnik teljesen. Ezt a folyamatot láthatjuk a 17.1. ábrán, amelyen a maradék rudacska hosszának megfelelő számot r1r_1-gyel jelöltük.

Maradékos osztás szemléltetése rudakkal
17.1. ábra: Maradékos osztás szemléltetése rudakkal

Ha belegondolunk, tulajdonképpen az történt, hogy az aa pozitív egész számot sikerült kifejeznünk "valahányszor bb, meg egy kis maradék" alakban, ahol k1k_1-gyel jelöltük a "valahányszort", r1r_1-gyel pedig a "maradékot":

a=k1b+r1a=k_1b+r_1

Ráadásul – és ez kulcsfontosságú – az r1r_1 maradékra teljesül, hogy legalább 00, viszont szigorúan kisebb bb-nél:

0≤r1<b0\leq r_1\lt b

A fenti egyenletből az r1r_1 maradékot ki tudjuk fejezni r1=a−k1br_1=a-k_1b alakban. Ez azért baromi jó, mivel az imént bizonyított 17.13. Tétel alapján a (b,r1)(b,r_1) kitüntetett közös osztó egyúttal az aa és bb elemek kitüntetett közös osztója is lesz. Az eredeti számok kitüntetett közös osztójának kiszámítását tehát sikerült két kisebb szám kitüntetett közös osztójának kiszámítására visszavezetni. Most folytassuk ugyanezt a lenyesegetős eljárást a bb és r1r_1 számokkal. Ez látható a 17.2. ábrán kinagyítva.

Maradékos osztás (második lépés)
17.2. ábra: Maradékos osztás (második lépés)

Ekkor tulajdonképpen a bb-t sikerült kifejeznünk "valahányszor r1r_1, meg egy kis maradék" alakban. Ezt az eljárást folytatva a következő sorozathoz jutunk:

a=k1b+r1b=k2r1+r2r1=k3r2+r3r2=k4r3+r4⋮\begin{aligned} a&=k_1b+r_1 \\ b&=k_2r_1+r_2 \\ r_1&=k_3r_2+r_3 \\ r_2&=k_4r_3+r_4 \\ &\vdots \end{aligned}

Mindeközben pedig a lépések során kapott maradékok így alakulnak:

0≤…<r4<r3<r2<r1<b0\leq \ldots \lt r_4 \lt r_3 \lt r_2 \lt r_1 \lt b

Továbbá a keresett kitüntetett közös osztóra igaz lesz az alábbi:

(a,b)∼(b,r1)∼(r1,r2)∼(r2,r3)∼…(a,b)\sim (b,r_1)\sim (r_1,r_2)\sim (r_2,r_3)\sim \ldots

A maradékok tehát egyre kisebbek és kisebbek lesznek, miközben mindegyikről tudjuk, hogy 00-nál semmiképpen sem lehetnek kisebbek. Ezért érezhetően véges számú lépés után valamelyik maradék előbb-utóbb biztosan 00 lesz. A 17.5. szakaszban megmutatjuk, hogy ez valóban a 11.1. Definíció szerinti Peano-axiómarendszer egy következménye. Egyelőre tegyük fel, hogy ez tényleg így van, és az utolsó nemnulla maradék rnr_n. Ekkor befejezhetjük az eljárást, és mivel rn≠0r_n\neq 0, továbbá a 16.2. Tétel 3. pontja miatt rn∣0r_n|0 ugye teljesül, így alkalmazhatjuk a 17.6. Tétel 4. pontját. Ez alapján gyakorlatilag megkaptuk a keresett kitüntetett közös osztót, ami nem más, mint rnr_n:

(a,b)∼(rn,0)∼rn(a,b)\sim (r_n,0)\sim r_n

Maradékos osztásnak nevezzük azt a műveletet, melynek során kiszámítjuk, hogy egy szám egy másikkal osztva mennyi maradékot ad. A maradékos osztás – itt nem részletezett digitális áramköri okok miatt – egy számítógép számára rendkívül hatékonyan elvégezhető. Ráadásul megmutatható – habár erre most nem térünk ki –, hogy a fenti algoritmushoz szükséges maradékos osztások száma a kisebbik bemenet számjegyeinek a számával egyenesen arányos. Ez azt jelenti, hogy még az több száz jegyű számok tartományában is nagyságrendileg pár száz maradékos osztásból megkaphatjuk a kitüntetett közös osztót. Egy átlagos számítógép számára ez egy szemvillanás alatt elvégezhető. Ezzel szemben a prímtényezős módszer az idők végezetéig is eltartana ebben a számtartományban.

E gyorsaság demonstrálására nézzük is meg, hogy mennyire gyorsan kapjuk meg a szakasz elején ismertetett példában szereplő 12 439 705 04912\space 439\space 705\space 049 és 15 828 713 00315\space 828\space 713\space 003 számok kitüntetett közös osztóját. A maradékos osztás műveletét könnyedén el tudjuk végezni a legegyszerűbb kalkulátorral is. Ezt általában a mod – vagy hasonló – feliratú nyomógombbal érhetjük el, és egyetlen lépésben képezni fogja nekünk a képződő maradékot. Például a 8 mod 38\space \text{mod}\space 3 műveletet elvégezve az eredmény 22, mivel a 88-at 33-mal osztva a maradék 22.

Az euklideszi algoritmust a két bemeneti számunkon lefuttatva az alábbi lépéseken keresztül jutunk el a keresett kitüntetett közös osztóig:

(15828713003,12439705049)∼∼ (12439705049,3389007954)∼∼ (3389007954,2272681187)∼∼ (2272681187,1116326767)∼∼ (1116326767,40027653)∼∼ (40027653,35580136)∼∼ (35580136,4447517)∼∼ (4447517,0)\begin{aligned} &(15828713003,12439705049) \sim \\ \sim ~ &(12439705049,3389007954) \sim \\ \sim ~ &(3389007954, 2272681187) \sim \\ \sim ~ &(2272681187,1116326767) \sim \\ \sim ~ &(1116326767, 40027653) \sim \\ \sim ~ &(40027653, 35580136) \sim \\ \sim ~ &(35580136,4447517) \sim \\ \sim ~ &(4447517, 0) \end{aligned}

A keresett kitüntetett közös osztó tehát 4 447 5174\space 447\space 517. Valóban ugyanazt az eredményt kaptuk, mint a prímtényezős felbontást használó módszerrel, csak épp nem sok ezer – vagy épp millió – osztáspróbával, hanem mindössze hét maradékos osztással. Úgy gondolom ez eléggé meggyőző, amikor hatékonyságról beszélünk.

17.5A végtelen leszállás módszere

Hamarosan azt fogjuk megvizsgálni, hogy az imént tanult eljárást hogyan tudjuk olyan integritástartományokra is kiterjeszteni, amelyek nem feltétlenül számokat tartalmaznak. Ehhez először megismerkedünk a "végtelen leszállás" néven ismeretes indirekt bizonyítási módszerrel. Ezzel fogjuk tudni igazolni, hogy az euklidészi algoritmus véges számú lépés után valóban befejeződik. A módszer a természetes számok N\N halmazának egy fontos tulajdonságán alapul. Ám mielőtt ezt ismertetnénk, először egy segédtételt fogunk bizonyítani.

17.14. Lemma:

Legyenek nn és xx a természetes számok N\N halmazának tetszőleges elemei, és jelölje s(n)s(n) az nn természetes szám 11.1. Definíció szerinti rákövetkezőjét. Ekkor tetszőleges xx természetes szám esetén teljesülnek az alábbiak:

1.
Ha n<x≤s(n)n<x\leq s(n), akkor x=s(n)x=s(n).
2.
Ha n≤x<s(n)n\leq x< s(n), akkor x=nx=n.

Megnézem a tudásbázisban

♣

Bizonyítás:

Kezdjük az 1. állítás igazolásával. Mivel x≤s(n)x\leq s(n), ezért az alábbi két eset lehetséges:

n<x=s(n)n<x<s(n)\begin{aligned} n<x&=s(n) \\ n<x&<s(n) \end{aligned}

Tegyük fel indirekt, hogy a tétel állításával szemben a második eset áll fenn, azaz:

n<x<s(n)n<x<s(n)

Ekkor az egész számok rendezésének a 15.18. Tételben szereplő definíciója alapján léteznek olyan k1≠0k_1\neq 0 és k2≠0k_2\neq 0 természetes számok, hogy teljesül az alábbi:

n+k1⏟=x+k2=s(n)\underbrace{n+k_1}_{=x}+k_2 = s(n)

A 11.4. Definíció 2. pontja alapján ez így írható:

n+k1+k2=n+s(0)⏟=s(n)n+k_1+k_2=\underbrace{n+s(0)}_{=s(n)}

Az egyenlet mindkét oldalát egyszerűsíthetjük nn-nel a 12.18. Lemma miatt:

k1+k2=s(0)k_1+k_2=s(0)

Mivel k1≠0k_1\neq 0, ezért a 11.1. Definíció 3. pontja miatt létezik olyan k0k_0 természetes szám, amelynek épp k1k_1 a rákövetkezője, azaz s(k0)=k1s(k_0)=k_1. Ekkor az egyenlet így írható:

s(k0)⏟=k1+k2=s(0)\underbrace{s(k_0)}_{=k_1}+k_2=s(0)

Ismét a 11.4. Definíció 2. pontja, valamint az összeadás kommutativitása miatt ez így is írható:

s(k0+k2)⏟=s(k0)+k2=s(0)\underbrace{s(k_0+k_2)}_{=s(k_0)+k_2}=s(0)

A 11.1. Definíció 2. pontja alapján ekkor:

k0+k2=0k_0+k_2=0

Végül alkalmazhatjuk a 12.19. Lemmát, mely szerint ez csak akkor lehetséges, ha teljesülnek az alábbiak:

k0=0k2=0\begin{aligned} k_0&=0 \\ k_2&=0 \end{aligned}

Ez viszont ellentmond annak, hogy k2≠0k_2\neq 0, vagyis az indirekt feltevésünk hibás volt, és így kizárólag csak az alábbi eset fordulhat elő, ahogy a tétel állítja:

n<x=s(n)n<x=s(n)

Most igazoljuk a 2. állítást. Mivel n≤xn\leq x, ezért az alábbi két eset lehetséges:

n=x<s(n)n<x<s(n)\begin{aligned} n=x&<s(n) \\ n<x&<s(n) \end{aligned}

Tegyük fel indirekt, hogy a tétel állításával szemben a második eset áll fenn, azaz:

n<x<s(n)n<x<s(n)

Erről viszont az 1. állítás kapcsán már láttuk, hogy lehetetlen.

Megnézem a tudásbázisban

∎

Ezt a segédtételt felhasználva most megmutatjuk a természetes számok N\N halmazának a már említett fontos tulajdonságát.

17.15. Tétel (A természetes számok minimumtétele):

Ha PP a természetes számok N\N halmazának tetszőleges nemüres részhalmaza, akkor PP-nek van minimuma a 15.18. Tétel szerinti ≤\leq relációra nézve. Minimum alatt egy olyan PP-beli pp elem létezését értjük, amelyre tetszőleges, szintén PP-beli qq elem esetén teljesül a p≤qp\leq q reláció.

Megnézem a tudásbázisban

♣

Megjegyzés:

Eszerint tehát sehogyan sem lehet kiválogatni véges vagy akár végtelen sok természetes számot úgy, hogy ezek között ne lenne legkisebb. Vegyük észre, hogy ez az egész számok Z\Z halmazára például nem érvényes, mivel bármilyen egész számnál létezik nála kisebb egész szám, hiszen itt a számegyenes mindkét irányban végtelen. De bizonyos számkörökben még csak erre sincs feltétlenül szükség. Habár a "törtszámokat" még nem építettük fel az axiómák segítségével, de intuitív módon érezhető, hogy bármely két törtszám között végtelen sok további törtszám létezik. Következésképp ebben a számkörben a számegyenes semmilyen véges hosszú szakaszára nem igaz a fenti tétel.

Az tehát, hogy a természetes számokra mégis igaz, egyáltalán nem magától értetődő, akármennyire is annak látszik. Szerencsénkre, ez ugyanis lehetőséget teremt egy újfajta bizonyítási módszerre, amelyet végtelen leszállásnak nevezünk. Ezt Pierre de Fermat fejlesztette ki a 17. században, és számos fontos eredményhez jutott ennek segítségével. A módszer tulajdonképpen egy indirekt érvelés, melynek során megmutatjuk, hogy ha a szóban forgó állítás hamis, akkor elő lehet állítani egy olyan természetes számokból álló sorozatot, amelynek nincs minimuma. Ez ugye ellentmondana a minimumtételnek, a bizonyítandó állítás tehát nem lehet hamis, következésképp igaznak kell lennie.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tegyük fel indirekt, hogy PP egy olyan galád nemüres részhalmaza N\N-nek, amelynek nincs minimuma. Jelöljük ezenkívül QQ-val N\N-nek azt a részhalmazát, amely pontosan azokat a természetes számokat tartalmazza, amelyek kisebbek PP minden eleménél. Azaz egyrészt minden QQ-beli qq elemre teljesül, hogy minden PP-beli pp elem esetén q<pq\lt p, másrészt semmilyen QQ halmazon kívüli elemre nem tejesül ez a tulajdonság. Ez a szituáció látható a 17.3. ábrán.

P és Q halmazok elhelyezkedése
17.3. ábra: P és Q halmazok elhelyezkedése

Egyelőre még nem tudjuk, hogy mely természetes számok tartoznak PP-be, és melyek QQ-ba. Az viszont bizonyos, hogy ha egy qq természetes szám QQ-ba tartozik, akkor nem tartozhat egyúttal PP-be is, máskülönben teljesülne a q<qq\lt q reláció. Ez viszont lehetetlen, hiszen a 15.18. Tétel alapján ekkor léteznie kéne egy olyan k≠0k\neq 0 természetes számnak, amelyre q+k=qq+k=q teljesül. Mindkét oldalból qq-t kivonva k=0k=0 adódna, ami ellentmond k≠0k\neq 0-nak.

Azt kell megmutatnunk, hogy valójában minden természetes szám QQ-ba tartozik, azaz Q=NQ=\N, hiszen ebből következne, hogy – indirekt feltételezésünkkel ellentétben – PP csak az üres halmaz lehet. Ezt teljes indukcióval fogjuk bizonyítani, amelyre a Peano-axiómarendszer 11.1. Definíciójának 4. pontja ad lehetőséget.

Kezdjük a 00-val. Tegyük fel indirekt, hogy a 00 nincs benne QQ-ban, azaz létezik olyan PP-beli pp elem, amelyre nem teljesül a 0<p0\lt p reláció. Ekkor viszont az egész számok rendezésének trichotómiája miatt szükségképpen teljesülne a p≤0p\leq 0 reláció. Ez a 15.18. Tétel miatt azt jelentené, hogy létezik olyan kk természetes szám, amelyre p+k=0p+k=0. A 12.19. Lemma alapján azonban a természetes számok körében egy összeg csak úgy lehet 00, ha mindkét tagja 00, és így p=0p=0 lenne.

Abból az indirekt feltételezésből tehát, miszerint a 00 nincs benne QQ-ban az következik, hogy benne van PP-ben. Ez viszont lehetetlen, hiszen bármely nn természetes számra teljesül 0≤n0\leq n reláció, és így PP-nek a 00 minimuma lenne, márpedig PP-ről a bizonyítás elején feltettük, hogy nincs minimuma. A 00-nak tehát szükségképpen QQ-ban kell lennie.

Tegyük most fel, hogy egy valamilyen nn természetes számról már tudjuk, hogy QQ-ban van – mint például a 00, amiről ezt az imént láttunk be. Azt szeretnénk megmutatni, hogy ekkor s(n)s(n) – azaz nn-nek a 11.1. Definíció szerinti rákövetkezője – is benne van a QQ-ban.

Ezt ismét indirekt módon bizonyítjuk. Tegyük ezért fel az állítás ellenkezőjét, azaz hogy s(n)s(n) nincs benne a QQ halmazban. Egyrészt ez azt jelentené, hogy létezne olyan PP-beli pp elem, amelyre nem teljesül az s(n)<ps(n)\lt p reláció. Ismét a trichotómia miatt ekkor szükségképpen teljesülne a p≤s(n)p\leq s(n) reláció. Másrészt, mivel ugye nn az indukciós feltétel miatt benne van a QQ halmazban, így teljesül az n<pn\lt p reláció is. Azaz összefoglalva:

n<p≤s(n)n\lt p\leq s(n)

Ebből viszont a 17.14. Lemma miatt az következik, hogy s(n)s(n) benne van a PP halmazban, mivel:

p=s(n)p=s(n)

Egyrészt tehát azt kaptuk, hogy ha s(n)s(n) nem lenne QQ-ban, akkor szükségképpen PP-ben kellene lennie. Másrészt viszont az iménti gondolatmenetet bármely PP-beli xx elemre megismételve azt kapnánk, hogy x≤s(n)x\leq s(n) csak úgy teljesülhet, ha x=s(n)x=s(n). Így tehát a PP halmaznak mégiscsak lenne minimuma, nevezetesen s(n)s(n). Tehát hibás volt az indirekt feltételezésünk, ezért ha nn benne van QQ-ban, akkor az ő rákövetkezője is szükségképpen QQ-ban kell legyen.

Ezzel kész a teljes indukció, hiszen láttuk, hogy a 00 benne van QQ-ban, így az iménti gondolatmenet alapján az ő rákövetkezője is, majd annak a rákövetkezője, és így tovább a végtelenségig. A 11.1. Definíció 4. pontja alapján így minden természetes számot lefedünk, azaz Q=NQ=\N. Ekkor PP csak az üres halmaz lehet, azaz valóban nem létezik olyan nemüres részhalmaza N\N-nek, amelynek nincs minimuma – épp ahogyan a tétel állítja.

Megnézem a tudásbázisban

∎

A fenti tételen kívül szükségünk lesz még egy állításra, amely a ≤\leq-nél szigorúbb <\lt reláció tranzitivitását garantálja. A ≤\leq reláció tranzitivitását már igazoltuk a 12.17. Tételben. Nem meglepő módon ez a tulajdonság a <\lt relációra is teljesül, így most ezt mutatjuk meg.

17.16. Tétel:

Tetszőleges aa, bb és cc egész számok esetén ha a≤ba\leq b és b≤cb\leq c teljesül, valamint az ennél szigorúbb a<ba\lt b vagy b<cb\lt c közül legalább az egyik teljesül, akkor a<ca\lt c is teljesül.

Megnézem a tudásbázisban

♣

Bizonyítás:

Az a≤ba\leq b és b≤cb\leq c relációk teljesülése, valamint az a<ba\lt b vagy b<cb\lt c relációk közül legalább az egyiknek a teljesülése a 15.18. Tétel miatt azt jelenti, hogy léteznek nn és kk természetes számok, amelyek közül legalább az egyik nem 00, és amelyekre igazak az alábbi egyenletek:

a+n=bb+k=c\begin{aligned} a+n&=b \\ b+k&=c \end{aligned}

A második egyenletbe bb helyére az első egyenlet baloldalát behelyettesíthetjük:

a+n⏟=b+k=c\underbrace{a+n}_{=b}+k=c

Az n+kn+k összegről viszont tudjuk, hogy mindkét tagja természetes szám, melyek közül legalább az egyik nem 00. Márpedig a 12.19. Lemma kimondja, hogy ebben az esetben maga az összeg sem 00. Azaz létezik olyan nem 00 természetes szám – nevezetesen az n+kn+k –, amelyet aa-hoz adva cc-t kapunk. Ez a 15.18. Tétel miatt épp azt jelenti, hogy:

a<ca\lt c

Megnézem a tudásbázisban

∎

Ezek után a fejezet hátralévő részében a 17.15. Tétel utáni megjegyzésben ismertetett végtelen leszállás módszerét fogjuk felhasználni annak megmutatásához, hogy a számelmélet alaptétele teljesül gyűrűk egy speciális osztályában, az úgynevezett "euklidészi gyűrűkben".

17.6Euklidészi gyűrűk

Az euklidészi algoritmus alapgondolatának ismertetésekor a 17.4. szakaszban feltételeztük, hogy az aa és bb bemenet egy-egy pozitív egész szám, amelyeknek tehát a kitüntetett közös osztóját keressük. Az alapötletet a 17.13. Tétel szolgáltatta, mely szerint ha aa és bb között el tudjuk végezni a maradékos osztást, akkor az (a,b)(a,b) kitüntetett közös osztó – amennyiben létezik – asszociáltja lesz a (b,r1)(b,r_1) kitüntetett közös osztónak, ahol r1r_1 a maradékos osztás során képződő maradék. Ezek után a bb és r1r_1 között kell maradékos osztást végezni, így ha a képződő maradék r2r_2, akkor a (b,r1)(b,r_1) kitüntetett közös osztó – amennyiben létezik – asszociáltja lesz az (r1,r2)(r_1,r_2) kitüntetett közös osztónak.

Ezt az eljárást tovább folytatjuk mindaddig, míg valamelyik lépésben a képződő maradék 00 nem lesz. Ha az utolsó nemnulla maradék rnr_n, akkor végülis azt kaptuk, hogy az (a,b)(a,b) kitüntetett közös osztó létezik, mivel ő (rn,0)(r_n,0) asszociáltja, ami viszont a 17.6. Tétel 4. pontja alapján rnr_n asszociáltja.

Látható tehát, hogy az (a,b)(a,b) kitüntetett közös osztó létezése azon múlik, hogy véges számú lépés után biztosan 00 lesz-e a képződő maradék. Ezt fentebb csak feltételeztük, most azonban a végtelen leszállás módszerével könnyedén adódik. Ugyanis egy xx és egy yy elem maradékos osztásánál fontos követelmény volt, hogy az xx elemet úgy tudjuk kifejezni "valahányszor yy, meg egy kis maradék" alakban, hogy a maradék mindig szigorúan kisebb legyen, mint yy.

Tegyük fel indirekt, hogy a maradékos osztást mindig el tudjuk végezni ebben az értelemben, ám az eljárás ennek ellenére nem ér véget véges számú lépés után. Ebben az esetben az

r1>r2>r3>…r_1 \gt r_2 \gt r_3 \gt \ldots

sorozat a >\gt reláció 17.16. Tétel szerinti tranzitivitása miatt a természetes számoknak egy olyan részhalmaza lenne, amelynek nem lenne minimuma. Ez viszont a 17.15. Tétel alapján ellentmondás. Ha tehát a maradékos osztást el tudjuk végezni minden esetben, akkor az euklideszi algoritmus biztosan lefut véges számú lépés után, és kiszámítja a keresett kitüntetett közös osztót.

Igenám, csakhogy mi tetszőleges integritástartományra szeretnénk kiterjeszteni ezt az algoritmust. Márpedig például az egész számok gyűrűjére nem érvényes a minimumtétel. Más integritástartományok pedig még csak nem is feltétlenül számokból, hanem egyéb objektumokból állhatnak. Sőt, még az is előfordulhat, hogy a "kisebb-nagyobb" relációnak nincs is értelme egy RR integritástartományon, mert mondjuk RR még csak nem is rendezhető.

Vegyük azonban észre, hogy minket nem konkrétan a képződő maradékok és a közöttük lévő valamilyen módon értelmezett "kisebb-nagyobb" viszonyok érdekelnek. Ehelyett ezeknek a maradékoknak a – bizonyos absztrakt értelemben vett – "nagysága" az, ami igazán fontos. Ha valahogy sikerülne az adott gyűrű elemeinek "nagyságát" természetes számokkal "mérni" úgy, hogy az euklidészi algoritmus lépései során keletkező maradékok "nagysága" egy szigorúan csökkenő számsorozatot alkosson, akkor nyert ügyünk lenne.

A most következő definíció precízen megfogalmazza, hogy pontosan mit értünk egy ilyen jellegű absztrakt "mérhetőség" alatt, és külön nevet ad az olyan integritástartományoknak, amelyek ebben az értelemben "mérhetőek".

17.17. Definíció (Euklidészi gyűrűk):

Legyen RR tetszőleges integritástartomány, és jelöljük RR nemnulla elemeinek halmazát R≠0R_{\neq 0}-rel, míg RR nullelemét 0R0_R-rel. Legyen továbbá értelmezve egy

f:R≠0→Nf:R_{\neq 0}\to \N

függvény úgy, hogy teljesüljenek az alábbi követelmények:

1.
Tetszőleges RR-beli aa és b≠0Rb\neq 0_R elemekhez található olyan kk hányados és rr maradék RR-ben, hogy
a=kb+ra=kb+r
2.
Az alábbiak közül legalább az egyik teljesül:
r=0Rf(r)<f(b)\begin{aligned} r&=0_R \\ f(r)&<f(b) \end{aligned}

Ekkor ff-et az RR integritástartományon értelmezett euklidészi függvénynek, az aa és bb elemekhez tartozó kk és rr elemek előállítását pedig euklidészi osztásnak vagy maradékos osztásnak nevezzük. Amennyiben RR-hez létezik ilyen tulajdonságú ff függvény, úgy RR-et euklidészi gyűrűnek nevezzük.

Megnézem a tudásbázisban

♣

Megjegyzés:

Az euklidészi gyűrű fogalmának bevezetése mögött tehát az a motiváció, hogy az euklidészi algoritmus ne csak a nemnegatív egész számok halmazán működhessen, hanem azt az ff euklidészi függvény segítségével ki lehessen terjeszteni integritástartományok lehetőleg minél szélesebb körére is.

Ez azáltal válik lehetségessé, hogy a maradékokhoz az ff függvény természetes számokat rendel hozzá, miközben olyan követelményeknek tesz eleget, amely követelmények biztosítják azt, hogy az eljárás véges számú lépés után garantáltan befejeződjön. Ezt a 17.18. Tételben fogjuk precízen kimondani és bizonyítani.

Fontos megjegyezni még, hogy egy euklidészi gyűrűnek, mint algebrai struktúrának nem része a konkrét euklidészi függvény. A definíció szerint elegendő, ha létezik ilyen függvény az adott gyűrűhöz. Sőt, egy euklidészi gyűrűhöz sok esetben több euklidészi függvény is értelmezhető.

Általában azonban igen nehéz annak eldöntése, hogy egy RR integritástartomány euklidészi gyűrű-e vagy sem. Természetesen ha találunk egy olyan függvényt, amely euklidészi, akkor RR nyilván euklidészi gyűrű. Ha azonban nem találunk ilyen függvényt, akkor ez még önmagában nem elég a nemleges válaszhoz. Ehhez azt kéne igazolni, hogy ilyen függvény egyáltalán nem is létezik az adott RR-hez. Ez számos nyitott kérdéshez és sejtéshez vezet, melyek a mai napig bizonyítatlanul várják az utókor ötleteit.

Megnézem a tudásbázisban

♣

Most azt fogjuk megvizsgálni, hogy miért olyan fontosak az euklidészi gyűrűk a számelmélet alaptétele szempontjából. Például azért, mert – ahogyan azt a most következő tételben ki is mondjuk – ezekben bármely két elemnek létezik kitüntetett közös osztója, és emiatt a 17.12. és a 16.18. Tételek értelmében teljesül bennük a számelmélet alaptételének egyértelműségi állítása.

17.18. Tétel:

Legyen RR tetszőleges euklidészi gyűrű. Ekkor RR-ben bármely két elemnek létezik kitüntetett közös osztója.

Megnézem a tudásbázisban

♣

Bizonyítás:

Legyen aa és bb az RR két tetszőleges eleme, és jelöljük 0R0_R-rel a nullelemet. Az általánosság megsértése nélkül feltételezhetjük, hogy a≠0Ra\neq 0_R és b≠0Rb\neq 0_R, minden más esetben ugyanis a 17.6. Tételből azonnal megkapjuk a keresett kitüntetett közös osztót.

Mivel RR euklidészi gyűrű, ezért a 17.17. Definíció 1. pontja szerint aa és bb között elvégezhető a maradékos osztás egy valamilyen ff euklidészi függvény szerint. Azaz RR-ben létezik k1k_1 hányados és r1r_1 maradék RR-ben úgy, hogy teljesüljön az alábbi egyenlet:

a=k1b+r1a=k_1b+r_1

Ekkor a 17.17. Definíció 2. pontja szerint az alábbiak közül legalább az egyik teljesül:

r1=0Rf(r1)<f(b)\begin{aligned} r_1&=0_R \\ f(r_1)&<f(b) \end{aligned}

Ha r1=0Rr_1=0_R, akkor a 17.13. Tétel, valamint a 17.6. Tétel 4. pontja alapján bb lesz a kitüntetett közös osztó, hiszen

(a,b)∼(b,r1⏟=a−k1b)∼(b,0R⏟=r1)∼b(a,b)\sim (b,\underbrace{r_1}_{=a-k_1b})\sim (b,\underbrace{0_R}_{=r_1})\sim b

Ha viszont r1≠0Rr_1\neq 0_R, akkor egyrészt a 17.17. Definíció 2. pontja értelmében szükségképpen teljesül az alábbi szigorú egyenlőtlenség:

f(b)>f(r1)f(b)>f(r_1)

Másrészt pedig a 17.17. Definíció 1. pontja alapján ezúttal bb és r1r_1 között ismét elvégezhető az ff szerinti maradékos osztás.

Ezt az eljárást mindaddig folytatjuk, amíg meg nem kapjuk a nullelemet maradékként valamelyik lépésben. Ekkor – ismételten a 17.13. Tétel, és a 17.6. Tétel 4. pontja miatt – az utolsó olyan maradék lesz a kitüntetett közös osztó, amely nem a nullelem.

Az eljárás garantáltan véget fog érni véges számú lépés után, máskülönben a maradékos osztások során előállna az alábbi, természetes számokból álló végtelen sorozat:

f(b)>f(r1)>f(r2)>f(r3)>…f(b)\gt f(r_1)\gt f(r_2)\gt f(r_3)\gt \ldots

Ez N\N-nek egy olyan részhalmaza lenne, amelynek a 17.16. Tétel miatt nincs minimuma, ami viszont a 17.15. Tétel alapján lehetetlen. Így az euklidészi algoritmus garantáltan leáll véges számú lépés után, és előállítja az aa és bb kitüntetett közös osztóját, amely tehát az utolsó nemnulla maradék lesz.

Megnézem a tudásbázisban

∎

A 17.8. szakaszban meg fogjuk mutatni, hogy ennél több is igaz. Nevezetesen: nemcsak a számelmélet alaptételének egyértelműségi állítása, hanem a felbontások létezése is garantált euklidészi gyűrűkben. Először azonban azt igazoljuk, hogy az egész számok gyűrűje is euklidészi.

17.7Euklidészi függvény a Z\Z gyűrűn

A 15.18. Tételben definiált teljes rendezés segítségével most egy függvényt fogunk értelmezni a Z\Z halmazon, majd megmutatjuk, hogy az egy euklidészi függvény. Nézzük először a kérdéses függvényt.

17.19. Definíció (Az egész számok abszolútértéke):

Definiáljunk egy f:Z→Nf:\Z \to \N függvényt a következőképpen:

f(a)={aha a≥0−aha a<0f(a) = \begin{cases} a &\text{ha } a\geq 0 \\ -a &\text{ha } a\lt 0 \end{cases}

Ekkor az f(a)f(a) természetes számot az aa egész szám abszolút értékének, az ff függvényt pedig abszolútérték-függvénynek nevezzük. Az aa egész szám abszolút értékének jelölése: ∣a∣|a|.

Megnézem a tudásbázisban

♣

Amennyiben tehát az egész számokat a mindkét irányban végtelen számegyenesen ábrázoljuk, akkor ez a függvény intuitív módon a 00 egész számtól való távolságot méri ezen az egyenesen. Ez alapján például az 55 és a −5-5 egész számok egyaránt 55 távolságra vannak a 00-tól, azaz

∣5∣=∣−5∣=5|5|=|-5|=5

Ezt szemlélteti a 17.4. ábra.

Abszolútérték a számegyenesen
17.4. ábra: Abszolútérték a számegyenesen

Az abszolútérték-függvénynek a következő tétel miatt van jelentősége számunkra.

17.20. Tétel:

A 17.19. Definíció szerinti f(a)=∣a∣f(a)=|a| abszolútérték-függvény egy euklidészi függvény a Z\Z gyűrűn, azaz Z\Z euklidészi gyűrű.

Megnézem a tudásbázisban

♣

Megjegyzés:

Ha egészen precízek akarunk lenni, akkor valójában nem pontosan a tételben szereplő ff függvény, hanem annak a nemnulla egész számokat tartalmazó halmazra történő megszorítása euklidészi. A 17.17. Definícióban található jelölést alkalmazva jelöljük ezt a halmazt Z≠0Z_{\neq 0}-val. Ekkor valójában az alábbi f′:Z≠0→Nf':Z_{\neq 0}\to\N függvényről van szó:

f′(a)={aha a>0−aha a<0f'(a) = \begin{cases} a &\text{ha } a\gt 0 \\ -a &\text{ha } a\lt 0 \end{cases}

Ez tehát pusztán abban különbözik a 17.19. Definícióban szereplő abszolútérték-függvénytől, hogy nincs értelmezve a 00-ra. Ám a tétel bizonyításában ezt nem használjuk ki, így az egyszerűség kedvéért ettől az apróságtól eltekintünk.

Megnézem a tudásbázisban

♣

Bizonyítás:

A 17.17. Definíció 1. pontja alapján egyrészt azt kell megmutatni, hogy tetszőleges aa és b≠0b\neq 0 egész számokhoz léteznek kk és rr egész számok úgy, hogy teljesül az alábbi egyenlet:

a=kb+ra=kb+r

Másrészt pedig a 17.17. Definíció 2. pontja alapján azt is meg kell mutatni, hogy emellett legalább az egyik teljesül az alábbiak közül:

r=0∣r∣<∣b∣\begin{aligned} r&=0 \\ |r|&<|b| \end{aligned}

Mivel a Z\Z gyűrűben vagyunk, és a 17.19. Definíció alapján r=0r=0 ekvivalens ∣r∣=0|r|=0-val, ezért ez utóbbi feltétel az alábbi rövidebb alakban is leírható:

0≤∣r∣<∣b∣0\leq |r|<|b|

A bizonyítás további részében ezt az alakot fogjuk használni.

A bizonyítás konstruktív lesz, azaz kk és rr létezését azáltal igazoljuk, hogy egy eljárást mutatunk a kiszámításukra. Ez az eljárás a gyakorlatban nem lenne túl hatékony, ám nekünk a bizonyításhoz épp elegendő lesz. Továbbá ki fogjuk használni, hogy a 15.18. Tételben definiált ≤\leq reláció teljesíti a 15.11. Definícióban megfogalmazott rendezési axiómákat.

Először szorítkozzunk arra az esetre, amikor egyik bemeneti számunk sem negatív, azaz teljesülnek az alábbiak:

0≤a0<b\begin{aligned} 0&\leq a \\ 0&\lt b \end{aligned}

Az eljárás lényege, hogy a hányadost és a maradékot próbálgatással keressük meg az alábbi lépéseket végrehajtva:

a=0b+a⏟=r0a=1b+(a−b)⏟=r1a=2b+(a−2b)⏟=r2⋮a=kib+(a−kib)⏟=ria=ki+1b+(a−ki+1b)⏟=ri+1⋮\begin{aligned} a&=0b+\underbrace{a}_{=r_0} \\ a&=1b+\underbrace{(a-b)}_{=r_1} \\ a&=2b+\underbrace{(a-2b)}_{=r_2} \\ &\vdots \\ a&=k_ib+\underbrace{(a-k_ib)}_{=r_i} \\ a&=k_{i+1}b+\underbrace{(a-k_{i+1}b)}_{=r_{i+1}} \\ &\vdots \end{aligned}

Itt az ii-edik lépésben kipróbált hányados-jelöltet kik_i-vel, míg az ugyanebben a lépésben kipróbált maradék-jelöltet rir_i-vel jelöltük.

Nyilván mindegyik egyenlet teljesül, hiszen minden lépésben tulajdonképpen annyi történik, hogy a jobboldalhoz hozzá is adunk, és ki is vonunk bb-t. Csak épp a hozzáadást a hányados-jelölt 11-gyel történő megnövelésével, míg a kivonást a maradék-jelölt bb-vel történő csökkentésével érjük el. Emiatt az ii-edik lépésből az i+1i+1-edik lépésbe így jutunk:

ki+1=ki+1ri+1=ri−b\begin{aligned} k_{i+1}&=k_i+1 \\ r_{i+1}&=r_i-b \end{aligned}

Az eljárás megkezdésekor a kiinduló állapot: k0=0k_0=0 és r0=ar_0=a.

Az eljárást mindaddig nem fejezzük be, ameddig az aktuális rir_i maradék-jelöltre már igaz nem lesz, hogy ri<br_i<b. A befejezés előtti lépésekben tehát még b≤rib\leq r_i, és ezekben az esetekben, mivel a 15.11. Definíció szerinti 1. rendezési axióma alapján a ≤\leq reláció kompatibilis az összeadással, ezért teljesül az alábbi:

0≤ri−b⏟=ri+10\leq \underbrace{r_i-b}_{=r_{i+1}}

Azaz egyrészt minden újabb lépésben folyamatosan nemnegatív maradék-jelölteket kapunk, azok tehát mindannyian természetes számok.

Másrészt, mivel ri+1=ri−br_{i+1}=r_i-b, ezért ri+1+b=rir_{i+1}+b=r_i, de ugye a bizonyítás elején egyelőre kikötöttük, hogy 0<b0<b, emiatt:

ri+1<rir_{i+1}<r_i

Azaz minden újabb lépésben szigorúan kisebb maradék-jelölteket kapunk, mint az azt megelőző lépésben.

Az eljárás emiatt nyilván véges számú lépés után garantáltan befejeződik, máskülönben egy végtelen leszálló természetes számokból álló sorozatot kapnánk, ami a 17.15. Tétel miatt ellentmondás. Az utolsó lépésben tehát az előbbiek alapján kaptunk egy olyan kk hányadost és rr maradékot, amelyekre teljesül, hogy

a=kb+r0≤r<b\begin{aligned} a&=kb+r \\ 0&\leq r\lt b \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<b0<b – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0≤∣r∣⏟=r<∣b∣⏟=b0\leq \underbrace{|r|}_{=r}<\underbrace{|b|}_{=b}

Azaz ebben az esetben teljesülnek a euklidészi függvényre vonatkozó követelmények.

Eddig tehát azt az esetet fedtük le, amikoris 0≤a0\leq a és 0<b0\lt b. Ennek az eredménynek az általánosítása a többi előjel-kombinációra már egyszerű. Az alábbiakban ennek technikai részleteit ismertetjük.

0≤a  eˊs  b<00\leq a ~~\text{és}~~ b\lt 0

Ekkor a 15.9. Lemma 1. pontja miatt 0<(−b)0\lt (-b), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor bb helyét (−b)(-b) veszi át. Az utolsó lépésben így kapunk egy olyan kk hányadost és rr maradékot, amelyekre teljesülnek az alábbiak:

a=k(−b)+r0≤r<(−b)\begin{aligned} a&=k(-b)+r \\ 0&\leq r\lt (-b) \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<(−b)0<(-b) – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0≤∣r∣⏟=r<∣−b∣⏟=(−b)0\leq \underbrace{|r|}_{=r}<\underbrace{|-b|}_{=(-b)}

Nekünk azonban aa-nak (−b)(-b) helyett a bb-vel történő maradékos osztására, és ezért a ∣−b∣|-b| helyett a ∣b∣|b| abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 3. pontja, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a=(−k)b+r0≤∣r∣<∣b∣⏟=∣−b∣\begin{aligned} a&=(-k)b+r \\ 0&\leq |r|\lt \underbrace{|b|}_{=|-b|} \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a≤0  eˊs  0<ba\leq 0 ~~\text{és}~~ 0\lt b

Ekkor a 15.9. Lemma 1. pontja miatt 0≤(−a)0\leq (-a), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor aa helyét (−a)(-a) veszi át. Az utolsó lépésben így kapunk egy olyan kk hányadost és rr maradékot, amelyekre teljesülnek az alábbiak:

(−a)=kb+r0≤r<b\begin{aligned} (-a)&=kb+r \\ 0&\leq r\lt b \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<b0<b – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0≤∣r∣⏟=r<∣b∣⏟=b0\leq \underbrace{|r|}_{=r}<\underbrace{|b|}_{=b}

Nekünk azonban (−a)(-a) helyett aa-nak a bb-vel történő maradékos osztására van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5. és 3. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a=(−k)b+(−r)0≤∣−r∣⏟=∣r∣<∣b∣\begin{aligned} a&=(-k)b+(-r) \\ 0&\leq \underbrace{|-r|}_{=|r|}\lt |b| \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a≤0  eˊs  b<0a\leq 0 ~~\text{és}~~ b\lt 0

Ekkor a 15.9. Lemma 1. pontja miatt 0<(−b)0\lt (-b) és 0≤(−a)0\leq (-a), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor aa helyét (−a)(-a) és bb helyét (−b)(-b) veszi át. Az utolsó lépésben így kapunk egy olyan kk hányadost és rr maradékot, amelyekre teljesülnek az alábbiak:

(−a)=k(−b)+r0≤r<(−b)\begin{aligned} (-a)&=k(-b)+r \\ 0&\leq r\lt (-b) \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<(−b)0<(-b) – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0≤∣r∣⏟=r<∣−b∣⏟=(−b)0\leq \underbrace{|r|}_{=r}<\underbrace{|-b|}_{=(-b)}

Nekünk azonban (−a)(-a) helyett aa-nak a (−b)(-b) helyett bb-vel történő maradékos osztására, és ezért a ∣−b∣|-b| helyett a ∣b∣|b| abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5., 3. és 4. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

a=kb+(−r)0≤∣−r∣⏟=∣r∣<∣b∣⏟=∣−b∣\begin{aligned} a&=kb+(-r) \\ 0&\leq \underbrace{|-r|}_{=|r|}\lt \underbrace{|b|}_{=|-b|} \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

Ezzel már minden esetet lefedtünk, azaz tetszőleges aa és b≠0b\neq 0 elemek között elvégezhető az abszolútérték-függvény szerinti maradékos osztás. Ez a függvény tehát valóban egy euklidészi függvény a Z\Z gyűrűn.

Megnézem a tudásbázisban

∎

Most tehát már tudjuk, hogy az egész számok gyűrűje egy euklidészi gyűrű, és így – mint ahogyan azt a 17.6. szakaszban megemlítettük – teljesül benne a számelmélet alaptételének egyértelműségi állítása.

17.8A számelmélet alaptétele euklidészi gyűrűkben

A számelmélet alaptételének egyértelműségi állítása pusztán annyit állít, hogy ha egy elemnek létezik felbontása, akkor az a tényezők sorrendjétől és asszociáltságtól eltekintve egyértelmű a 16.16. Definíció szerinti értelemben. Semmit nem mond azonban arról, hogy bármely elemnek egyáltalán létezik-e ilyen felbontása. Most azt fogjuk igazolni, hogy euklidészi gyűrűkben a felbontás létezése is garantált. Ehhez a kulcsot a következő tétel fogja jelenteni.

17.21. Tétel:

Legyen RR tetszőleges euklidészi gyűrű, és jelöljük RR nullelemét 0R0_R-rel. Ekkor RR-hez létezik olyan gg euklidészi függvény, amely a 17.17. Definícióban megfogalmazott követelményeken kívül tetszőleges aa és b≠0Rb\neq 0_R elemekre teljesíti az alábbi monotonitási tulajdonságot is:

g(a)≤g(ab)g(a)\leq g(ab)

Ilyenkor gg-t monoton euklidészi függvénynek nevezzük – amikor tehát a nemnulla elemekkel való szorzás nem csökkenti az euklidészi függvény értékét.

Megnézem a tudásbázisban

♣

Bizonyítás:

Legyen ff egy tetszőleges euklidészi függvény RR-hez. Ilyen ugye létezik, mivel RR euklidészi gyűrű. A bizonyítás konstruktív lesz, azaz ff felhasználásával definiálni fogunk egy olyan gg függvényt, amely maga is euklidészi függvény, de ezen felül teljesíti a tételben szereplő monotonitási tulajdonságot is.

Tegyük fel, hogy valamilyen tetszőleges kk elemre szeretnénk kiszámítani a g(k)g(k) függvényértéket. Ehhez először képezzük a kk elem összes nemnulla többszörösének az ff függvény szerinti értékét, azaz minden RR-beli x≠0x\neq 0 elemre kiszámítjuk az f(kx)f(kx) természetes számokat. Ezután válasszuk g(k)g(k) értékének ezek közül a legkisebbet, amely ugye a 17.15. Tétel miatt biztosan létezik. Más szavakkal a g(k)g(k) függvényérték legyen az eredeti ff függvénynek a kk elem nemnulla többszörösein felvett minimuma.

A gg függvény iménti definíciója alapján tehát a tételben szereplő aa és b≠0Rb\neq 0_R elemek esetén létezik olyan c≠0Rc\neq 0_R elem, amelyre g(ab)=f(abc)g(ab)=f(abc) teljesül. Nevezetesen épp az a cc elem, amelyre az f(abc)f(abc) felveszi a minimumát.

Mivel ugyanakkor az abcabc szorzat az abab elemen kívül az aa elemnek is egy nemnulla többszöröse, ezért ismét a gg függvény fenti definíciója miatt:

g(a)≤f(abc)g(a)\leq f(abc)

De mivel azt mondtuk, hogy g(ab)=f(abc)g(ab)=f(abc), ezért valóban fennáll a tételben szereplő egyenlőtlenség:

g(a)≤g(ab)⏟=f(abc)g(a)\leq \underbrace{g(ab)}_{=f(abc)}

Már csak annyit kell igazolni, hogy maga gg is euklidészi függvény RR-hez. Legyen b≠0Rb\neq 0_R egy tetszőleges nemnulla RR-beli elem, valamint válasszuk ki bb-nek egy olyan nemnulla többszörösét, amelyre az eredeti ff euklidészi függvény épp a minimumát veszi fel. Ez ugye biztosan létezik, mint azt már láttuk fentebb. Azaz válasszunk ki egy olyan c≠0Rc\neq 0_R elemet, amelyre

g(b)=f(bc)g(b)=f(bc)

Minthogy b≠0Rb\neq 0_R és c≠0Rc\neq 0_R ezért a nullosztómentesség miatt bc≠0Rbc\neq 0_R. Azaz tetszőleges aa elem maradékosan elosztható a bcbc elemmel az eredeti ff euklidészi függvény szerint. Ez azt jelenti, hogy létezik olyan kk hányados és rr maradék, amelyekre teljesül az alábbi egyenlet:

a=k⋅(bc)+ra=k\cdot (bc) + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r=0Rf(r)<f(bc)\begin{aligned} r&=0_R \\ f(r)&\lt f(bc) \end{aligned}

Az általánosság megsértése nélkül feltehetjük, hogy r≠0Rr\neq 0_R, és így az ff-re vonatkozó egyenlőtlenség áll fenn, máskülönben a további lépésekben amúgysem nyernénk semmilyen további információt gg-ről.

Egyrészt a gg függvény definíciója miatt g(r)≤f(r)g(r)\leq f(r), hiszen rr a 16.2. Tétel 1. pontja alapján önmagának is többszöröse. Másrészt viszont a cc elemet épp úgy választottuk ki, hogy f(bc)=g(b)f(bc)=g(b) teljesüljön. Létezik tehát olyan hányados – nevezetesen kckc – és maradék – nevezetesen rr –, amelyre teljesülnek az alábbiak:

a=(kc)⋅b+rg(r)⏟≤f(r)<g(b)⏟=f(bc)\begin{aligned} a&=(kc)\cdot b + r \\ \underbrace{g(r)}_{\leq f(r)}&\lt \underbrace{g(b)}_{=f(bc)} \end{aligned}

Azaz tetszőleges aa elem tetszőleges b≠0Rb\neq 0_R elemmel maradékosan elosztható a gg függvény szerint is, így gg valóban egy euklidészi függvény.

Megnézem a tudásbázisban

∎

Az iménti tételben szereplő monotonitási tulajdonság tehát azt jelenti, hogy egy ilyen euklidészi függvény tetszőleges elem bármely nemnulla többszörösére legalább akkora "nagyságot" fog "mérni", mint magára az elemre. A most következő tétel arra ad választ, hogy mely esetekben teljesül egyenlőség a két oldal között, és mely esetekben nem.

17.22. Tétel:

Legyen RR tetszőleges euklidészi gyűrű, gg pedig egy monoton euklidészi függvény RR-hez, amelyre tehát teljesül a 17.21. Tétel szerinti monotonitási tulajdonság. Jelöljük RR nullelemét 0R0_R-rel.

Ekkor tetszőleges a≠0Ra\neq 0_R és b≠0Rb\neq 0_R elemek esetén

g(a)=g(ab)g(a)=g(ab)

akkor és csak akkor teljesül, ha bb egység.

Minden más esetben szigorú egyenlőtlenség áll fenn, azaz

g(a)<g(ab)g(a)\lt g(ab)

Megnézem a tudásbázisban

♣

Bizonyítás:

Ha bb egység, akkor a 16.5. Tétel értelmében osztója az egységelemnek. Létezik tehát olyan cc elem, amelyre bc=1bc=1 teljesül. Mivel c≠0Rc\neq 0_R – máskülönben a 15.1. Tétel 1. pontja alapján a bcbc szorzat a nullelem lenne –, ezért a gg euklidészi függvény monotonitási tulajdonsága miatt:

g(ab)≤g(abc⏟=1)=g(a)g(ab)\leq g(a\underbrace{bc}_{=1})=g(a)

Ugyanakkor szintén a monotonitási tulajdonság miatt:

g(a)≤g(ab)g(a)\leq g(ab)

Mindkét irányban fennáll tehát a ≤\leq reláció, így az antiszimmetria miatt szükségképpen

g(a)=g(ab)g(a)=g(ab)

Visszafelé: Tegyük fel indirekt, hogy bb nem egység, ám ennek ellenére

g(a)=g(ab)g(a)=g(ab)

Mivel aa-ról és bb-ről a tétel szövege alapján tudjuk, hogy egyik sem a nullelem, ezért a nullosztómentesség miatt az abab szorzat sem lehet az. Emiatt az aa elem maradékosan elosztható az abab elemmel a gg euklidészi függvény szerint. Azaz létezik olyan kk hányados és rr maradék, hogy teljesül az alábbi egyenlet

a=kab+ra=kab + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r=0Rg(r)<g(ab)\begin{aligned} r&=0_R \\ g(r)&\lt g(ab) \end{aligned}

Az általánosság megsértése nélkül feltehetjük, hogy r≠0Rr\neq 0_R, és így a gg-re vonatkozó egyenlőtlenség áll fenn, máskülönben a további lépésekben amúgysem nyernénk semmilyen további információt gg-ről.

Az egyenlet mindkét oldalából kabkab-t levonva ezt kapjuk:

a−kab=ra-kab=r

A baloldalt a disztributivitási szabályok miatt így írhatjuk át:

a⋅(1−kb)=ra\cdot (1-kb)=r

Mivel bb-ről indirekt azt mondtuk, hogy nem egység, ezért a 16.5. Tétel miatt nem lehet osztója az egységelemnek. Emiatt kb≠1kb\neq 1, és így 1−kb1-kb biztosan nem a nullelem. Minthogy a tétel szöveg alapján aa sem a nullelem, ezért a nullosztómentesség miatt rr az aa-nak egy nemnulla többszöröse – egész konkrétan 1−kb1-kb-szerese –, és így a gg euklidészi függvény monotonitási tulajdonsága miatt teljesül a következő egyenlőtlenség:

g(a)≤g(r⏟=a⋅(1−kb))g(a)\leq g(\underbrace{r}_{=a\cdot (1-kb)})

Ugyanakkor indirekt feltételeztük, hogy g(a)=g(ab)g(a)=g(ab), így a fentebbi maradékos osztásból kapott g(r)<g(ab)g(r)\lt g(ab) szigorú egyenlőtlenségből

g(r)<g(a)g(r)\lt g(a)

következik.

Ez ellentmondás, hiszen g(r)g(r) nem lehet egyszerre legalább akkora, mint g(a)g(a), és határozottan kisebb is nála. Az indirekt feltételezésünk hibás volt, azaz a g(a)=g(ab)g(a)=g(ab) egyenlőség nem állhat fenn, amennyiben bb nem egység.

Megnézem a tudásbázisban

∎

Az iménti két tételt felhasználva már könnyedén beláthatjuk ennek a résznek a főtételét, amely az euklidészi gyűrűk legfontosabb tulajdonságát mondja ki.

Bizonyítás:

Legyen RR valamilyen euklidészi gyűrű. A 17.18. Tétel alapján RR-ben bármely két elemnek létezik kitüntetett közös osztója. Így a 17.12. Tétel miatt minden felbonthatatlan elem prím. Ebből viszont a 16.18. Tétel szerint következik a számelmélet alaptételének egyértelműségi állítása. Ha tehát valamely elemnek egyáltalán létezik felbontása, akkor az sorrendtől és asszociáltságtól eltekintve egyértelmű.

Így már csak azt kell megmutatni, hogy bármely nemnulla és nem egység elemnek ténylegesen létezik felbontása. Tegyük fel, hogy gg egy olyan euklidészi függvény, amely eleget tesz a 17.21. Tételben szereplő monotonitási tulajdonságnak is. Ilyen euklidészi függvény ugyanezen tétel miatt garantáltan létezik. A bizonyításhoz a gg norma értékkészletén, azaz a természetes számok N\N halmazán fogunk teljes indukciót alkalmazni.

Ennek során minden nn természetes számra megmutatjuk, hogy RR összes olyan nemnulla és nem egység elemének létezik prímtényezős felbontása, amelynek a gg euklidészi függvény szerinti értéke legfeljebb nn. A 17.5. ábrán az RR elemeinek azon A0A_0, A1A_1, A2A_2, ... részhalmazai láthatók, amelyek az első néhány természetes számhoz tartoznak ebben az értelemben. Az elemeket pontokkal jelöltük, valamint ábrázoltuk a gg által hozzájuk rendelt értékeket is.

A teljes indukció vázlata
17.5. ábra: A teljes indukció vázlata

Először is indukciós feltételként feltesszük, hogy valamilyen nn-re már igaz az állítás, azaz bármely nn-nél nemnagyobb gg-értékű nemnulla és nem egység elemnek létezik prímtényezős felbontása. Ezt az elemhalmazt a fenti ábrán AnA_n-nel jelöltük. Azt kell megmutatnunk, hogy ekkor az An+1A_{n+1} halmaz elemeire is teljesülni fog az állítás. Tegyük fel, hogy aa egy tetszőleges An+1A_{n+1}-beli elem. Feltételezhetjük, hogy nincs benne AnA_n-ben, hiszen máskülönben az indukciós feltétel miatt róla már amúgyis tudnánk, hogy létezik prímtényezős felbontása. Így tehát:

g(a)=n+1g(a)=n+1

Ha aa felbonthatatlan, akkor az ő prímtényezős felbontása alatt a 16.16. Definíció alapján önmagát, mint "egytényezős szorzatot" értjük, így az nyilván létezik. Feltételezhetjük tehát, hogy aa nem felbonthatatlan, azaz felírható a=bca=bc alakban úgy, hogy bb és cc közül egyik sem egység.

Ekkor azonban a gg euklidészi függvényre a 17.22. Tétel miatt fennállnak az alábbi szigorú egyenlőtlenségek, hiszen aa nem egységszerese sem bb-nek, sem pedig cc-nek:

g(b)<g(a)g(c)<g(a)\begin{aligned} g(b)&\lt g(a) \\ g(c)&\lt g(a) \end{aligned}

Ez viszont g(a)=n+1g(a)=n+1 miatt azt jelenti, hogy

g(b)≤ng(c)≤n\begin{aligned} g(b)&\leq n \\ g(c)&\leq n \end{aligned}

Az indukciós feltétel alapján azonban emiatt bb-nek és cc-nek létezik prímtényezős felbontása, hiszen mindketten benne vannak az AnA_n halmazban. Így ha az a=bca=bc szorzatba bb és cc helyére beírjuk e két felbontást, akkor épp aa-nak a felbontását kapjuk.

Eddig tehát azt bizonyítottuk, hogy ha valamilyen nn-re az AnA_n halmaz minden elemének létezik felbontása, akkor ez igaz lesz az őt tartalmazó An+1A_{n+1} halmaz elemeire is. Már csak el kell indítani az indukciós "dominósor" ledöntését, azaz meg kell mutatni, hogy n=0n=0-ra valóban teljesül a tétel állítása.

Az n=0n=0 esethez az A0A_0 halmaz tartozik, amely tehát azokat a nemnulla és nem egység elemeket tartalmazza, amelyeknek a gg-értéke legfeljebb 00. Tegyük fel indirekt, hogy ezek között mégis létezik egy olyan xx elem, amelynek nem létezik prímtényezős felbontása. Minthogy az A0A_0 halmaz definíciója miatt g(x)≤0g(x)\leq 0, ugyanakkor g(x)g(x) csak nemnegatív szám lehet, mivel a gg függvény N\N-be képez, ezért ez azt jelenti, hogy valójában

g(x)=0g(x)=0

Jelöljük 1R1_R-rel az RR egységelemét, és végezzük el a gg euklidészi függvény szerinti maradékos osztást 1R1_R és xx között. Ez megtehető, hiszen RR euklidészi gyűrű. Létezik tehát olyan kk hányados és rr maradék, hogy teljesül az alábbi egyenlet:

1R=kx+r1_R=kx+r

Továbbá az alábbiak közül legalább az egyik teljesül:

r=0Rg(r)<g(x)⏟=0\begin{aligned} r&=0_R \\ g(r)&< \underbrace{g(x)}_{=0} \end{aligned}

Az egyenlőtlenség nem teljesülhet, hiszen – mint már említettük – a gg függvény N\N-be képez, és emiatt semmilyen gg-érték nem lehet 00-nál kisebb. Ezért tehát szükségképpen r=0Rr=0_R, azaz

1R=kx+0R⏟=r1_R=kx+\underbrace{0_R}_{=r}

Tehát valójában azt kaptuk, hogy xx osztója az egységelemnek, azaz a 16.5. Tétel alapján egység. Ez viszont ellentmondás, mivel azt mondtuk, hogy az A0A_0 halmazban csak nemnulla és nem egység elemek vannak.

Azt kaptuk tehát, hogy az A0A_0 halmazra igaz lesz a tétel állítása. Ekkor azonban a már bizonyított indukciós lépés miatt igaz lesz A1A_1-re is, majd emiatt A2A_2-re is, és így tovább, egészen a végtelenségig. Minthogy a gg euklidészi függvény összes lehetséges értékét lefedtük, ezért biztosan nem hagytunk ki egyetlen nemnulla és nem egység elemet sem a buliból. Mindegyikre igaz tehát a prímtényezős felbontás létezése, és így a számelmélet alaptétele.

Megnézem a tudásbázisban

∎

Ez a tétel egy elégséges feltételt biztosít ahhoz, hogy egy integritástartományban teljesüljön a számelmélet alaptétele. Megjegyezzük azonban, hogy ez a feltétel nem szükséges az alaptételhez. Léteznek olyan integritástartományok is, amelyekben semmilyen értelemben nem végezhető el a maradékos osztás, és így nem euklidészi gyűrűk, ám mégis teljesül bennük a számelmélet alaptétele.

Ebben a fejezetben megismerkedtünk a kitüntetett közös osztó fogalmával, és az euklidészi algoritmussal, amely azt képes hihetetlen sebességgel kiszámítani. A kitüntetett közös osztó azért volt nagyon fontos számunkra, mert annak létezéséből már következik a számelmélet alaptételének egyértelműségi állítása. Ezért általánosságban is megvizsgáltuk, mi kell ahhoz, hogy az euklidészi algoritmus valamilyen integritástartományon működhessen. Ezzel eljutottunk a maradékos osztás és az euklidészi gyűrű fogalmához, és megmutattuk, hogy az ilyen gyűrűkben mindig teljesül a számelmélet alaptételének mindkét állítása. Ezen túlmenően igazoltuk, hogy az egész számok gyűrűje is euklidészi gyűrű – például az abszolútérték-függvényre, mint euklidészi függvényre nézve.

A 9. fejezetben a Diffie-Hellman kulcscsere protokoll kapcsán már felületesen megismerkedtünk az úgynevezett óra-, vagy becsületesebb nevén moduláris aritmetikával. Ez szintén egy fontos összetevője az aszimmetrikus kulcsú titkosítási eljárásoknak, ezért a következő fejezetben ezt a témakört újra elővesszük. Ám ezt ezúttal a gyűrűk absztrakciós szintjén fogjuk megtenni, melynek keretében megismerkedünk az úgynevezett maradékosztálygyűrűkkel és ideálokkal.