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