The prime $ p = 71$ has $7$ as a primitive root. Find all primitive roots of $71$ and also find a primitive root for $p^2$ and for $2p^2$.

Question

The prime $ p = 71$ has $7$ as a primitive root. Find all primitive roots of $71$ and also find a primitive root for $p^2$ and for $2p^2$.

This is a question from Apostol's Analytic Number theory. I could solve the first part of the question. I want to use the following theorem for the next part:

" If $g$ is primitive root mod $p$, then it is primitive root $p^{\alpha}$ iff $g^{p-1} \not \equiv 1 \mod p^2$." But finding $7^{70} \mod 71^2$, I suppose is not easy. If we find one primitive root then the numbers $7^a, (a,71^2)=1$are the others root.

So how can I find $7^{70} \mod 71^2 \text{or at least show that it is not $\not \equiv 1$ }$ ?

Thank You

Answer 1

Mod $71^2$ we have:

$7^2 \equiv 49$

$7^4 \equiv 49^2 = 2401$

$7^8 \equiv 2401^2 \equiv 2938$

$7^{16} \equiv 2938^2 \equiv 1652$

$7^{32} \equiv 1652^2 \equiv 1923$

$7^{64} \equiv 1923^2 \equiv 2876$

$7^{70} = 7^{64} \cdot 7^{4} \cdot 7^{2} \equiv 2876 \cdot 2401 \cdot 49 \equiv 1563 \not\equiv 1$

This method of finding powers is called exponentiation by squaring.

However, you don't need to compute any of this: $7$ is the smallest primitive root mod $71$ and the smallest primitive root mod $p$ is a primitive root mod $p^2$ for all odd $p<40487$. See OEIS:A055578.