Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 4 / 1H / Solution

Choose an integer $b$ whose reduction is a primitive root modulo $p$. At least one of $b,b+p$ satisfies $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$, because the binomial theorem givesand the added coefficient is nonzero modulo $p$. Both choices still generate the multiplicative group modulo $p$. Choose such a $g$ and write $g^{p-1}=1+up$ with $p\nmid u$.

For $k\ge 1$ and $p\nmid v$, another binomial expansion showsThe intermediate binomial coefficients are divisible by $p$, and the final term also has valuation at least $k+2$ because $p$ is odd. Induction therefore givesThus $g^{p-1}$ has order exactly $p^{n-1}$ modulo $p^n$. The order of $g$ itself is divisible by $p-1$, by reduction modulo $p$, and divides the number $p^{n-1}(p-1)$ of invertible residue classes. Its order must consequently be precisely that number. This proves the lifting a primitive root to odd prime powers result andFor the requested example choose $g=2$. Modulo $11$, $2^5\equiv -1$ and $2^2\not\equiv 1$, excluding the proper divisors $1,2,5$ of ten, so its order is ten. Also $2^{10}-1=1023=11\cdot 93$, which is not divisible by $11^2$. Hence