2
$\begingroup$

I know how to find primitive roots of relatively small primes. But how can one possibly find a primitive root modulo $5^{10}$? I can't test every single number less than $5^{10}$. Is there a fast way to locate just one primitive root of $5^{10}$?

$\endgroup$
5
$\begingroup$
  1. Find a primitive root mod $5$. I notice $3$ is a primitive root mod $5$.

  2. Either $3$ or $3 + 5 = 8$ will be a primitive root mod $25$. A quick check shows that $3$ is still a primitive root mod $25$.

  3. A primitive root mod $25$ will be a primitive root mod $5^k$ for all $k \geq 1$.

This works because of a few fundamental ideas concerning primitive roots.

Lemma: If $g$ is a primitive root mod an odd prime $p$, then either $g$ or $g + p$ is a primitive root mod $p^2$.

Proof: This is the theorem in this answer, although the phrasing is a little bit different.

And also,

Lemma: If $g$ is a primitive root mod $p^2$ where $p$ is an odd prime, then $g$ is a primitive root mod $p^k$ for all $k \geq 1$.

Proof: See this question and its answers.

$\endgroup$
  • $\begingroup$ $2$ is also a primitive root mod $5$. A bit smaller. $\endgroup$ – user236182 Oct 19 '17 at 12:30

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.