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.

  • $\begingroup$ What is your question, exactly? Do you want a proof? $\endgroup$ – A.P. May 2 '15 at 11:35
  • $\begingroup$ @A.P. yes, I want a proof of the two statements. I assume they are both correct. $\endgroup$ – user236182 May 2 '15 at 11:35
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 2 '15 at 13:10

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.