We want to show that any divisor
-
$M(n) \equiv 2^n - 1 \equiv 0 \pmod d$ (given) -
$2^n \equiv 1 \pmod d$ (restatement of step (1)) -
$\left( 2^{(n/2)}\right)^{d-1} \equiv 2^{\left(\frac {n(d-1)} 2 \right)} \equiv \left(2^n\right)^{\left( \frac {d-1} 2 \right)} \equiv 1 \pmod d$ (step (2),$d-1$ is even) -
$(2^{n/2})^{d-1} \equiv 1 \pmod d \rightarrow$ $d$ is pseudo-prime in base$2^{n/2}$ (definition)
Thus,