= Solution
For odd $N>1$ coprime to $b$, the <Fermat pseudoprime> test is $b^{N-1}\equiv1\pmod N$. The <Euler pseudoprime> test meant here is the Euler–Jacobi test,
$$
b^{(N-1)/2}\equiv\left(\frac bN\right)\pmod N,
$$
where the right side is the <Jacobi symbol>. Write $N-1=2^sd$, with $d$ odd. The <strong pseudoprime> test passes when $b^d\equiv1$, or when $b^{2^jd}\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\cdot31$ is composite and $2^{10}=1024\equiv1\pmod{341}$, so $2^{340}\equiv1$. It passes the <Fermat primality test>. However $2^{170}\equiv1$, whereas the supplementary law for the <Jacobi symbol> gives $(2/341)=-1$ since $341\equiv5\pmod8$. Thus \b[341 is Fermat but not Euler–Jacobi pseudoprime to base two]. A weaker convention defining an Euler test merely by $b^{(N-1)/2}=\pm1$ would not give the claimed distinction, which is why the Jacobi convention matters.
Back to article page
