So I'm having a bit of trouble proving the following theorem:

Suppose that $p$ is a prime, $k \in \mathbb{N}$ and $b \in \mathbb{Z}$. Show that the number of $k$th roots of $b$ modulo $p$ is either $0$ or $(k, p - 1)$ (note that $(\cdot,\cdot) \equiv \gcd(\cdot,\cdot)$).

Here is my attempt.

If there are $0$ roots then we are done.

Suppose now that the congruence $x^k \equiv b \mod{p}$ has a solution, say $x \equiv r \mod{p}$ for some $r \in \{0, 1, 2, \dots, p - 1\}$. We know that $p$ has exactly $\phi(p - 1)$ primitive roots and that $a^{v\phi(n) + 1} \equiv a \mod{p}$ for any $a \in \mathbb{Z}$. Now, if $(r,p) \ne 1$, then either $r = 1$ or $p \vert r$. If $r = 1$, then we must have $x^k \equiv 1 \mod{p}$. We know from a previous theorem that the order of any number modulo a prime must divide $p - 1$, so $(k,p - 1) = k$ (I'm not sure where to go from here). If $p \vert r$ , then $x \equiv 0 \mod{p} \Rightarrow x^k \equiv 0 \mod{p} \Rightarrow b \equiv 0 \mod{p}$ (again no idea if I'm headed in the right direction)...

Suppose that $(r,p) = 1$. Then $r^k \equiv b \mod{p} \Rightarrow r^{k\phi(p)} \equiv b^{\phi(p)} \Rightarrow b^{p - 1} \equiv 1 \mod{p}$. I know that there are $\phi(p - 1)$ such $b$ that satisfy this, but again, I have no idea where this is going..

I think it's likely that I'm just completely venturing out in the wrong direction here. Even a nudge in the right direction would be appreciated.


If $b \not \equiv 0\bmod p$ and $x^k \equiv b\bmod p$ has one solution $x=a$ then the other solutions are $x= a\zeta$ where $\zeta^k = 1$, which has $$ \# \{ \zeta \bmod p, \text{ord}(\zeta)\ |\ k\}=\# \{ \zeta \bmod p, \text{ord}(\zeta)\ |\ (k,p-1)\}= (k,p-1)$$ solutions, since $\mathbb{Z}/p \mathbb{Z}^\times$ is cyclic with $p-1$ elements so it contains an element $\mu$ of order $(k,p-1)$ and $\zeta^k=1 \implies \zeta = \mu^n$


For root solving, I often find it easier to consider every element as power of a generator $g$. What I can suggest is setting $x\equiv g^i$ and $b\equiv g^j$ for some $0\leq i,j<p-1$ if you want to give it a try yourself. (A possible solution below.)

A solution may look something like this (can be shortened considerably):
If $b\equiv 0\pmod p$, then we have exactly 1 solution $x\equiv 0\pmod p$.

Next, suppose $b\neq 0$ and let $g$ be a generator. Then we may assume $x\equiv g^i$ and $b\equiv g^j$ for some $0\leq i,j <p$. Therefore $$g^{ik}\equiv g^j \pmod p$$

This then gives $$ik\equiv j \pmod{p-1},$$ or equivalently $$ik=j+t(p-1).$$ Now we set $$d=(k,p-1)$$ $$l=k/d, \;\; q=(p-1)/d$$ then we can rewrite the equation as $$ild=j+tqd$$ which tells us that $j\equiv 0 \pmod d$.
(Edit: If $j\not\equiv 0\pmod d$ then there are $0$ solutions, the first case.)

Letting $m=j/d$ and dividing by $d$, we get $$il=m+tq\implies i\equiv ml^{-1} \pmod q$$ (Noting that $l$ is invertible since $(l,q)=1$.) This tells us that $i$ has the form $$i=u+vq$$ for some fixed $u\in [0,q-1]$ (such that $u\equiv ml^{-1} \pmod q$) and any $v$. To get distinct solutions, we set $i\in [0,(p-1)-1=dq-1]$, which gives $$0\leq u+vq \leq dq-1$$ Hence we may let $v={0,1,\dots,d-1}$, giving us $d$ solutions. (Q.E.D)

Observe that $$u+(d-1)q \leq (q-1)+(d-1)q=dq-1$$ so that $v=d-1$ is a valid choice.

  • $\begingroup$ Hi take a look at my answer $\endgroup$ – reuns Oct 30 '17 at 11:26
  • $\begingroup$ @reuns I did, although I am not sure what is your intention. Is there a problem here? $\endgroup$ – Yong Hao Ng Oct 31 '17 at 2:17

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.