1

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?

Bean Guy
  • 321
  • 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$. – TonyK Dec 28 '20 at 12:18
  • This is not true, since $e=2$ contradicts this fact. I just wanted to know if there exists another criteria. – Bean Guy Dec 28 '20 at 16:53

1 Answers1

4

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

Similar considerations hold for the multiplicative group of any finite field.

Andrea Mori
  • 26,969
  • 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? – Bean Guy Dec 28 '20 at 16:52
  • 1
    @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 https://en.wikipedia.org/wiki/Discrete_logarithm – Andrea Mori Dec 29 '20 at 14:10