# 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: 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!! :)

• I have never heard of "ind". Please define this function. Jan 31, 2021 at 15:52
• A pattern suggests itself if you look at examples. Try $p=2,3,5,7...$ and look at some small primes $q$.
– lulu
Jan 31, 2021 at 16:01
• ind(x)=k refers to the smallest exponent k such that r^k is congruent to x modulo p, where p is a prime and r is a primitive root of p. Hope this answers ur q @Peter Jan 31, 2021 at 16:03
• @lulu please elaborate Jan 31, 2021 at 16:04
• Just look at examples. If $p=2$, what is the least $q$ that works? What about $p=3,5, 7$ and so on? I think you will spot a pattern rather quickly (and then, of course, you need to prove that it works). Should stress: I don't know that the obvious pattern works. It appears to work in examples.
– lulu
Jan 31, 2021 at 16:06

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