= Solution
For an odd composite $N$ and a unit $b$ modulo $N$, $N$ is a <Fermat pseudoprime> to base $b$ when
$$
b^{N-1}\equiv1\pmod N.
$$
It is an <Euler pseudoprime> to base $b$ when
$$
b^{(N-1)/2}\equiv\left(\frac bN\right)\pmod N,
$$
where the right side is the Jacobi symbol.
By the Chinese remainder theorem,
$$
(\mathbb Z/105\mathbb Z)^\times
\cong(\mathbb Z/3\mathbb Z)^\times
\times(\mathbb Z/5\mathbb Z)^\times
\times(\mathbb Z/7\mathbb Z)^\times,
$$
and $\varphi(105)=2\cdot4\cdot6=48$. The condition $b^{104}=1$ is automatic modulo $3$ and $5$. Modulo $7$ it has
$$
\gcd(104,6)=2
$$
solutions. Thus there are $2\cdot4\cdot2=16$ Fermat <bases>, giving proportion
$$
\boxed{\frac{16}{48}=\frac13}.
$$
For the Euler condition, $b^{52}=1$ modulo $3$, so the Jacobi symbol must be $+1$. The power condition is automatic modulo $5$, while modulo $7$ it again restricts $b$ to the two solutions of $b^2=1$. For each of those two residues, exactly half of the $2\cdot4$ choices modulo $3$ and $5$ have Jacobi symbol $+1$. Hence there are $2\cdot4=8$ Euler <bases> and proportion
$$
\boxed{\frac8{48}=\frac16}.
$$
Back to article page
