Several algorithms exist to find the primitive roots of prime numbers. How does one find the primitive roots of a non-prime number?
closed as off-topic by Greg Martin, graydad, Claude Leibovici, Venus, user223391 Sep 1 '15 at 7:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Greg Martin, graydad, Claude Leibovici, Venus, Community
Apart from $1$, $2$, and $4$, the only numbers with primitive roots are the numbers of the shape $p^k$ or $2p^k$, where $p$ is an odd prime.
Once we have a primitive root $g$ for the odd prime $p$, finding primitive roots for $p^k$ and $2p^k$ is relatively cheap.
For $p^k$, we use the fact that if $g$ is a primitive root of $p$, then $g$ or $g+p$ is a primitive root of $p^k$ for all $k$.
So once we have found a primitive root $g$ of $p$, we test whether $g$ is a primitive root of $p^2$. If it is, we are finished. And if it is not, then we know $g+p$ is a primitive root of $p^k$ for all $k$.
As for $2p^k$, if $r$ is a primitive root of $p^k$ and $r$ is odd, then $r$ is a primitive root of $2p^k$. And if $r$ is even then $r+p^k$ is a primitive root of $2p^k$.