Simplified justification of the probabilistic Miller–Rabin test for primality

Let $m$ be a positive integer and $\mathbb Z_m^*$ be the set of all positive integeres which are no greater than $m$ and relatively prime to $m$. A number $s\in\mathbb Z_m^*$ is called a witness of primality of $m$ if the sequence
$$ s^{(m-1)2^{-i}} \pmod m,\quad i = 0,1,\ldots, r,\quad m-1 = 2^{r}t, $$
where $t$ is odd, consists only of ones, or begins with ones and continues by minus one and, may be, then by other integers.
We give a simple proof of the following known assertion that is a ground of the Miller–Rabin primality test: The cardinality of the set of witnesses of primality of a composite $m$ is no greater than $\varphi(m)/4$, where $\varphi(m)$ is Euler's totient function.
This work was supported by the Russian Foundation for Basic Research, grant 96–01–068.