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!! 🙂
Best Answer
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$.