Az 1. állítás bizonyításához először azt igazoljuk, hogy részcsoport -ben. A alapján ez az alábbi 3 feltétel ellenőrzését jelenti: nemüres Fennáll a tartalmazási reláció zárt a csoport műveletére nézve. Az első feltétel nyilván teljesül, hiszen …
1. eset: valamilyen prímhatvány Ekkor tehát , ahol valamilyen páratlan prímszám, továbbá , máskülönben nem lenne összetett. A modulo redukált maradékosztályok a multiplikatív csoport elemei, melynek rendjét a alapján az Euler-féle -függvény adja meg. Ennek …
A titkos kitevőt tehát alábbi lineáris kongruencia megoldásaként kapjuk: Ennek a kongruenciának a alapján természetesen létezik megoldása, amely a 1. pontja szerint egyértelmű. A továbbiakban azt szeretnénk igazolni, hogy tetszőleges egész szám esetén teljesül az …
Legyen egy pozitív, páratlan prímszám, pedig egy pozitív kitevő, továbbá egy tetszőleges olyan egész szám, amelyre teljesül az alábbi konguencia: Jelöljük -rel az összes olyan egész szám halmazát, amelyeket helyére behelyettesítve fennáll mindkét alábbi kongruencia: …
Legyen tetszőleges pozitív, páratlan prímszám, pedig tetszőleges pozitív kitevő. A nek megfelelően jelöljük -vel azon modulo maradékosztályok halmazát, amelyek NEM Miller-Rabin-tanúi -nek. Ekkor ugye a 2. pontja alapján a multiplikatív csoport egy részcsoportja. E részcsoport …
Legyen egy tetszőleges -nél nagyobb páratlan szám, amelynek darab különböző prímtényezője van, azaz prímtényezős felbontása az alábbi alakban írható fel valamilyen páronként egymástól különböző pozitív, páratlan , , …, prímszámokkal és valamilyen pozitív , , …
Egy pozitív egész szám esetén akkor és csak akkor létezik primitív gyök modulo , ha az alábbiak valamelyike, ahol tetszőleges pozitív, páratlan prímszám, pedig tetszőleges pozitív kitevő:
Egy pozitív összetett egész szám akkor és csak akkor Carmichael-szám, ha négyzetmentes és bármely pozitív prímosztójára teljesül az alábbi oszthatóság:
Legyen tetszőleges kommutatív gyűrű, és jelölje az feletti polinomok halmazát. Ekkor az halmaz a ban bevezetett műveletekkel szintén egy kommutatív gyűrűt alkot, amelyet az feletti polinomgyűrűnek nevezünk. Ezt a gyűrűt az alaphalmazához hasonlóan szintén -szel …
Legyen tetszőleges kommutatív gyűrű, és pedig tetszőleges feletti polinomok a hozzájuk tartozó és polinomfüggvényekkel. Az gyűrű műveleteit jelöljük a szokásos módon, míg az polinomgyűrű műveleteit jelöljük a és szimbólumokkal. Ekkor az összegpolinomhoz az , míg …
Legyen egy tetszőleges kommutatív, egységelemes gyűrű, egy tetszőleges polinom a hozzátartozó polinomfüggvénnyel, pedig egy tetszőleges gyűrűelem. Ekkor létezik olyan polinom, amelynek polinomfüggvényére teljesül az alábbi egyenlet: Legyen most az az elsőfokú polinom, amelyhez az polinomfüggvény …
Legyen egy tetszőleges kommutatív, egységelemes és nullosztómentes gyűrű, legyen továbbá egy tetszőleges nemnulla polinom, amelynek pontosan az , , …, gyűrűelemek a gyökei. Ha a szimbólummal jelöljük az polinomgyűrű szorzását, akkor az polinom felírható az …
Legyen tetszőleges kommutatív gyűrű, és jelölje az feletti polinomok halmazát, továbbá legyenek és tetszőleges nemnulla polinomok. Ekkor a ban bevezetett polinomok közötti műveletekre teljesülnek az alábbiak: Ha , akkor . Ha , akkor . Ha …
Legyen tetszőleges pozitív egész szám, valamint a szerinti Euler-függvény. Amennyiben , , …, az egész szám összes pozitív osztója, akkor teljesül az alábbi összefüggés:
Legyen tetszőleges csoport, pedig ennek egy tetszőleges eleme, amelynek rendje , azaz: Ekkor tetszőleges -adik hatványának (lásd a t) rendjét az alábbi képlet adja meg, ahol azt az egész számot jelöli, amelyet a kitüntetett közös …
Legyen valamilyen pozitív prímszám, a modulo maradékosztálygyűrű multiplikatív csoportja, pedig tetszőleges pozitív egész szám. Ekkor esetén esetén a csoportban pontosan darab rendű elem létezik, ha pedig , akkor egyáltalán nincs rendű elem. Következésképp esetén darab …
Legyen egy tetszőleges -nél nagyobb páratlan szám, amelynek legalább két egymástól különböző prímtényezője is van, azaz nem prímhatvány. Képezzük azt az kitevőt és páratlan számot, amelyekre teljesül az alábbi: A szövegével megegyező módon legyen a …
