Előszöris nyilván létezik legalább egy a tételben említett feltételnek megfelelő j kitevő, hiszen például j=0 és x=-1 választással teljesül az alábbi kongruencia:

(\underbrace{-1}_{=x})^{2^{\overbrace{0}^{=j}}}\equiv -1\pmod n

Tehát az ilyen kitevők között létezik legnagyobb is, amelyet ugye j_{\text{max}}-szal jelöltünk.

Nézzük először az 1. állítást, és mutassuk meg, hogy a H_n-ben lévő összes [a]_n maradékosztály redukált. A H_n halmaz definíciója miatt:

a^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Akár 1, akár -1 szerepel a jobboldalon, a kongruenciát négyzetre emelve a következőt kapjuk:

a^{2^{j_{\text{max}}+1}k} \equiv 1\pmod n

Találtunk tehát egy olyan pozitív kitevőt – nevezetesen 2^{j_{\text{max}}+1}k-t – amelyre emelve a-t az eredmény kongruens lesz 1-gyel modulo n. Ebből viszont a 20.20. Tétel alapján következik, hogy a relatív prím n-hez, azaz a 20.14. Tétel értelmében [a]_n redukált maradékosztály. Ezzel igazoltuk a tétel 1. állítását.

A 2. állítás igazolásához a 24.13. Következmény értelmében azt kell megmutatni, hogy H_n nemüres és zárt a maradékosztályok közötti szorzásra, azaz a (\Z/n\Z)^{\times} csoport műveletére nézve. Mivel 1^{2^{j_{\text{max}}}k}\equiv 1\pmod n, ezért a tétel szövege alapján H_n nemüres, hiszen tartalmazza legalább az [1]_n maradékosztályt. Legyen most [a]_n és [b]_n a H_n halmaz két tetszőleges eleme. A H_n halmaz definíciója miatt ekkor teljesülnek az alábbi kongruenciák:

\begin{aligned}a^{2^{j_{\text{max}}}k} &\equiv \pm 1\pmod n \\ b^{2^{j_{\text{max}}}k} &\equiv \pm 1\pmod n\end{aligned}

A 20.2. Tétel 5. pontja szerint ez a két kongruencia összeszorozható. Ekkor a 18.8. Tétel 1. pontjának alkalmazása után ezt kapjuk:

(ab)^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Azt kaptuk tehát, hogy az [ab]_n maradékosztály is a H_n halmaz eleme. Minthogy az [ab]_n maradékosztály a 20.5. Tételben bevezetett műveletek definíciója alapján épp az [a]_n és [b]_n maradékosztályok szorzata, ezért H_n zárt a (\Z/n\Z)^{\times} multiplikatív csoport műveletére nézve, azaz a 24.13. Következmény értelmében annak valóban részcsoportja. Ezzel igazoltuk a tétel 2. állítását.

A 3. állítás igazolásához tekintsünk egy tetszőleges [a]_n maradékosztályt, amely nem Miller-Rabin-tanú. Ekkor a Miller-Rabin-tanúk 23.9. Definíciója alapján vagy teljesül az a^k\equiv 1\pmod n kongruencia, vagy pedig létezik olyan j kitevő a \{0; 1;2; \ldots ; e-1\} számok között, amelyre teljesül az alábbi kongruencia:

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

Amennyiben az a^k\equiv 1\pmod n kongruencia teljesül, akkor mindkét oldalt j_{\text{max}}-szor négyzetre emelve, továbbá alkalmazva a 18.8. Tétel 2. pontját, az alábbit kapjuk:

a^{2^{j_{\text{max}}}k}\equiv 1\pmod n

Következésképp az [a]_n maradékosztály benne van a H_n halmazban.

Most nézzük meg, mi a helyzet akkor, ha nem teljesül az a^k\equiv 1\pmod n kongruencia. Ekkor ugye – mint már említettük – létezik olyan j kitevő a \{0; 1;2; \ldots ; e-1\} számok között, amelyre teljesül az alábbi kongruencia:

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

Alkalmazva a hatványozás azonosságairól szóló 18.8. Tétel 2. pontját ez így írható fel:

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

Az a^k tehát egy olyan egész szám, amelyet a 2-nek a j-edik hatványára, mint kitevőre emelve egy olyan egész számot kapunk, amely -1-gyel kongruens modulo n. A tétel szövegében bevezetett j_{\text{max}} definíciója alapján ekkor j\leq j_{\text{max}}.

Amennyiben egyenlőség áll fenn, azaz j=j_{\text{max}}, akkor teljesül az alábbi kongruencia:

a^{2^{\overbrace{j}^{=j_{\text{max}}}}\cdot k}\equiv -1\pmod n

Ez a H_n halmaz definíciója alapján azt jelenti, hogy [a]_n\in H_n.

Amennyiben nem áll fenn egyenlőség, akkor j\lt j_{\text{max}}. Az alábbi kongruenciáról ugye már tudjuk, hogy teljesül:

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

Mindkét oldalt sorozatosan négyzetre emelve az alábbi kongruenciákat kapjuk:

\begin{aligned}(a^k)^{2^{j+1}}&\equiv 1\pmod n \\ (a^k)^{2^{j+2}}&\equiv 1\pmod n \\ (a^k)^{2^{j+3}}&\equiv 1\pmod n \\ &\vdots \end{aligned}

Mivel j\lt j_{\text{max}}, ezért a sorozatos négyzetre emelések hatására előbb-utóbb a alábbi kongruenciát fogjuk kapni:

(a^k)^{2^{j_{\text{max}}}}\equiv 1\pmod n

Alkalmazva a hatványozás azonosságairól szóló 18.8. Tétel 2. pontját ez így írható fel:

a^{2^{j_{\text{max}}}k}\equiv 1\pmod n

Ez a H_n halmaz definíciója alapján ugyancsak azt jelenti, hogy [a]_n\in H_n. Igazoltuk tehát a tétel 3. állítását, miszerint minden nem Miller-Rabin-tanú a H_n részcsoportban van.

Végül a 4. állításhoz azt kell igazolni, hogy H_n valódi részcsoport (\Z/n\Z)^{\times}-ben, azaz találni kell egy olyan redukált maradékosztályt, amely nincs benne H_n-ben. Az n-ről a tétel szövegében kikötöttük, hogy ő egy olyan 1-nél nagyobb páratlan összetett szám, amelynek legalább két egymástól különböző prímtényezője van. Legyen n egyik prímtényezője p. Ekkor létezik olyan c\geq 1 kitevő és m\gt 1 páratlan egész szám, hogy egyrészt m tovább már nem osztható p-vel, másrészt pedig n felírható az alábbi alakban:

n=p^cm

A 24.15. Definíció alapján úgy is mondhatjuk, hogy az n egész szám p-adikus rendje c\geq 1.

Ekkor p^c-nek és m-nek nincs közös prímtényezője, mert ha lenne, akkor az csak p valamilyen nulladiknál nagyobb hatványa lehetne, és így az n egész szám p-adikus rendje biztosan nagyobb lenne c-nél. Így tehát p^c és m relatív prímek. Ebben az esetben érvényes a kínai maradéktétel (22.2. Tétel), amelynek következményeként a 22.8. Tétel alapján fennáll az alábbi gyűrűizomorfizmus:

\Z/n\Z \simeq \Z/p^c\Z \times \Z/m\Z

A tétel szövegéből tudjuk, hogy a j_{\text{max}} kitevőhöz létezik olyan egész szám, amelyet x helyére behelyettesítve teljesül az alábbi kongruencia:

x^{2^{j_{\text{max}}}}\equiv -1\pmod n

Jelöljük az egyik ilyen egész számot s-sel, és tekintsük az [s]_n maradékosztályt a \Z/n\Z gyűrűben. Neki a 22.8. Tételben szereplő g gyűrűizomorfizmus az alábbi maradékosztálypárt felelteti meg a \Z/p^c\Z \times \Z/m\Z gyűrűben:

[s]_n \xmapsto{g} ([s]_{p^c};[s]_m)

Ha a baloldali [s]_n maradékosztályt a 2^{j_{\text{max}}}k-adik hatványra emeljük a \Z/n\Z gyűrűben, akkor a g gyűrűizomorfizmus a művelettartó tulajdonság miatt ehhez épp a jobboldali maradékosztálypárnak a \Z/p^c\Z \times \Z/m\Z gyűrűben vett 2^{j_{\text{max}}}k-adik hatványát fogja hozzárendelni. Azaz:

[s]_n^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c};[s]_m)^{2^{j_{\text{max}}}k}

A jobboldalon szereplő szorzatgyűrűbeli szorzást – és így a hatványozást – a 22.7. Tétel alapján komponensenként kell elvégezni, azaz:

[s]_n^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c}^{2^{j_{\text{max}}}k};[s]_m^{2^{j_{\text{max}}}k})

A maradékosztályok közötti szorzást – és így a hatványozást – viszont a 20.5. Tétel szerint a reprezentánselemeken kell elvégezni, azaz:

[s^{2^{j_{\text{max}}}k}]_n \xmapsto{g} ([s^{2^{j_{\text{max}}}k}]_{p^c};[s^{2^{j_{\text{max}}}k}]_m)

A baloldalon szereplő modulo n maradékosztály reprezentánseleme tehát s^{2^{j_{\text{max}}}k}, amely a hatványozás azonosságairól szóló 18.8. Tétel 2. pontja alapján (s^{2^{j_{\text{max}}}})^k-val egyezik meg. Az s definíciójából tudjuk azonban, hogy:

s^{2^{j_{\text{max}}}}\equiv -1\pmod n

Mindkét oldalt k-adik hatványra emelve a kongruencia jobboldalán továbbra is -1 marad, hiszen k a tétel szövege alapján páratlan:

s^{2^{j_{\text{max}}}k}\equiv \underbrace{-1}_{=(-1)^k}\pmod n

Vagyis a fenti g szerinti hozzárendelés baloldalán tulajdonképpen a [-1]_n maradékosztály szerepel. Ám ekkor a g gyűrűizomorfizmus 22.8. Tételben szereplő definíciója alapján a jobboldalon pedig a ([-1]_{p^c};[-1]_m) maradékosztálypár kell szerepeljen:

\underbrace{[s^{2^{j_{\text{max}}}k}]_n}_{=[-1]_n} \xmapsto{g} (\underbrace{[s^{2^{j_{\text{max}}}k}]_{p^c}}_{=[-1]_{p^c}};\underbrace{[s^{2^{j_{\text{max}}}k}]_m}_{=[-1]_m})

Vagyis azt kaptuk, hogy az s^{2^{j_{\text{max}}}k} hatvány -1-gyel kongruens modulo p^c is, azaz:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

Ezt a kongruenciát hamarosan felhasználjuk, amikoris a g gyűrűizomorfizmus segítségével megmutatjuk, hogy létezik olyan X\in \Z/n\Z redukált maradékosztály, amely nincs benne H_n-ben. A H_n definíciója alapján ez a keresett X maradékosztály pontosan akkor nincs benne H_n-ben, ha az ő \Z/n\Z gyűrűben vett 2^{j_{\text{max}}}k-adik hatványa különbözik mind az [1]_n, mind pedig a [-1]_n maradékosztálytól.

Legyen ez a keresett X az a maradékosztály, amely esetén a g gyűrűizomorfizmus épp az alábbi hozzárendelést valósítja meg:

X \xmapsto{g} ([s]_{p^c};[1]_m)

Ilyen X ugye létezik, hiszen g kölcsönösen egyértelmű leképezés, azaz minden \Z/p^c\Z \times \Z/m\Z-beli maradékosztálypárt hozzárendeli valamelyik \Z/n\Z-beli maradékosztályhoz – jelen esetben az ([s]_{p^c};[1]_m) párt X-hez. A g művelettartó tulajdonsága alapján ekkor teljesül az alábbi hozzárendelés is:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c};[1]_m)^{2^{j_{\text{max}}}k}

A jobboldalon szereplő szorzatgyűrűbeli szorzást – és így a hatványozást – a 22.7. Tétel alapján komponensenként kell elvégezni, azaz:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s]_{p^c}^{2^{j_{\text{max}}}k};[1]_m^{2^{j_{\text{max}}}k})

A maradékosztályok közötti szorzást – és így a hatványozást – viszont a 20.5. Tétel szerint a reprezentánselemeken kell elvégezni, azaz:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([s^{2^{j_{\text{max}}}k}]_{p^c};[\underbrace{1^{2^{j_{\text{max}}}k}}_{=1}]_m)

Azt azonban már tudjuk, hogy teljesül az alábbi kongruencia:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

Így tehát a fenti g szerinti hozzárendelés valójában az alábbi:

X^{2^{j_{\text{max}}}k} \xmapsto{g} ([-1]_{p^c};[1]_m)

Így viszont a baloldalon szereplő X^{2^{j_{\text{max}}}k} hatvány biztosan nem lehet az [1]_n maradékosztály. Ebben az esetben ugyanis a g gyűrűizomorfizmus a 22.8. Tétel alapján az alábbi hozzárendelést valósítaná meg:

\underbrace{[1]_n}_{=X^{2^{j_{\text{max}}}k}} \xmapsto{g} \underbrace{([1]_{p^c};[1]_m)}_{=([-1]_{p^c};[1]_m)}

Ez csak akkor volna lehetséges, ha [1]_{p^c}=[-1]_{p^c} teljesülne, azaz fennállna az alábbi kongruencia:

1\equiv -1\pmod{p^c}

Ez viszont azt jelentené, hogy teljesül az alábbi oszthatóság:

p^c|\underbrace{1-(-1)}_{=2}

Ez viszont lehetetlen, hiszen p az n prímtényezője, amely páratlan, ezért p is, és így p^c is páratlan, azaz legalább 3. Márpedig a 17.2. Lemma alapján egy pozitív egész szám bármely osztója legfeljebb akkora lehet, mint maga a szám.

Hasonló gondolatmenet alapján az X^{2^{j_{\text{max}}}k} hatvány biztosan nem lehet a [-1]_n maradékosztály sem, hiszen ekkor a g gyűrűizomorfizmus a 22.8. Tétel alapján az alábbi hozzárendelést valósítaná meg:

\underbrace{[-1]_n}_{=X^{2^{j_{\text{max}}}k}} \xmapsto{g} \underbrace{([-1]_{p^c};[-1]_m)}_{=([-1]_{p^c};[1]_m)}

Ez csak akkor volna lehetséges, ha [-1]_m=[1]_m teljesülne, azaz fennállna az alábbi kongruencia:

1\equiv -1\pmod m

Ez viszont azt jelentené, hogy teljesül az alábbi oszthatóság:

m|\underbrace{1-(-1)}_{=2}

Ez viszont ugyancsak lehetetlen, hiszen m-ről azt mondtuk, hogy 1-nél nagyobb páratlan egész, azaz legalább 3.

Azt kaptuk tehát, hogy az X maradékosztály 2^{j_{\text{max}}}k-adik hatványa különbözik az [1]_n és [-1]_n maradékosztályoktól, és így valóban nem lehet H_n-ben.

Annyit kell még igazolni, hogy X redukált maradékosztály, és ennek ellenére nincs H_n-ben – azt ugyanis már az 1. állításban igazoltuk, hogy nem redukált maradékosztályok amúgysem lehetnek benne H_n-ben. Az X konstrukciója alapján a g gyűrűizomorfizmus ugye az alábbi hozzárendelést valósítja meg:

X \xmapsto{g} ([s]_{p^c};[1]_m)

Most tegyük fel, hogy az a egész szám az X maradékosztály egy reprezentánseleme, azaz legyen X=[a]_n. A 22.8. Tétel alapján azonban teljesül az alábbi hozzárendelés is:

\underbrace{[a]_n}_{=X} \xmapsto{g} ([a]_{p^c};[a]_m)

Mivel a g által megvalósított hozzárendelés kölcsönösen egyértelmű, ezért a fenti két hozzárendelés egyszerre csak akkor teljesülhet, ha a jobboldalakon szereplő két maradékosztálypár egy és ugyanaz, azaz fennállnak a maradékosztályok közötti alábbi egyenlőségek:

\begin{aligned}[a]_{p^c}&=[s]_{p^c} \\ [a]_m&=[1]_m\end{aligned}

A második egyenlőségből a 20.14. Tétel alapján következik, hogy a relatív prím m-hez. Az [a]_m=[1]_m maradékosztály ugyanis nyilván invertálható a \Z/m\Z gyűrűben, hiszen ő ennek a gyűrűnek az egységeleme, amelynek inverze önmaga.

Az első egyenlőségből szintén a 20.14. Tétel alapján következik, hogy a pontosan akkor relatív prím p^c-hez, ha s is az, hiszen ők ugyanannak a modulo p^c maradékosztálynak a reprezentánselemei. Az s-ről azonban korábban már megmutattuk, hogy teljesül rá az alábbi kongruencia:

s^{2^{j_{\text{max}}}k}\equiv -1\pmod{p^c}

A 20.2. Tétel 8. pontja alapján mindkét oldalt négyzetre emelhetjük:

s^{2^{j_{\text{max}}+1}k}\equiv 1\pmod{p^c}

Találtunk tehát egy olyan pozitív kitevőt – nevezetesen 2^{j_{\text{max}}+1}k-t – amelyre emelve s-t az eredmény kongruens lesz 1-gyel modulo p^c. Ebből viszont a 20.20. Tétel alapján következik, hogy s relatív prím p^c-hez, és így a is.

Egyrészt azt kaptuk tehát, hogy a relatív prím m-hez, vagyis nincs vele közös prímtényezője. Másrészt a relatív prím p^c-hez is, tehát vele sincs közös prímtényezője. Ekkor viszont a p^cm=n szorzattal sincs közös prímtényezője, tehát n-hez is relatív prím. Vagyis a 20.14. Tétel szerint az X=[a]_n valóban egy redukált maradékosztály a \Z/n\Z gyűrűben.