Solution
= Solution
If $N$ is prime, <Fermat's little theorem> gives $b^{2^sd}\equiv1$. If $b^d\equiv1$, the strong test already passes. Otherwise let $j\ge1$ be the first index with $b^{2^jd}\equiv1$. Its preceding value $u=b^{2^{j-1}d}$ satisfies $u^2=1$ and $u\ne1$ 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 \b[every coprime base passes the strong test when $N$ is prime].