Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 4 / 11H (Number Theory)

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.

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.

For the plain pseudoprime assertion use the Fermat primality test. In the finite group of units modulo an integer, letIt is the kernel of a group homomorphism, because the unit group is an abelian group. The given witness makes $L$ a proper subgroup. By Lagrange's theorem for finite groups, $|L|\le \phi (N)/2$. Thus at least half of all units fail the test. Removing base one removes a passing base, so among the permitted $1<b<N$ there remain $\phi (N)-|L|$ failures out of $\phi (N)-1$ bases, still at least half.

The same argument works for the Euler–Jacobi test: its passing bases form the kernel of $b\mapsto b^{(N-1)/2}(b/N{)}^{-1}$. One must not assert that strong-test passing bases form a subgroup; the kernel argument above concerns the Fermat statement requested here.