Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 11I (Number Theory)

An integer $b$ is a primitive root modulo $n$ when it is coprime to $n$ and its residue class generates the multiplicative group of integers modulo n. Equivalently,

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.

By lifting a primitive root to odd prime powers, it is enough to test primitivity modulo $25$. The positive integers below eight either fail to be units or have orderswhereasTherefore the three smallest required integers are

By the primitive-root modulus classification, $P(n)>0$ only forwith $p$ an odd prime, and thenFix $k\ge 1$. The finite fibres of the Euler totient function imply that there are only finitely many possible values $m=\phi (n)$ satisfying $\phi (m)=k$. For each such $m$, the same result gives only finitely many $n$ satisfying $\phi (n)=m$. The union of these finitely many finite sets is finite, proving the claim.