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

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.

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.

• Can you explain the notation? I've never seen it before.
– user706791
Oct 19, 2019 at 7:47
• Also, would you happen to know how to find the smallest positive prime divisor of $1^{60}+2^{60}+...+33^{60}$?
– user706791
Oct 19, 2019 at 7:51
• Factoring numbers that large can in the worst case be intractable. However, by just checking the first few numbers, you can check that 17 divides that quantity Oct 19, 2019 at 7:55
• And by the notation, I just mean those are not equal mod $43^{63}$. Oct 19, 2019 at 23:30
• If $p$ is an odd prime and $x$ is a primitive root mod $p$ and if $x$ is not a primitive root mod $p^2$ then $x+p$ is a primitive root mod $p^n$ for all $n\ge 2.$ Oct 20, 2019 at 2:25

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.