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.
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.