# Is there any general criteria to find $e$'th roots modulo a primer number $p$?

It is known that if $$p$$ is an odd prime and $$\gcd(e, p-1) = 1$$, then one can easily find an $$e$$'th root of every $$a \in \mathbb{Z}_p$$ by computing $$d \equiv e^{-1} \pmod{p-1}$$: $$a^{de} = a^{k(p-1)+1} = (a^{p-1})^k a = a.$$

Also, if $$e = 2$$ (meaning that $$\gcd(2, p-1) \neq 1$$) we know how to efficiently compute square roots modulo a prime $$p$$.

But note that the first sentence is just an implication: $$\gcd(e, p-1) = 1 \implies \exists x \in \mathbb{Z}_p,~ x^e \equiv a \pmod{p}$$ What about the other implication? Do we know something? Do we have a general "if and only if" criteria for the existence of an $$e$$'th root, even if it is proven using a constructive proof?

• So you are asking this: If there exists $x\in\Bbb Z_p$ such that $x^e\equiv a\bmod p$, then $\gcd(e,p-1)$ must equal $1$. Do I have that right? But that surely depends on $a$. Dec 28, 2020 at 12:18
• This is not true, since $e=2$ contradicts this fact. I just wanted to know if there exists another criteria. Dec 28, 2020 at 16:53

For any $$n\in\mathbb{Z}$$ the map $$\mathbb{Z}_p^\times\longrightarrow\mathbb{Z}_p^\times\qquad x\mapsto x^n$$ is a homomorphism which is surjective if and only if $${\rm gcd}(n,p-1)=1$$. This is a straightforward consequence of the fact that the multiplicative group $$\mathbb{Z}_p^\times$$ is cyclic.
So, given any $$n>0$$ there are $$\frac{p-1}{{\rm gcd}(n,p-1)}$$ elements in $$\mathbb{Z}_p^\times$$ that have a $$n$$-th root.
The problem is that it is hard to get a practical characterization of this set since we don't easily know a generator of $$\mathbb{Z}_p^\times$$, e.g. see Artin's Conjecture
• Well the generators of $\mathbb{Z}_p^*$ are basically the generators of $\mathbb{Z}_{p-1}$, i.e., $\mathbb{Z}_{p-1}^*$. Why do you mean that it is not easy to obtain them? Dec 28, 2020 at 16:52
• @BeanGuy: The problem is that you know that $\mathbb{Z}_p^\times$ is cyclic of order $p-1$ but you don't have an explicit isomorphism with the additive group $\mathbb{Z}_{p-1}$. This phenomenon has actually practical implications, e.g. in cryptography, see en.wikipedia.org/wiki/Discrete_logarithm Dec 29, 2020 at 14:10