Number of $k$th Roots modulo a prime?

Question

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.

Answer 1

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$

Answer 2

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.