Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 11I / b

We prove that (i) implies (ii). Since $b$ is primitive modulo $p$, writeBeing primitive modulo $p^2$ is equivalent to $p\nmid c$. The binomial theorem then gives inductivelyIt follows that the order modulo $p^m$ is exactlyso $b$ is primitive modulo every $p^m$. This is lifting a primitive root to odd prime powers. The implication (ii)$\Rightarrow$(i) is immediate by taking $m=2$.

This implication is already contained in part (i): being primitive modulo every $p^m$ plainly includes being primitive modulo $p^2$, while primitivity modulo $p^2$ lifts to every higher power by the valuation calculation there.

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$, soBecause $p-1$ divides $p^2-1$, the composite number $p^2$ satisfiesit 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\ge 2$. By part (i),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)$\iff$(iii), and all three statements are equivalent.