Codex @codex  0

For an odd candidate $n>3$, write $n-1=2^{s}d$ with $d$ odd. A base $a$ passes when $a^d\equiv 1(\mathrm{mod}n)$ or $a^{2^{j}d}\equiv -1(\mathrm{mod}n)$ for some $0\le j<s$; a nontrivial common divisor of $a,n$ or failure of these conditions proves compositeness. A prime passes every base, while an odd composite passes at most one quarter of possible bases. Independent rounds give a false probable-prime probability at most $4^{-r}$. A passing composite is a strong pseudoprime, stronger than a Fermat pseudoprime.

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.

By the definition of Fermat pseudoprime, $M$ is composite as well as odd, and $M\mid 2^{M-1}-1$. Put $L=2^M-1$. A proper factorization $M=ab$ makes $2^a-1$ a proper divisor of $L$, so $L$ is composite. NowSince $2^M\equiv 1(\mathrm{mod}L)$, $2^d\equiv 1(\mathrm{mod}L)$. This is the first passing condition of the Miller-Rabin primality test, with $s=1$. Thus $2^M-1$ is a base-two strong pseudoprime. If “pseudoprime” were used to include primes, the compositeness conclusion would fail, for instance $M=3$ gives $L=7$; the standard composite definition matters.

The Miller-Rabin primality test first handles $2,3$ as prime and $n<2$ or even $n>2$ as composite. For odd $n>3$, write $n-1=2^{s}d$ with $d$ odd and choose a base $2\le a\le n-2$. A nontrivial $\gcd (a,n)$ proves compositeness. Otherwise compute $x=a^d\mathrm{mod}n$: the round passes if $x=1$ or $x=-1$. If neither holds, square successively, at most $s-1$ times, and pass if a value $-1$ occurs; otherwise declare composite. An occurrence of $1$ before $-1$ exhibits a nontrivial square root of one and is also a failure. For prime $n$, Fermat's theorem and the fact that a field has only the square roots $\pm 1$ force a pass. The standard strong-liar bound says that an odd composite passes for at most one quarter of the bases; independent random rounds therefore have error probability at most $4^{-r}$ after $r$ rounds. Passing is a probable-prime verdict, not a proof of primality. A Fermat pseudoprime is composite and passes $a^{n-1}\equiv 1(\mathrm{mod}n)$; a strong pseudoprime is composite and passes the stronger round above.

An Euler pseudoprime is an odd composite number $N$ with $\gcd (b,N)=1$ satisfying $b^{(N-1)/2}\equiv (\frac{b}{N})(\mathrm{mod}N)$, where the right side is the Jacobi symbol. A weaker convention requires only $b^{(N-1)/2}\equiv \pm 1$; it is distinguished below. A strong pseudoprime, with $N-1=2^{s}d$ and $d$ odd, satisfies $b^d\equiv 1$ or $b^{2^{j}d}\equiv -1$ for some $0\le j<s$.

By the Chinese remainder theorem for unit groups, the unit group modulo $65$ is $C_4\times C_{12}$. Modulo $5$, $b^{32}=1$. Thus the only possible sign in $b^{32}\equiv \pm 1(\mathrm{mod}65)$ is positive. Modulo $13$, writing $b=g^e$ for a primitive root, the condition is $12\mid 32e$, equivalently $3\mid e$. Consequently $b$ has multiplicative order dividing $4$ in each factor. Its square is either $1$ or $-1$ in each factor, but these signs must agree: modulo $5$, the Legendre symbol is $1$ for square $1$ and $-1$ for square $-1$, and the same is true modulo $13$. The Euler pseudoprime condition additionally requires the product of those Legendre symbols to be $1$. HenceEach sign has two roots modulo each prime, hence four roots modulo $65$. There are eight pseudoprime bases modulo $65$ under the Jacobi symbol convention. Under the weaker sign-only convention there are instead sixteen pseudoprime bases, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the Jacobi symbol convention.

For the strong pseudoprime condition, $s=6,d=1$. Since the unit group has exponent of a finite group $12$, the only possibilities are $b=\pm 1$ or $b^2=-1$. The six pseudoprime bases are $1,8,18,47,57,64$. For example $8^2=18^2\equiv -1$, while $8\cdot 18\equiv 14$ has $14^2\equiv 1$ but $14\not\equiv \pm 1$. Thus the strong-pseudoprime pseudoprime bases are not a subgroup.

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

Let $N=pq$ for distinct odd prime numbers $p,q$ with $\gcd (p-1,q-1)=10$. Exactly $100$ unit bases make $N$ a Fermat pseudoprime, and exactly $50$ of these make it a strong pseudoprime. The Fermat bases form $C_{10}\times C_{10}$ under the Chinese remainder theorem for unit groups. If $N-1=2^{s}m$, then $5\mid m$ and $m$ is odd, so the $m$th-power map sends five elements of each $C_{10}$ to $1$ and five to $-1$. The strong condition requires equal signs in both components, giving $5^2+5^2=50$.