To prove that it is possible to find a prime number q with a primitive root r such that ind(p) is a prime, for a particular prime p.

Question

Question: Let $p$ be a prime number. Prove that there exist a prime number $q$ such that for every integer $n$, the number $n^{p}-p$ is not divisible by $q$.

I was trying to solve the above question with an original method using indices and I couldn't proceed after a certain point. My approach is shown below

$\textbf{Approach:}$ The congruence $n^{p}\equiv p\pmod{q}$ can be reduced to $$p\cdot ind(n)\equiv ind(p) \pmod{q-1}$$ We can do this since every prime has a primitive root. A solution to this congruence exists iff $gcd(ind(n), q-1)|ind(p)$. Thus, if the congruence has no solution for all integers $n$, then it is logical to conclude that $ind(p)$ could be a prime. Hence, I present the following lemma

$\textbf{Lemma:}$ It is possible to find a prime $q$ with a primitive root $r$ such that $ind_{r}(p)$ is a prime number.

It would be a great help if someone could prove or disprove the above Lemma. Thanks a lot for your help!! :)

Answer 1

If $ind_r(p)$ is coprime with $q-1$, then $p \equiv r^{ind_r(p)}$ is a primitive root $\bmod q$ (as $ind_r(p)$ is invertible $\bmod q-1$). Conversely, given a prime $q$ for which $p$ is a primitive root, we may pick any prime $i$ coprime with $q - 1$ and obtain a primitive root $r$ for which $ind_r(p) = i$ by $r \equiv p^{i^{-1}}$.

We therefore need to prove that all primes $p$ are primitive roots modulo some prime $q > p$.