Legyenek adottak valamilyen tetszőleges és egész számok. Ekkor bármilyen egész szám esetén teljesül az alábbi összefüggés:

Semmilyen -nél nagyobb páratlan prímszámnak nincs Miller-Rabin-tanúja. Másként fogalmazva ha egy -nél nagyobb páratlan számnak van Miller-Rabin-tanúja, akkor összetett.

Legyen tetszőleges pozitív egész szám. Tegyük fel, hogy adva van egy valamilyen egész szám által reprezentált redukált maradékosztály, amely Fermat-tanú. Legyen adott továbbá egy valamilyen egész szám által reprezentált redukált maradékosztály, amely nem Fermat-tanú. Ekkor …

Legyen egy tetszőleges pozitív egész szám. Amennyiben -nek létezik Fermat-tanúja a redukált maradékosztályok között, akkor a modulo redukált maradékosztályoknak legalább a fele Fermat-tanú.

Ha bármely két egymástól különböző és maradékosztályt megszorzunk egy tetszőleges redukált maradékosztállyal, akkor az így kapott maradékosztályok is különböznek egymástól. Azaz ha , akkor .

Legyen egy tetszőleges nemnulla egész szám, amely nem egység, valamint jelöljük -rel a lehető legnagyobb olyan egész számot, amelyre teljesül. Ebben az esetben az egész szám akkor és csak akkor prím (azaz felbonthatatlan), ha nem …

Legyen egy tetszőleges nemnulla egész szám, amely nem egység. Ebben az esetben akkor és csak akkor prím (azaz felbonthatatlan), ha nem létezik -nél nagyobb, de -nél kisebb osztója. Ezzel ekvivalens megfogalmazás: Az akkor és csak …

Legyen tetszőleges, pedig valamilyen pozitív egész szám. Ekkor tetszőleges prímszám esetén az egész akkor és csak akkor relatív prím a hatványhoz, ha nem osztható -vel, azaz NEM teljesül a oszthatóság.