= Solution
Suppose first that $b$ is not primitive modulo $p^2$. Since it is primitive modulo $p$, its order modulo $p^2$ is then $p-1$, so
$$
b^{p-1}\equiv1\pmod{p^2}.
$$
Because $p-1$ divides $p^2-1$, the composite number $p^2$ satisfies
$$
b^{p^2-1}\equiv1\pmod{p^2};
$$
it is a <Fermat pseudoprime> to base $b$ and is divisible by $p^2$. Thus (iii) fails.
Conversely, suppose $b$ is primitive modulo $p^2$ and a base-$b$ pseudoprime $N$ is divisible by $p^a$ with $a\geq2$. By part (i),
$$
\operatorname{ord}_{p^a}(b)=p^{a-1}(p-1).
$$
The pseudoprime congruence forces this order to divide $N-1$, so in particular $p\mid N-1$. But $p\mid N$, a contradiction. Hence no such pseudoprime exists. This proves (i)$\Leftrightarrow$(iii), and all three statements are equivalent.
Back to article page
