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
Best Answer
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.