5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ This could be hard.... See for instance here: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Vincent
    Commented 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
    Commented 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
    Commented Apr 4, 2019 at 20:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I see. Well... Then, is there any elementary way to mimic the given proofs? $\endgroup$
    – Kanu Kim
    Commented 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
    Commented 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$
    – Keith Backman
    Commented 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
    Commented 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$
    – Robert Israel
    Commented Apr 5, 2019 at 12:05

You must log in to answer this question.

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