Finding all solutions of 'Discrete Root'

Question

Ques: $x^k \equiv a \pmod n$, where n is prime. What are the possible values of x?

I know how to find a discrete root using both primitive root and discrete logarithm concepts. But I am wondering how to find all other possible values of 'x'?

Answer 1

COMMENT.-See at the following example for the finite field $\mathbb F_7$ $$\mathbb F_7=\{1,2,3,4,5,6,0\}\\\mathbb F_7^2=\{1,4,2,2,4,1,0\}\\\mathbb F_7^3=\{1,1,6,1,6,6,0\}\\\mathbb F_7^4=\{1,2,4,4,2,1,0\}\\\mathbb F_7^5=\{1,4,5,2,3,6,0\}\\\mathbb F_7^6=\{1,1,1,1,1,1,0\}$$ and consider your equation $x^k \equiv a \pmod 7$.You find out that $$\begin{cases}k=1,\text{one solution for all }a\\k=2,\text{non solution for }a=3,5,6\\k=3,\text{non solution for }a=2,3,4,5\\k=4,\text{non solution for }a=3,5,6\\k=5,\text{one solution for all }a\\k=6,\text{it is Fermat's Little Theorem for }p=7\end{cases}$$ Now what can you infer, by helping you from the preceding example, from $$1=a^{p-1}=a^2\cdot a^{p-3}=a^3\cdot a^{p-4}=\cdots?$$ A small effort can be useful to understand your equation more.