= Solution
The <Lagrange root bound over a field> says that a nonzero <polynomial> of <degree of a polynomial>[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=\langle g\rangle$ is a <cyclic group> of order $d$. The solutions in $H$ of $x^e=1$ are
$$
1,g^{d/e},g^{2d/e},\ldots,g^{(e-1)d/e},
$$
so 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>[Fermat-pseudoprime] base precisely when its two components satisfy
$$
b^{n-1}=1\quad\hbox{in }\mathbb F_p^\times
\qquad\hbox{and}\qquad
b^{n-1}=1\quad\hbox{in }\mathbb F_q^\times.
$$
The <power roots in a finite field> and
$$
\gcd(n-1,p-1)=\gcd(q-1,p-1)=10,
\qquad
\gcd(n-1,q-1)=\gcd(p-1,q-1)=10
$$
show that each component has ten choices. Therefore there are
$$
10\cdot10=100
$$
Fermat-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
$$
\boxed{5^2+5^2=50.}
$$
Back to article page
