# 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$.

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

• It does not solve my query. – epsilon_delta Nov 21 '19 at 10:36
• The title does not reflect the question. – lhf Nov 21 '19 at 10:53

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.

• Oh so that's the name for what I call "squaring and multiplication". +1. – Oscar Lanzi Nov 21 '19 at 10:57