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

Question

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.

Answer 1

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.

Answer 2

A primitive root can be shown to exist (that is the group of units is cyclic) iff the integer is $1,2,4,p^k$ or $2p^k$ for $p$ an odd prime.

Gauß knew this. He gave an existence proof, as well as a constructive proof (for $p$ prime), in his Disquisitiones Arithmeticae of $1801$.

To find a primitive element $\pmod n$, one approach is to factor $\varphi(n)$, and look for an element whose order isn't a (proper) factor. There are algorithms, such as successive squaring, to help with computing this order.