Bizonyítás
Legyen [a]_n egy tetszőleges Miller-Rabin-nemtanú, j_{\text{max}} pedig a 24.16. Tételben bevezetett kritikus négyzetreemelési szint. Ekkor a 23.9. Definíció szerint 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ámhalmazban, amelyre teljesül az alábbi kongruencia:
Ha az a^k\equiv 1\pmod n kongruencia teljesül, akkor ezt a 20.2. Tétel 6. pontja alapján 2^{j_{\text{max}}}-edik hatványra emelve, majd a baloldalt a 24.11. Tétel 2. pontja alapján átírva az alábbit kapjuk:
Ez a 24.16. Tétel szerint azt jelenti, hogy [a]_n\in H_n.
Ha a második eset áll fenn, akkor a fenti kongruencia baloldalát a 24.11. Tétel 2. pontja alapján átírva ezt kapjuk:
Az x=a^k egész számra tehát teljesül az x^{2^j}\equiv -1\pmod n kongruencia, azaz j egyike azoknak a kitevőknek, amelyek közül a 24.16. Tételben definiált j_{\text{max}} a legnagyobb. Így szükségképpen j\leq j_{\text{max}}.
Amennyiben j=j_{\text{max}}, akkor a kiindulási kongruencia épp az alábbi alakú:
Ez a 24.16. Tétel szerint ismét azt jelenti, hogy [a]_n\in H_n.
Amennyiben j\lt j_{\text{max}}, akkor emeljük négyzetre az (a^k)^{2^j}\equiv -1\pmod n kiindulási kongruenciát a 20.2. Tétel 6. pontja alapján. Mivel a 24.11. Tétel 2. pontja szerint ((a^k)^{2^j})^2=(a^k)^{2^{j+1}}, a jobboldalon pedig (-1)^2=1 áll, ezért:
Minden további négyzetreemelés 1-gyel növeli a 2 kitevőjét, a jobboldalon viszont 1^2=1 miatt továbbra is 1 marad. Mivel j+1\leq j_{\text{max}}, ezért a négyzetreemeléseket ismételve előbb-utóbb eljutunk az alábbi kongruenciák közül az utolsóig:
Az utolsó kongruencia baloldalát a 24.11. Tétel 2. pontja alapján átírva:
Ez a 24.16. Tétel szerint ugyancsak azt jelenti, hogy [a]_n\in H_n. Tehát valóban minden Miller-Rabin-nemtanú a H_n halmazban van, azaz G_n\sube H_n.
∎