# Prove that there are infinitely many primes which are primitive roots modulo $N$

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.

• This could be hard.... See for instance here: citeseerx.ist.psu.edu/viewdoc/… – Vincent Apr 4 at 18:30
• Murty's result is so surprising! But that is not that close to this problem, since it is not about a specific arithmetic progression. – Kanu Kim Apr 4 at 19:41
• 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. – Vincent Apr 4 at 20:18

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.
• 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... – Vincent Apr 4 at 18:21
• @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? – Keith Backman Apr 4 at 18:49
• 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... – Kanu Kim Apr 5 at 6:23
• 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$. – Robert Israel Apr 5 at 12:05