Mivel a tételben szereplő G_n halmaz elemei a NEM Miller-Rabin-tanúk, ezért a 23.9. Definíció utáni megjegyzés alapján az biztos, hogy itt csak redukált maradékosztályok lehetnek, azaz G_n\sube (\Z/n\Z)^{\times}.

Ha c=1, akkor n=p^c=p egy prímszám, amelynek a 23.10. Tétel értelmében egyáltalán nincsenek Miller-Rabin-tanúi, azaz ebben az esetben G_n=(\Z/n\Z)^{\times}. Ezzel c=1-re igazoltuk a 2. és 3. állításokat. Mivel n=p most egy prímszám, ezért az 1. állítás a kis Fermat-tételből (22.1. Tétel) azonnal következik, mely szerint bármilyen n=p-hez relatív prím a egész számra teljesül az a^{p-1}\equiv 1\pmod p kongruencia. A 20.14. Tétel alapján az n=p-hez relatív prím egész számok pontosan a redukált maradékosztályokat, azaz a (\Z/n\Z)^{\times} multiplikatív csoport elemeit reprezentálják, ami ugye – mint láttuk – megegyezik a NEM Miller-Rabin-tanúk G_n halmazával.

Az általánosság megsértése nélkül feltehetjük tehát, hogy c\geq 2.

Nézzük az 1. állítást ebben az esetben! Azt kell tehát bizonyítani, hogy az n=p^c egész szám NEM Miller-Rabin-tanúinak a reprezentánselemei, és csak azok elégítik ki az alábbi kongruenciát:

a^{p-1}\equiv 1\pmod{\underbrace{n}_{=p^c}}

Ha az [a]_n maradékosztály nem Miller-Rabin-tanú, akkor egyrészt a 23.9. Definíció utáni megjegyzés alapján csak redukált maradékosztály lehet, és így a 20.14. Tétel szerint a és n=p^c relatív prímek. Ekkor viszont érvényes az Euler-Fermat tétel (20.19. Tétel), miszerint:

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

Másrészt viszont ha [a]_n nem Miller-Rabin-tanú, akkor szintén a 23.9. Definíció utáni megjegyzés szerint nem lehet Fermat-tanú sem. Ez a 23.3. Definíció alapján azt jelenti, hogy fennáll az alábbi kongruencia is:

a^{n-1}\equiv 1\pmod n

A 24.12. Tétel 2. pontja alapján tehát a (\Z/n\Z)^{\times} csoportban az [a]_n elem rendje közös osztója \varphi(n)-nek és n-1-nek. Ez viszont a 17.4. Definíció miatt azt jelenti, hogy osztója a (\varphi(n), n-1) kitüntetett közös osztónak is, azaz teljesül az alábbi oszthatóság:

o([a]_n)|(\varphi(n), n-1)

Alkalmazva az n=p^c helyettesítést a jobboldalon szereplő kitüntetett közös osztóra a 21.5. Tétel alapján, továbbá a 14.12. Definícióban szereplő 5. gyűrűaxióma szerint a következőt kapjuk:

(\underbrace{p^c-p^{c-1}}_{=\varphi(p^c)}, p^c-1)=((p-1)p^{c-1},p^c-1)=\ldots

Szintén a gyűrűaxiómák következménye, hogy a jobboldalon szereplő p^c-1 kifejezésből is kiemelhető a p-1 tényező, méghozzá az alábbi összefüggés miatt, amelyet az Olvasó maga is leellenőrizhet a zárójelek felbontásával:

p^c-1=(p-1)(p^{c-1}+p^{c-2}+\ldots+p+1)

Alkalmazhatjuk tehát a kitüntetett közös osztó kiemelési tulajdonságát (17.9. Tétel), azaz a fenti kitüntetett közös osztóból kiemelhetjük p-1-et:

\ldots=(p-1)\cdot (p^{c-1},p^{c-1}+p^{c-2}+\ldots+p+1)=\ldots

Vegyük észre, hogy az itt szereplő jobboldali p^{c-1}+p^{c-2}+\ldots+p+1 összeg minden tagja osztható p-vel, kivéve az utolsó. Ez az összeg tehát p-vel osztva 1 maradékot ad, azaz a prímtényezői biztosan mind különböznek p-től. Ezzel szemben a baloldali p^{c-1} prímtényezői között csak p szerepel. A két mennyiség emiatt egymáshoz relatív prím, azaz:

\ldots=(p-1)\cdot \underbrace{1}_{=(p^{c-1},p^{c-1}+p^{c-2}+\ldots+p+1)}

Azt kaptuk tehát, hogy ha az [a]_n maradékosztály nem Miller-Rabin-tanú, akkor az ő rendje a (\Z/n\Z)^{\times} csoportban osztója lesz a (\varphi(n),n-1)=p-1 kitüntetett közös osztónak. Ez viszont a 24.12. Tétel 2. pontja alapján épp azt jelenti, hogy valóban teljesül az alábbi kongruencia, ahogyan a tétel állítja:

a^{p-1}\equiv 1\pmod{\underbrace{n}_{=p^c}}

Most nézzük visszafelé! Tegyük fel, hogy teljesül az iménti kongruencia egy a egész számra. Most azt kell bizonyítani, hogy ekkor az [a]_n maradékosztály nem Miller-Rabin-tanú. Mivel n=p^c páratlan, ezért n-1=p^c-1 páros, és így valahányszor osztható 2-vel. Azaz létezik olyan e\geq 1 kitevő és k\geq 1 páratlan egész, hogy:

n-1=p^c-1=2^e\cdot k

Ehhez hasonlóan p-1-hez is létezik olyan f\geq 1 kitevő és l\geq 1 páratlan egész, hogy:

p-1=2^f\cdot l

A korábban már említett p^c-1=(p-1)(p^{c-1}+p^{c-2}+\ldots+p+1) azonosság alapján tudjuk, hogy teljesül az alábbi oszthatóság:

\underbrace{2^fl}_{=p-1}|\overbrace{2^ek}^{=p^c-1}

Mivel l és k páratlan, így ezek prímtényezői között biztosan nem szerepel a 2-es. Ezért a fenti oszthatóság csak úgy teljesülhet, ha fennáll az alábbi két feltétel:

\begin{aligned}f&\leq e \\ l&|k\end{aligned}

Ugye abból indultunk ki, hogy teljesül az a^{p-1}\equiv 1\pmod n kongruencia. Ez az imént bevezetett p-1=2^fl jelölést alkalmazva így írható:

a^{2^fl}\equiv 1\pmod n

Ez a hatványozás azonosságairól szóló 18.8. Tétel 2. pontja miatt így is írható:

(a^l)^{2^f}\equiv 1\pmod n

A 24.12. Tétel 2. pontja alapján tehát az [a^l]_n maradékosztály rendje osztója 2^f-nek. Ez csak úgy lehet, ha ez a rend is valamilyen 2-hatvány egy f-nél nemnagyobb, nemnegatív j kitevővel, azaz o([a^l]_n)=2^j.

Ha j=0, akkor ugye (a^l)^{2^0}=a^l és így teljesül az alábbi kongruencia:

a^l\equiv 1\pmod n

De mivel tudjuk, hogy l|k – azaz k az l-nek többszöröse –, ezért ekkor teljesül az a^k\equiv 1\pmod n kongruencia is. Ez épp a 23.9. Definícióban szereplő első kongruencia, amely szerint tehát [a]_n valóban nem lehet Miller-Rabin-tanú.

Ha j\geq 1, akkor ez az elemrend 24.11. Definíciója miatt azt jelenti, hogy 2^j a legkisebb olyan kitevő, amely esetén az alábbi kongruencia teljesül:

(a^l)^{2^j}\equiv 1\pmod n

Az ennél kisebb kitevőkre ez már nem teljesül, tehát például:

(a^l)^{2^{j-1}}\ \cancel{\equiv}\ 1\pmod n

A felső kongruencia baloldala épp az alsó kongruencia baloldalának négyzete, hiszen:

((a^l)^{2^{j-1}})^2=(a^l)^{2^{j-1}\cdot 2}=(a^l)^{2^j}

Ha most az áttekinthetőség kedvéért bevezetjük az x=(a^l)^{2^{j-1}} jelölést, akkor fenti két kongruencia tulajdonképpen az alábbi két állításnak felel meg:

\begin{aligned}x\ &\cancel{\equiv}\ 1\pmod n \\ x^2&\equiv 1\pmod n\end{aligned}

Az alsó kongruencia a 20.1. Tétel 3. pontja alapján az alábbi oszthatóságot jelenti:

n|x^2-1

Ennek az oszthatóságnak a jobboldala a 14.12. Definícióban ismertetett gyűrűaxiómák miatt szorzatba fejthető:

\underbrace{n}_{=p^c}|(x+1)\cdot (x-1)

Ez az oszthatóság tehát biztosan teljesül. Ugyanakkor az is bizonyos, hogy x+1 és x-1 közül legfeljebb az egyikük prímtényezői között szerepelhet p, hiszen közöttük mindössze 2 a különbség. Más szavakkal az egyikük biztosan relatív prím lesz n=p^c-hez, és így az euklidészi lemma (17.11. Tétel) alapján a másik viszont biztosan osztható lesz n-nel. Azaz az alábbi oszthatóságok közül pontosan az egyik teljesül:

\begin{aligned}n&|x+1 \\ n&|x-1\end{aligned}

Azonban a második oszthatóság lehetetlen, hiszen az a 20.1. Tétel 3. pontja szerint azt jelentené, hogy mégiscsak teljesülne az x\equiv 1\pmod n kongruencia, amiről már láttuk, hogy nem teljesülhet. Következésképp csak az első oszthatóság teljesülhet. Ez viszont ismét a 20.1. Tétel 3. pontja miatt épp az alábbi kongruenciát jelenti:

x\equiv -1\pmod n

Azonban emlékezzünk rá, hogy x-szel tulajdonképpen az (a^l)^{2^{j-1}}=a^{2^{j-1}l} kifejezést jelöltük, ezért ez a kongruencia ennek felel meg:

a^{2^{j-1}l} \equiv -1\pmod n

Mivel korábban már láttuk, hogy k többszöröse l-nek, azaz létezik olyan t egész szám, amely esetén lt=k. Ráadásul mivel a k és l számokról tudjuk, hogy páratlan számok, ezért a t is szükségképpen páratlan. Ha tehát a fenti kongruencia mindkét oldalát t-edik hatványra emeljük (amelyet ugye a 20.2. Tétel 8. pontja alapján tehetünk meg), akkor ezt kapjuk:

a^{2^{j-1}\overbrace{lt}^{=k}} \equiv \overbrace{(-1)^t}^{=-1}\pmod n

Itt a jobboldal valóban -1 marad, hiszen negatív szám páratlanadik hatványa ugyancsak negatív. Végeredményben tehát ezt kaptuk:

a^{2^{j-1}k} \equiv -1\pmod n

Tekintve, hogy j-1 biztosan kisebb a bevezetett e kitevőnél, ezért az alábbi kongruenciák közül biztosan teljesül az egyik:

\begin{aligned}a^k&\equiv -1 \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}

Ez viszont a 23.9. Definíció alapján azt jelenti, hogy az [a]_n maradékosztály ebben az esetben sem lehet Miller-Rabin-tanú. Ezzel a tétel 1. állítását igazoltuk, miszerint valóban pontosan azok a maradékosztályok nem Miller-Rabin-tanúk – azaz tartoznak bele a tétel szövegében szereplő G_n halmazba –, amelyekre teljesül az alábbi kongruencia:

a^{p-1}\equiv 1\pmod n

Most igazoljuk a 2. állítást, amely azt állítja, hogy G_n részcsoportja a (\Z/n\Z)^{\times} multiplikatív csoportnak. Mivel (\Z/n\Z)^{\times} rendje véges, ezért a 24.13. Következmény szerint elegendő azt ellenőrizni, hogy G_n nemüres és zárt a maradékosztályok közötti szorzásra, mint műveletre. Az első feltétel nyilván teljesül, hiszen 1^{p-1}\equiv 1\pmod n, és így az 1. állítás értelmében az [1]_n maradékosztály benne van G_n-ben.

Legyen most [a]_n és [b]_n két tetszőleges maradékosztály, amelyek a G_n halmaz elemei. Ez az imént bizonyított 1. állítás alapján azt jelenti, hogy teljesülnek az alábbi kongruenciák:

\begin{aligned}a^{p-1}&\equiv 1\pmod n \\ b^{p-1}&\equiv 1\pmod n\end{aligned}

A két kongruenciát a 20.2. Tétel 5. pontja alapján összeszorozhatjuk egymással, így ezt kapjuk:

a^{p-1}b^{p-1}\equiv 1\pmod n

A baloldalt a hatványozás azonosságairól szóló 18.8. Tétel 1. pontját felhasználva átírhatjuk:

(ab)^{p-1}\equiv 1\pmod n

Ez viszont ismét az imént bizonyított 1. állítás miatt azt jelenti, hogy az [ab]_n maradékosztály is a G_n halmaz eleme. Az [ab]_n maradékosztály azonban a 20.5. Tételben szereplő definíciónak megfelelően épp az [a]_n és [b]_n maradékosztályok szorzata. A G_n halmaz tehát valóban részcsoport (\Z/n\Z)^{\times}-ban.

Végül a 3. állítást igazoljuk. Azt már láttuk, hogy c=1 esetben G_n=(\Z/n\Z)^{\times}, így elegendő azt igazolni, hogy c\geq 2 esetén viszont valódi részcsoportról van szó. Azaz kell találni egy olyan redukált maradékosztályt, amely nincs benne a G_n halmazban. Más szavakkal kell találnunk egy olyan a egész számot, amely relatív prím n=p^c-hez, de amelyre a^{p-1}\ \cancel{\equiv}\ 1\pmod{p^c}. Hiszen ekkor egyrészt a 20.14. Tétel alapján [a]_n egy redukált maradékosztály, másrészt pedig a már bizonyított 1. állítás alapján [a]_n\notin G_n.

Nézzük meg először, hogy mi következik abból, ha egy a szám teljesíti a fenti kongruenciát. Ekkor ugye a (\Z/n\Z)^{\times} csoportban a 24.12. Tétel 2. pontja alapján az [a]_n maradékosztály rendje osztója p-1-nek, azaz teljesül az alábbi oszthatóság:

o([a]_n)|p-1

Ám p-1 prímtényezős felbontásában biztosan nem szerepel p, így nem szerepelhet p-1 egyetlen osztójának prímtényezős felbontásában sem, emiatt o([a]_n) felbontásában sem, azaz:

p\nmid o([a]_n)

Megfordítva a gondolatmenetet, ha tehát találunk egy olyan [a]_n redukált maradékosztályt, amelynek rendje osztható p-vel, akkor az kizárja azt, hogy teljesüljön az a^{p-1}\equiv 1\pmod{p^c} kongruencia, ami a már bizonyított 1. állítás alapján azt jelentené, hogy [a]_n\notin G_n.

Vegyük észre, hogy a [p+1]_n maradékosztály teljesíti ezt a feltételt. Egyrészt ugyanis p+1 nyilván relatív prím p-hez – azaz [p+1]_n egy redukált maradékosztály –, másrészt pedig teljesül az alábbi kongruencia:

p+1\equiv 1\pmod p

Ekkor azonban alkalmazható a 24.17. Következmény, amely szerint teljesül az alábbi kongruencia is:

(p+1)^{p^{c-1}}\equiv 1\pmod{\underbrace{p^c}_{=n}}

Ez viszont a 24.12. Tétel 2. pontja alapján azt jelenti, hogy a [p+1]_n maradékosztály rendje osztója p^{c-1}-nek. Továbbá ugyanezen tétel 5. pontja miatt ez a rend biztosan nem 1, hiszen [p+1]_n\neq [1]_n. Minthogy p^{c-1} prímtényezős felbontásában csak p szerepel, ezért ennek bármilyen 1-től különböző osztója szükségképpen osztható p-vel.

A [p+1]_n redukált maradékosztály tehát valóban nincs benne G_n-ben, és így G_n tényleg valódi részcsoportja (\Z/n\Z)^{\times}-nek, ahogyan a tétel állítja.