# 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.

## 2 Answers

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 '19 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 '19 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 – vujazzman Oct 19 '19 at 7:55
• And by the notation, I just mean those are not equal mod $43^{63}$. – vujazzman Oct 19 '19 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.$ – DanielWainfleet Oct 20 '19 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.