Legyen n\gt 1 egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges [a]_n redukált maradékosztály. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesülnek az alábbiak:

n-1=2^e\cdot k

Azt kell igazolni, hogy [a]_n nem lehet Miller-Rabin-tanú, azaz az alábbi kongruenciák közül legalább az egyiknek teljesülnie kell:

\begin{aligned}a^k&\equiv +1\pmod n \\ 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}

Mivel n prím, továbbá (a,n)=1 – hiszen [a]_n egy redukált maradékosztály –, ezért a kis Fermat-tétel (22.1. Tétel) miatt teljesül rá az alábbi kongruencia:

a^{\overbrace{2^e\cdot k}^{=n-1}}\equiv 1\pmod n

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az alábbi oszthatóság:

n|a^{2^e\cdot k}-1

Az oszthatóságban szereplő jobboldali kifejezést a 23.8. Tétel alapján szorzatba fejthetjük:

n|(a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)

Mivel n prím, ezért a 16.13. Definíció utáni megjegyzés szerint legalább az egyik jobboldali tényezőnek osztója kell legyen. Azaz az alábbi oszthatóságok közül legalább az egyiknek teljesülnie kell:

\begin{aligned}n&|a^k-1 \\ n&|a^k+1 \\ n&|a^{2k}+1 \\ n&|a^{4k}+1 \\ &\vdots \\ n&|a^{2^{e-1}k}+1 \end{aligned}

A 20.1. Tétel 3. pontja alapján ez tehát azt jelenti, hogy legalább az egyik kongruenciának teljesülnie kell az alábbiak közül:

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

Ez viszont a 23.9. Definíció szerint épp azt jelenti, hogy az [a]_n maradékosztály nem Miller-Rabin-tanú.