# How to find a primitive root modulo $5^{10}$?

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}$?

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.

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