0
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Can you explain the notation? I've never seen it before. $\endgroup$
    – user706791
    Oct 19, 2019 at 7:47
  • $\begingroup$ Also, would you happen to know how to find the smallest positive prime divisor of $1^{60}+2^{60}+...+33^{60}$? $\endgroup$
    – user706791
    Oct 19, 2019 at 7:51
  • $\begingroup$ 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 $\endgroup$
    – vujazzman
    Oct 19, 2019 at 7:55
  • $\begingroup$ And by the notation, I just mean those are not equal mod $43^{63}$. $\endgroup$
    – vujazzman
    Oct 19, 2019 at 23:30
  • $\begingroup$ 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.$ $\endgroup$ Oct 20, 2019 at 2:25
1
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.