I know how to find the primitive roots modulo $23$ and and the primitive roots modulo $23^2=529$, in which we are finding the primitive roots of prime powers.
My questions are what if we want to find the primitive roots of $46$ $(=2\times23)$ and $12167$ $(=23\times529)$?
How can we relate to the primitive roots of $23$ and $529$ that we had found previously? Which theorems can we use?
Many thanks for the helps!
On
The crucial fact is this:
If $g$ is a primitive root mod $p$, then $g$ or $g+p$ is a primitive root mod $p^n$ for all $n\ge 1$.
You'll find that all primitive roots mod $23$ are primitive roots mod $23^n$, but this does not always happen.
Edit: It has been pointed out that if we have a primitive root mod $p$, we can easily find primitive roots mod $p^n$ and $2p^n$. My mistake. I believe the following still holds for arbitrary $n$ not of those forms.
I could be wrong, but I believe that there is no elementary way to find primitive roots $g \pmod{n}$ for arbitrary $n$.
If I were writing a computer program to find primitive roots, I would simply iterate through the set of units modulo n:
$$ U_n = \{m \in \{0,1,...,(n-1)\} : gcd(m,n) = 1\} $$
For each $m \in U_n$, I would use modular exponentiation (computationally cheap) to find $m^k$ for $k \in \{d \in \{1,2,...,\phi(n)\} : d | \phi(n)\}$. We know that the order of $U_n$ is $\phi(n)$, and by Lagrange's theorem the order of any element must divide the order of $U_n$, so we need only check if the order of an element is a divisor of $\phi(n)$. I would break out of the loop if $m^k \equiv 1$ for some $k < \phi(n)$, since the primitive roots are the elements of order $\phi(n)$.
As for finding them on paper, I'd basically use the same method although it would take a lot longer. There may exist computationally faster methods, but I don't know what they are. Honestly though, for any example where I have needed to find a primitive root by hand, I have found one within the first few iterations.