Assuming $N$ has a primitive root, show that there are infinitely many primes which are primitive roots modulo $N$.

It is obviously true using Dirichlet's theorem on primes, but I want to prove without this. There is a given hint:

Try to mimic the proof of that there are infinitely many primes of the form $3n-1$, $4n+3$ or $5n\pm 2$.

This proof basically is as follows:

  • If $N=q_1\cdots q_s$ is, say, congruent to 3 modulo 4, then one of $q_i$ should be congruent to 3 modulo 4.
  • List all such primes $p_1,\cdots,p_r$, and let $N = \alpha p_1\cdots p_r + C$ for some $\alpha$ and $C$ so that $N$ cannot be divided by any of $p_i$ but it must has a prime factor of the given form, leading to a contradiction.

I tried to, but failed to show both steps:

  • Can I derive that if $M = q_1\cdots q_s$ is a primitive root modulo $N$ then one of $q_i$ is also a primitive root modulo $N$?
    • Counterexample by Robert: $2$ and $6$ are not primitive roots mod $7$, but $2\cdot 6=12$ is.
    • What if $q_i$'s are primes?
      • Counterexample by Annyeong: $52=2\cdot 2\cdot 13\equiv 3 \pmod 7$ is a primitive root but $2$ and $13\equiv 6$ are not modulo $7$.
    • Any other method to get the similar proof? I think $N$ should be sort of a polynomial of $p_1\cdots p_r$, as in the proof for $2kp+1$-primes
  • How to choose $\alpha$ and $C$ above?
  • We cannot prove that there are infinitely many primes congruent to a specific primitive root in this way, by Murty. (See the comment below by Vincent.)

Any helps and hints are welcome!

Update: Professor has retracted this problem from the homework.

  • 1
    $\begingroup$ This could be hard.... See for instance here: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Vincent
    Apr 4, 2019 at 18:30
  • 1
    $\begingroup$ Murty's result is so surprising! But that is not that close to this problem, since it is not about a specific arithmetic progression. $\endgroup$
    – Kanu Kim
    Apr 4, 2019 at 19:41
  • 2
    $\begingroup$ Yes, but it is tempting to try and prove it for a specific progression $Nn + a$ where the only property of $a$ we use is that it is a primitive root mod $N$. But if I understand Murty correctly that approach won't work and we need something like showing that the primitive root classes mod N together have infinitely many primes, without being able to show it for any individual class. This sounds tricky, though. $\endgroup$
    – Vincent
    Apr 4, 2019 at 20:18

1 Answer 1


It's certainly not true that if $M = q_1 \ldots q_n$ is a primitive root mod $N$ then one of the $q_i$ is a primitive root mod $N$. For example, $2$ and $6$ are not primitive roots mod $7$, but $2 \cdot 6 = 12$ is.

  • $\begingroup$ I see. Well... Then, is there any elementary way to mimic the given proofs? $\endgroup$
    – Kanu Kim
    Apr 4, 2019 at 17:03
  • 1
    $\begingroup$ On the bright side, your original approach DOES work in case $N$ is such that the regular $N$-gon can be constructed by ruler and compass (which is obviously the case for the examples $N=4, N=5$ and $N=3$ from the hint.) Still it would be nice to have a proof that works for $N = 7$ and $N = 9$ as well... $\endgroup$
    – Vincent
    Apr 4, 2019 at 18:21
  • $\begingroup$ @Robert Israel I note that OP does not require that $q_i$ be prime, but if $q_i$ are not prime, then we have choices as to how to represent the factorization of $M$. In the case that we represent $12=2\cdot 2\cdot 3$ we observe that $3$ is a primitive root mod $7$, consonant with OP's sought for derivation. I'm not sure that whether this merely addresses your example, or the truth of the general assertion. If $M$ is a primitive root and $q_i$ are prime, will one of them necessarily be a primitive root? $\endgroup$ Apr 4, 2019 at 18:49
  • 1
    $\begingroup$ Someone found a counterexample for the prime case: $52 = 2 \cdot 2 \cdot 13$ is a primitive root modulo 7 but 2 and 13(=6) are not... $\endgroup$
    – Kanu Kim
    Apr 5, 2019 at 6:23
  • 1
    $\begingroup$ Also $26 = 2 \cdot 13$ is a primitive root mod $7$. This is really the same example as mine, because $13 \equiv 6 \bmod 7$. $\endgroup$ Apr 5, 2019 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.