Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 4 / 11H / a / Solution

If $N$ is prime, Fermat's little theorem gives $b^{2^{s}d}\equiv 1$. If $b^d\equiv 1$, the strong test already passes. Otherwise let $j\ge 1$ be the first index with $b^{2^{j}d}\equiv 1$. Its preceding value $u=b^{2^{j-1}d}$ satisfies $u^2=1$ and $u\ne 1$ in the field ${\mathbb{F}}_N$. Since $(u-1)(u+1)=0$ in a field, $u=-1$. The index $j-1$ lies between zero and $s-1$, so every coprime base passes the strong test when $N$ is prime.