Exercise 2.4.8 (Strong pseudoprime algorithm)

Proof. If the strong pseudoprime test does not terminate prematurely, it does not terminate at the step $j-1$, therefore $a^{2^{j-1}d}=a^{(m-1)∕2}\not\equiv \pm 1(\mathit{mod}m)$.

If $a^{m-1}\not\equiv 1(\mathit{mod}m)$, then $m$ is composite, since it does not verify the conclusion of Fermat theorem.

If $a^{m-1}\equiv 1(\mathit{mod}m)$, then $m$ is also composite, since ${\left[a^{(m-1)∕2}\right]}^2\equiv 1(\mathit{mod}m)$, but $a^{(m-1)∕2}\not\equiv \pm 1(\mathit{mod}m)$.

In both cases $m$ is composite, thus it is useless to compute $a^{m-1}$ modulo $m$.

This gives step 5 of the algorithm:

5. If the procedure has not already terminated, then $m$ is composite. □