A Fermat-tanú 23.3. Definíciójához hasonlóan itt is teljes maradékosztályokra célszerű vonatkoztatni ezt a fogalmat. Ha ugyanis egy b egész szám a-val azonos modulo n maradékosztályban van, akkor teljesül az a\equiv b\pmod n kongruencia, és így a 20.2. Tétel 8. pontja alapján teljesülnek az alábbi kongruenciák is:

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

Mármost ha a baloldal nem kongruens a definícióban szereplő számokkal, akkor a jobboldal sem. Így tehát az [a]_n maradékosztálynak vagy minden eleme teljesíti a Miller-Rabin-tanúkkal szemben támasztott kritériumokat, vagy egyik sem.

Szintén a Fermat-tanú 23.3. Definíciójához hasonlóan itt sem kell kikötni, hogy [a]_n egy redukált maradékosztály, hiszen ha van egységtől különböző közös osztója a-nak és n-nek, akkor n nyilván összetett. Nem mellesleg itt is megjegyezzük, hogy a Miller-Rabin-kongruenciák amúgysem teljesülhetnének, amennyiben [a]_n nem egy redukált maradékosztály, azaz (a,n) nem egység. Ennek indoklása szinte szóról szóra megegyezik a 23.3. Definíció utáni megjegyzésben leírtakkal.

Ez tehát azt jelenti, hogy NEM Miller-Rabin-tanú csak redukált maradékosztály lehet. Ezen túlmenően a 23.8. Tétel miatt ha egy [a]_n redukált maradékosztály NEM Miller-Rabin tanú – azaz teljesül a definícióban szereplő kongruenciák közül legalább az egyik –, akkor Fermat-tanú SEM lehet. Ha ugyanis teljesül legalább az egyik kongruencia, akkor a 20.1. Tétel 3. pontja alapján n osztója az alábbi kifejezések közül legalább az egyiknek:

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

Ám e kifejezések szorzata a 23.8. Tétel alapján épp a^{n-1}-1, aminek n a 16.2. Tétel 7. pontja miatt szintén osztója. Azaz teljesül az a^{n-1}\equiv 1\pmod n kongruencia, és így az [a]_n redukált maradékosztály valóban nem Fermat-tanú. Másként fogalmazva ez azt jelenti, hogy minden Fermat-tanú egyúttal Miller-Rabin-tanú is, vagyis az új definíció tágítani igyekszik a lehetséges tanúk körét.

Az alábbi ábrán a NEM Miller-Rabin-tanúk és a NEM Fermat-tanúk elhelyezkedése látható a modulo n maradékosztályok között.