# How many solutions to $x^d\equiv a\pmod {p}$?

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$.

If $\gcd(d,p-1) > 1$, there are exactly $d$ solutions to $x^d\equiv a\pmod p$.

$p$ prime, $d\ge 1$, $a\not\equiv 0\pmod p$. I've found this on the Internet and it's the first time I've seen it.

It's, of course, related to FLT: $\,p\nmid x\,\Rightarrow\,x^{p-1}\equiv 1\pmod p$.

edit: I've refuted the 2nd statement: if $d=k(p-1), k\ge 2$, then $a\not\equiv 1\pmod {p}$ gives no solutions and $a\equiv 1\pmod p$ gives $p-1$ ($\neq k(p-1)$) solutions.

The 2nd statement really sounds silly after you think about it: the number of solutions is surely $\le |\mathbb Z_p\setminus\{0\}|=p-1$ and yet $d$ is unconstrained in size.

• What is your question, exactly? Do you want a proof? – A.P. May 2 '15 at 11:35
• @A.P. yes, I want a proof of the two statements. I assume they are both correct. – user236182 May 2 '15 at 11:35
• The first difficulty is that the number of solutions (when $\gcd(d,p-10>1$) depends on $a$, not just on $d$. E.g., $x^2=1$ has 2 solutions modulo 3, but $x^2=2$ has none. – Gerry Myerson May 2 '15 at 13:10

## 1 Answer

The statements are not correct there is some small mistakes in them there is a correction in the end of this answer.

Let's prove a similar statement using the fact that $Z_p^*$ is a cyclic group this means that there exists an element $g$ of order $p-1$ ($g^i\equiv 1\mod p$ if and only if $p-1$ divides $i$) such that: $$\Bbb Z_p=\{0,1,g,g^2,\cdots,g^{p-2}\}$$ Given a positive integer $d$, let $\gcd(d,p-1)=m$ and let $a=g^n$ be an element of $\Bbb Z_p^*$ we have (modulo $p$): $$x^d=a\overset{\color{#f00}{x=g^k}}\iff (g^k)^d=g^n\iff g^{kd-n}=1\iff p-1|kd-n$$ and from hare we have:

• If $m$ does not divide $n$ then no solution exists.
• If $m$ divides $n$ then the number of solutions is the number of integers $0\leq k\leq p-2$ such that $\frac{p-1}{m}$ divides $k\frac{d}{m}-\frac{n}{m}$ which can be written as the congruence: $$k\frac{d}{m}\equiv \frac{n}{m}\mod \frac{p-1}{m}$$

which has only one solution $k_0$ less than $\frac{p-1}{m}$ which is the inverse of $\frac{d}{m}$ modulo $\frac{p-1}{m}$ so it has exactly $m$ solutions modulo $p-1$ and these solutions can be written $k_1=k_0,k_2=k_0+1\cdot\frac{p-1}{m},\cdots,k_m=k_0+(m-1)\cdot \frac{p-1}{m}$.

In order to return to the initial equation the solutions are: $$x_1=g^{k_1},\cdots,x_m=g^{k_m}$$

Conclusion

If $\gcd(d,p-1)=m$ and $a$ is a non null $m$-th power then the equation $x^d=a$ has exactly $m$ solutions in the field $\Bbb Z_p$, if $a$ is not an $m$-th power no solution exists.

In order to correct the statements I would say that:

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$.

If $\gcd(d,p-1) > 1$, and the equation $x^d\equiv a\mod p$ has one solution then there are exactly $\gcd(d,p-1)$ solutions to $x^d\equiv a\pmod p$.