= Solution
For the plain pseudoprime assertion use the <Fermat primality test>. In the finite <group of units modulo an integer>, let
$$
L=\{b\in(\mathbb Z/N\mathbb Z)^\times:b^{N-1}=1\}.
$$
It 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\varphi(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 $\varphi(N)-|L|$ failures out of $\varphi(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.
Back to article page
