Először a Carmichael-számok paritására vonatkozó állítást igazoljuk. Legyen tetszőleges Carmichael-szám. Az és az egész számok egymáshoz relatív prímek. Ugyanis bármilyen közös osztó a 6. pontja alapján osztója e két szám különbségének, azaz -nek, és így …
A megoldáshalmaz minden eleme kielégíti az első kongruenciát, azaz -rel azonos modulo maradékosztályban van. Következésképp a alapján minden esetén létezik olyan egész szám, hogy teljesül az alábbi egyenlet: Tehát tulajdonképpen azokat az egész számokat keressük, …
A utáni megjegyzés alapján nem Fermat-tanú csak redukált maradékosztály lehet, ezért fennáll az tartalmazási reláció. Így az részcsoport reláció igazolásához a alapján csak azt kell megmutatni, hogy nemüres és zárt a -beli csoportműveletre nézve. Az …
A tételt a kitevőre vonatkozó teljes indukcióval fogjuk igazolni. Nézzük először a esetet! A 3. pontja alapján ekkor épp megegyezik a multiplikatív csoporttal. Ennek rendje a modulo redukált maradékosztályok számával, azaz -vel egyezik meg, ami …
Ha négyzetmentes, akkor a alapján nem osztható semmilyen egész szám négyzetével, így nyilván pozitív prímszámok négyzetével sem. Megfordítva: Tegyük fel, hogy nem négyzetmentes, azaz létezik olyan egész szám, hogy . Legyen egy olyan prímszám, amely …
Előszöris megmutatjuk, hogy a ban bevezetett műveletek nem vezetnek ki az halmazból, azaz algebrai értelemben is műveletek (lásd a t). A 1. és 2. pontjai alapján ugyanis nemnulla polinomok összegének foka legfeljebb a polinomok fokainak …
A továbbiakban reprezentáljuk az és polinomokat az alábbi végtelen sorozatokkal, ahol jelöli az gyűrű nullelemét: A szerint e két polinom összegének -adik tagját az alábbi képletből kapjuk: Szintén a alapján a két polinom szorzatának -adik …
Tegyük fel, hogy az polinomfüggvény olyan, hogy tetszőleges gyűrűelemhez az alábbi kifejezés eredményét rendeli hozzá: Ennek értékét esetén tehát az alábbi kifejezés kiértékelésével számíthatjuk ki: Emeljük ki -et minden olyan tagból, amelyikből lehet: Ismételgessük ezt …
Legyen az gyűrű nulleleme, továbbá vezessük be az alábbi jelöléseket: Ennek megfelelően és az alábbi sorozatokkal reprezentálhatók: Az 1. állítás: Mivel , vagyis az index nagyobb fokánál, emiatt , tehát az összegpolinom -edik tagja . …
Tekintsük elsőként az gyöktényezőt. A alapján felírható az alábbi alakban valamilyen alkalmas polinommal: Mivel egységelemes, továbbá az gyöktényező főegyütthatója az egységelem – hiszen az ugye a alapján megegyezik a hozzátartozó polinomfüggvény elsőfokú tagjának, azaz -nek …
A 4. pontja alapján tehát azt a legkisebb pozitív kitevőt keressük, amellyel a elemet hatványozva a csoport -vel jelölt egységelemét kapjuk. Ez a hatvány a 2. pontja alapján a elem -adik hatványa lesz, azaz felírható …
Minden egyes, a tételben szereplő osztóból állítsuk elő az összes olyan számpárt, amelynek első tagja , második tagja pedig egy olyan -nél kisebb nemnegatív egész szám, amely relatív prím -hez. A alapján pontosan darab olyan …
A csoport a maradékosztálygyűrű redukált maradékosztályaiból áll, ezért a alapján ennek a csoportnak a rendje , azaz a miatt . Mivel a miatt bármely elem rendje osztója a csoport rendjének, ezért ha , akkor -ben …
Elsőként azt mutatjuk meg, hogy ha Carmichael-szám, akkor teljesíti a fenti két kritériumot. Először igazoljuk, hogy négyzetmentes, ami a alapján azt jelenti, hogy nem létezik olyan pozitív prímosztója, amelynek a négyzetével is osztható. Tegyük fel …
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 …
A alapján a illetve a csoportok ciklikusak. Ezért ha izomorf valamelyikükkel, akkor a alapján is ciklikus, hiszen a csoportizomorfizmus a alapján egy szürjektív homomorfizmus. Megfordítva: Tegyük fel, hogy ciklikus, és legyen egy generátorelem. Ekkor minden …
Azt kell megmutatni, hogy valóban generátoreleme. Legyen ezért a csoport tetszőleges eleme. Mivel az csoporthomomorfizmus szürjektív, ezért biztosan létezik olyan elem -ben, amelynek épp az szerinti képe, azaz: Mivel ciklikus, ezért ez a bizonyos kifejezhető …
Mivel a és a csoportok esetén a csoportműveletet jelöli, ezért a nak megfelelően az „egységelem” és „inverz” helyett a „nullelem” és „ellentett” kifejezéseket használjuk, továbbá a utáni megjegyzés alapján a szokásos helyett az írásmódot követjük …
