Legyen n\gt 1 egy tetszőleges páratlan egész szám. Ha n összetett, akkor a modulo n redukált maradékosztályoknak legalább a fele Miller-Rabin-tanú.