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

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.