Ha részcsoport, akkor teljesíti a feltételeit, így a műveleti zártságot is. Visszafelé: Tegyük fel, hogy olyan részhalmaz, amely zárt a csoportműveletre nézve, legyen tetszőleges -beli elem, továbbá jelöljük egységelemét -vel. Mivel véges, ezért -nek nem …
Jelöljük -vel azt a halmazt, amely olyan egész számokból áll, amelyekre teljesül az alábbi: Azaz azon kitevők halmaza, amelyekre a elemet emelve a csoport egységelemét kapjuk. Az halmaz zárt az egész számok összeadására nézve, hiszen …
A bizonyításban a ben definiált baloldali mellékosztályokat fogjuk használni, de értelemszerűen ugyanígy használhatnánk a jobboldali mellékosztályokat is. Az említett tételben definiált reláció egy ekvivalenciareláció, melynek ekvivalencia-osztályai a szerinti baloldali mellékosztályok. Ezek az ekvivalenciarelációkról szóló alapján …
A alapján azt kell tehát bizonyítani, hogy a szimbólummal jelölt reláció reflexív (), tranzitív () és szimmetrikus (). Az alábbiakban legyenek , és a csoport tetszőleges elemei, az egységelemet pedig jelöljük -vel. A bizonyítás során …
Egyrészt az általánosság megsértése nélkül feltehetjük, hogy , ebben az esetben ugyanis a tétel nyilvánvalóan igaz. Továbbá azt is feltehetjük, hogy , mivel ebben az esetben a feltétel alapján csak lehet, és ekkor a tétel …
Mivel , ezért , és így a alapján egy véges nemnegatív szám, amiről a tétel szövege alapján tudjuk, hogy nemnulla, tehát . Jelöljük ezt a számot -val, azaz vezessük be az alábbi jelölést: Ez a …
Tegyük fel, hogy részcsoport -ben. Ekkor a műveleti zártság – azaz az 1. tulajdonság – nyilvánvalóan teljesül, máskülönben nem lenne csoport a műveletére nézve, és így részcsoport sem lehetne -ben. Mivel -nak létezik egységeleme – …
Ha -vel jelöljük a művelet neutrális elemét, akkor egyrészt: Másrészt: Azaz a alapján és valóban egymás inverzei. Ha és felcserélhetők, akkor pedig nyilván is igaz.
Legyen egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges redukált maradékosztály. Képezzük azt az kitevőt és páratlan számot, amelyekre teljesülnek az alábbiak: Azt kell igazolni, hogy nem lehet Miller-Rabin-tanú, azaz az alábbi kongruenciák közül …
Azt a jól ismert azonosságot fogjuk használni, miszerint bármilyen kommutatív gyűrű tetszőleges és elemeire teljesül az alábbi: Ez a ben szereplő gyűrűaxiómák közvetlen következménye, amelyet most le is ellenőrzünk. Rögtön alkalmazhatjuk az 5. pontban lévő …
Tegyük fel, hogy összesen darab olyan modulo redukált maradékosztály van, amely nem Fermat-tanú. Legyenek például ezek az alábbiak, amelyek tehát páronként különböző redukált maradékosztályok: Tegyük fel továbbá, hogy -nek létezik legalább egy Fermat-tanúja a redukált …
Képezzük e két maradékosztály szorzatát, azaz az maradékosztályt. A művelet ben ismertetett definíciója alapján ez épp az maradékosztály lesz. Először azt kell bizonyítanunk, hogy ez a maradékosztály Fermat-tanú. Ez a alapján az alábbit jelenti: Az …
Tegyük fel indirekt, hogy nem ez a helyzet, vagyis annak ellenére, hogy és különböznek egymástól, mégiscsak teljesül az alábbi egyenlőség: A művelet ben ismertetett definíciója alapján ez az alábbit jelenti: Az egész számok maradékosztályainak ben …
Előszöris az világos, hogy nemnegatív, hiszen az ő és az ellentettjének a négyzete megegyezik, így ha negatív lenne, akkor nem ő lenne a legnagyobb olyan egész szám, amelyre teljesül. Másodszor biztosan nem lehet nulla sem. …
Először nézzük azt az esetet, amikor pozitív, azaz . Ekkor ugye a alapján. Tegyük fel, hogy -nek létezik -nél nagyobb, de -nél kisebb osztója, amit jelöljünk -val. Azaz egyrészt: Másrészt: Ez az oszthatóság a alapján …
Tegyük fel ugyanis, hogy teljesül a oszthatóság. Ekkor – mivel a oszthatóság nyilvánvalóan teljesül – egy közös osztója lesz -nak és -nak. Mivel a tétel szövege szerint prím – és így a szerint nem egység …
Mivel teljesül az kongruencia, ezért a 3. pontja alapján teljesül az alábbi oszthatóság: Az oszthatóság ja alapján ekkor létezik olyan egész szám, amelyre teljesül az alábbi egyenlet: Mindkét oldalhoz -et adva: Azt kell tehát bizonyítani, …
A kongruencia a 3. pontja alapján az alábbi oszthatóság teljesülését jelenti: Ez az oszthatóság a alapján azt jelenti, hogy létezik olyan egész szám, amelyre teljesül az alábbi egyenlet: Az egyenlet mindkét oldalához -t adva az …
Az függvényről a ben igazoltuk, hogy minden -beli rendezett párhoz pontosan egy -beli maradékosztályt rendel hozzá. Méghozzá azt a maradékosztályt, amely a rendezett pár két komponensének a metszete. A ben pedig azt mutattuk meg, hogy …
A ban felsorolt gyűrűaxiómákat kell ellenőrizni: A művelet kommutativitása könnyedén adódik az , , …, gyűrűkön értelmezett összeadások ugyanezen tulajdonságából: Hasonlóképpen adódik a művelet asszociativitása: És a művelet asszociativitása is: Továbbá a két művelet közötti …
