Number of $k$th Roots modulo a prime? 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. 
 A: 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.
A: 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$
