1. eset: n valamilyen prímhatvány

Ekkor tehát n=p^c, ahol p valamilyen páratlan prímszám, továbbá c\geq 2, máskülönben n=p nem lenne összetett. A modulo p^c redukált maradékosztályok a (\Z/p^c\Z)^{\times} multiplikatív csoport elemei, melynek rendjét a 20.7. Definíció alapján az Euler-féle \varphi-függvény adja meg. Ennek értéke a 21.5. Tétel szerint az alábbi:

|(\Z/p^c\Z)^{\times}|=\varphi(p^c)=p^c-p^{c-1}=p^{c-1}\cdot (p-1)

Másrészt a nem Miller-Rabin-tanúk G_{p^c}-vel jelölt csoportjának rendje a 26.20. Tétel értelmében:

|G_{p^c}|=p-1

Azt kell megmutatni, hogy (\Z/p^c\Z)^{\times} legalább négyszer annyi elemet tartalmaz, mint G_{p^c}, azaz:

\underbrace{p^{c-1}\cdot (p-1)}_{=|(\Z/p^c\Z)^{\times}|}\geq 4\cdot \underbrace{(p-1)}_{=|G_{p^c}|}

Az n=p^c-ről ugye tudjuk, hogy ő egy 9-nél nagyobb prímhatvány, azaz p legalább 5 és c legalább 2. Az alábbi tehát biztosan teljesül:

p^{c-1}\geq 4

Mindkét oldalt megszorozva p-1-gyel – ami a fentiek alapján biztosan pozitív – a 15.11. Definíció szerinti 2. rendezési axióma alapján megkapjuk a tétel állítását a prímhatványok esetére:

p^{c-1}\cdot (p-1)\geq 4\cdot (p-1)

2. eset: n nem prímhatvány, és nem Carmichael-szám

Ekkor a nem Miller-Rabin-tanúk ugyan nem alkotnak részcsoportot (\Z/n\Z)^{\times}-ben, azonban a 26.21. Tétel 1. pontja alapján a nem Fermat-tanúk F_n-nel jelölt csoportja valódi részcsoport (\Z/n\Z)^{\times}-ben, továbbá az ugyanezen tételben H_n-nel jelölt csoport valódi részcsoport F_n-ben, amely viszont a 24.19. Tétel 1. pontja alapján minden nem Miller-Rabin-tanút tartalmaz. Azaz a következő a helyzet:

A Lagrange-tétel (24.8. Tétel) miatt azonban a redukált maradékosztályoknak legfeljebb a fele tartozhat F_n-be, amelyeknek legfeljebb a fele – köztük az összes nem Miller-Rabin-tanú – tartozhat H_n-be. Következésképp a redukált maradékosztályoknak ebben az esetben is legalább a háromnegyede Miller-Rabin-tanú.

3. eset: n nem prímhatvány, és Carmichael-szám

Ekkor a 26.21. Tétel 1. pontja helyett a 26.22. Tételt kell alkalmaznunk. Eszerint a nem Miller-Rabin-tanúkat tartalmazó H_n részcsoport indexe a tételben szereplő D_n részcsoportban 2^{r-1}, ahol r az n egész szám egymástól különböző prímtényezőinek számát jelöli. Továbbá, mivel D_n részcsoport (\Z/n\Z)^{\times}-ben, ezért a H_n részcsoport indexe (\Z/n\Z)^{\times}-ben legalább 2^{r-1}. Ez a Lagrange-tétel (24.8. Tétel) alapján azt jelenti, hogy (\Z/n\Z)^{\times} rendje legalább 2^{r-1}-szerese H_n rendjének, amely ugye a 24.19. Tétel 1. pontja alapján minden nem Miller-Rabin-tanút tartalmaz.

Mivel azonban n Carmichael-szám, ezért a Korselt-kritérium 26.18. Következménye alapján r\geq 3, és így ez a bizonyos 2^{r-1} szorzó tényező legalább 4. Most is azt kaptuk tehát, hogy a redukált maradékosztályoknak legalább a háromnegyede Miller-Rabin-tanú.