1
$\begingroup$

I know how to find the primitive roots modulo $23$ and and the primitive roots modulo $23^2=529$, in which we are finding the primitive roots of prime powers.

My questions are what if we want to find the primitive roots of $46$ $(=2\times23)$ and $12167$ $(=23\times529)$?

How can we relate to the primitive roots of $23$ and $529$ that we had found previously? Which theorems can we use?

Many thanks for the helps!

$\endgroup$
7
  • 4
    $\begingroup$ Every odd primitive root modulo a prime $p$ is automatically a primitive root modulo $2p$, and every primitive root modulo $p^2$ is automatically a primitive root modulo $p^3$, $p^4$, etc. The first statement, you should be able to prove yourself! (The second statement is somewhat deeper.) $\endgroup$
    – Greg Martin
    Oct 16, 2015 at 3:54
  • $\begingroup$ @GregMartin. So you are saying that since 23 is odd, so the primitive root mod 23 is the same as the primitive root mod 46? or the primitive root mod 23 is the subset of the primitive root mod 46? if it is a subset how can we find the remaining primitive roots? Thanks. $\endgroup$
    – user71346
    Oct 16, 2015 at 3:59
  • 1
    $\begingroup$ @user71346 No, if you read the comment carefully, the adjective "odd" applies to the primitive root, not the prime. $\endgroup$
    – Erick Wong
    Oct 16, 2015 at 4:22
  • $\begingroup$ @ErickWong. Yes, I mean the primitive root, sorry. So if 5 is a primitive root mod 23, is there any other primitive root mod 46 besides 5? $\endgroup$
    – user71346
    Oct 16, 2015 at 4:25
  • $\begingroup$ If $n$ has one primitive root then it has $\phi(\phi(n))$ of them (distinct modulo $n$). Of course there are others besides $5$: just pick any other odd primitive root modulo $23$. $\endgroup$
    – Erick Wong
    Oct 16, 2015 at 4:43

2 Answers 2

Reset to default
1
$\begingroup$

The crucial fact is this:

If $g$ is a primitive root mod $p$, then $g$ or $g+p$ is a primitive root mod $p^n$ for all $n\ge 1$.

You'll find that all primitive roots mod $23$ are primitive roots mod $23^n$, but this does not always happen.

$\endgroup$
1
0
$\begingroup$

Edit: It has been pointed out that if we have a primitive root mod $p$, we can easily find primitive roots mod $p^n$ and $2p^n$. My mistake. I believe the following still holds for arbitrary $n$ not of those forms.

I could be wrong, but I believe that there is no elementary way to find primitive roots $g \pmod{n}$ for arbitrary $n$.

If I were writing a computer program to find primitive roots, I would simply iterate through the set of units modulo n:

$$ U_n = \{m \in \{0,1,...,(n-1)\} : gcd(m,n) = 1\} $$

For each $m \in U_n$, I would use modular exponentiation (computationally cheap) to find $m^k$ for $k \in \{d \in \{1,2,...,\phi(n)\} : d | \phi(n)\}$. We know that the order of $U_n$ is $\phi(n)$, and by Lagrange's theorem the order of any element must divide the order of $U_n$, so we need only check if the order of an element is a divisor of $\phi(n)$. I would break out of the loop if $m^k \equiv 1$ for some $k < \phi(n)$, since the primitive roots are the elements of order $\phi(n)$.

As for finding them on paper, I'd basically use the same method although it would take a lot longer. There may exist computationally faster methods, but I don't know what they are. Honestly though, for any example where I have needed to find a primitive root by hand, I have found one within the first few iterations.

$\endgroup$
4
  • $\begingroup$ This is informative but it doesn't address the question at all. There is indeed a very easy way to obtain primitive roots modulo $p^k$ and $2p^k$ once you have a primitive root modulo $p$. $\endgroup$
    – Erick Wong
    Oct 16, 2015 at 4:36
  • $\begingroup$ My mistake, I forgot about that method, edited. $\endgroup$
    – William Henry Langhoff
    Oct 16, 2015 at 4:54
  • 1
    $\begingroup$ And arbitrary $n$ don't possess primitive roots at all, so it's important to know which ones do before spending all this time looking for them. $\endgroup$
    – Greg Martin
    Oct 16, 2015 at 7:27
  • $\begingroup$ About your edit: if $n$ is not of the form $p^m$ or $2p^m$, then there is no primitive root modulo $n$.. $\endgroup$
    – N. S.
    Nov 6, 2017 at 1:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .