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

For odd $N>1$ coprime to $b$, the Fermat pseudoprime test is $b^{N-1}\equiv 1(\mathrm{mod}N)$. The Euler pseudoprime test meant here is the Euler–Jacobi test,where the right side is the Jacobi symbol. Write $N-1=2^{s}d$, with $d$ odd. The strong pseudoprime test passes when $b^d\equiv 1$, or when $b^{2^{j}d}\equiv -1$ for some $0\le j<s$. Terminology often reserves “pseudoprime” for composite numbers; the question uses it for passing the respective test, including primes.

For the final example, $341=11\cdot 31$ is composite and $2^{10}=1024\equiv 1(\mathrm{mod}341)$, so $2^{340}\equiv 1$. It passes the Fermat primality test. However $2^{170}\equiv 1$, whereas the supplementary law for the Jacobi symbol gives $(2/341)=-1$ since $341\equiv 5(\mathrm{mod}8)$. Thus 341 is Fermat but not Euler–Jacobi pseudoprime to base two. A weaker convention defining an Euler test merely by $b^{(N-1)/2}=\pm 1$ would not give the claimed distinction, which is why the Jacobi convention matters.