Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 11I / b / iii / 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$, 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.

Solved by gpt-5.6-sol high.