Find one primitive root of $\pmod{43^{63}}$

number theoryprimitive-roots

Find one primitive root of $\pmod{43^{63}}$.
Also, is there a general formula for finding the primitive roots modulo an integer $n$?

In regards to the second question, if there is no general formula, then is there a proof that affirms this?

Here's what I done so far in regards to the specific question:
It's possible that there's a primitive root since it is of the form $p^k$, but it might not have a primitive root.
Apparently, $a$ is a primitive root modulo $n$ if and only if $\phi(n)$ (i.e. Euler's totient function) must be the multiplicative order of $a$, but this obviously doesn't even come close to simplifying this problem.

I strongly believe that there is no general formula for finding primitive roots. This should be obvious due to the "random" behaviour of numbers, though as for the proof, I am completely lost. It might be on Wikipedia or some advanced math website.

Edit: Initially I used $63^{43}$ but that clearly cannot have a primitive root since the set of integers coprime to it doesn't form a cyclic group.
Also, according to Wikipedia, it seems like the number of primitive roots increases as the number increases, so I've changed the requirement to $1$ primitive root.

Best Answer

3 is a primitive root mod $43^{63}$. To see this, note that $\phi(43^{63}) = 2\cdot 3\cdot 7 \cdot 43^{62}$, and $3^{3\cdot 7 \cdot 43^{62}} \ne 1$, $3^{2\cdot 7\cdot 43^{62}} \ne 1$, $3^{2\cdot 3\cdot 43^{62}} \ne 1$, and $3^{2\cdot 3\cdot 43^{61}} \ne 1$, mod $43^{63}$.

In general, tests for primitive roots are fast to perform once you've factored $\phi(n)$. Since primitive roots are relatively frequent among all residue classes, simply randomly testing numbers (or testing small numbers until one is found), is a viable algorithm to find primitive roots.

Related Question