1
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh so that's the name for what I call "squaring and multiplication". +1. $\endgroup$ – Oscar Lanzi Nov 21 '19 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.