Uniqueness of $k$th root mod $m$ if $(k, \phi(m)) = 1$. I'm trying to prove a fact about $k$th roots that says that if $(k, \phi(m)) = 1$ and $(b,m) = 1$, then there is a unique $k$th root modulo $m$ (composite $m$). 
I'm not sure how to go about it but here's an attempt;
Suppose towards a contradiction that there are two solutions $x_1 = b^r$ and $x_2 = b^s$ to the congruence $x^k \equiv b \bmod m$. Then $$x_1^k \equiv x_2^k \equiv b \bmod m$$
so that $b^{kr} \equiv b^{ks} \equiv b \bmod m$, or equivalently, $b^{kr - 1} \equiv b^{ks - 1} \bmod m$. We can then conclude that $m \mid b^{kr - 1} - b^{ks - 1}$. Now we can factor to obtain $b^{kr - 1} - b^{ks - 1} = b^{kr - 1}(b^{k(s-r)} - 1)$ to conclude that $m \mid b^{kr - 1}(b^{k(s-r)} - 1)$. But since $(b, m) = 1$, we must have $m\mid b^{k(s-r)} - 1$, or equivalently, 
$$b^{k(s-r)} \equiv 1 \bmod m$$
which would imply $k(s-r) = \phi(m)v$ for some $v \in \mathbb Z$.
I feel like there could be a way to extract a contradiction from this last step but I can't see it, would somebody be able to check if this is a good way to go?
 A: Here is a simpler approach:
Since $(k, \phi(m)) = 1$, write $uk + v \phi(m)=1$ for $u,v \in \mathbb Z$.
Then, if $(x,m)=1$ we have $x=x^1=x^{uk + v \phi(m)}={(x^u)}^k (x^{\phi(m)})^v \equiv {(x^u)}^k \bmod m$.
This proves that the map $x \mapsto x^k$ is surjective and so is a bijection.
In other words, every $x$ with $(x,m)=1$ has a unique $k$-th root mod $m$.
A: To (uniquely) solve $\ x^{\large k} \equiv b\ $ take a $k$'th root (i.e. raise both sides to power $1/k)$,  just as for reals.
Let $\phi = \phi(m).\, $ $\,(k,\phi) = 1\,\Rightarrow\, j := 1/k\pmod{\!\phi}\,$ exists, so raising to power $\,j\,$ yields
$$\begin{align} &\left[x_1^{\large k} \equiv b\equiv x_2^{\large k}\right]^{\large j}\\
\Rightarrow\ &\ \  x_1 \equiv b^{\large j}\!\equiv x_2\end{align}$$
This works because by Euler all exponents can be taken mod $\phi$ (on all  $\,a\,$ coprime to $m),\,$ i.e. $\!\bmod m\!:\ \color{#c00}{a^{\large \phi}\equiv 1}\,\Rightarrow\, a^{\large r+q\,\phi}\equiv a^{\large r}(\color{#c00}{a^{\large \phi}})^{\large q}\equiv a^{\large r}\color{#c00}1^{\large q}\equiv a^{\large r},\ $ i.e. $\,a^{\large n}\!\equiv a^{\large n\bmod\phi},\,$ hence
$$ (x^{\large k})^{\large j}\! \equiv x^{\large kj}\!\equiv x^{\large kj\bmod\phi}\!\equiv x^{\large k(1/k)\bmod \phi}\!\equiv x^{\large 1}$$  Thus the solution amounts to raising $\,x^{\large k}\,$ to power $\,1/k\,$ (i.e. taking its $k$'th root) to solve for $\,x.$
Note: it is valid to apply Euler $\phi\,$ to powers of $x$ since $\,(x,m) = 1,\,$ by $\,1=(b,m)=(x^k,m)$
See this answer for elaboration and a fully worked example.
A: There is $l$ with $kl\equiv 1\pmod{\phi(m)}$. Note that for all $a$
coprime to $m$, then $r\equiv s\pmod{\phi(m)}$ implies $a^r\equiv a^s\pmod m$.
Then $$b\equiv a^k\pmod{m}\iff a\equiv b^l\pmod{m}.$$
One way: $b\equiv a^k\pmod{m}\implies b^l\equiv a^{kl}\pmod m$.
As $a^{kl}\equiv a\pmod{m}$ (why?) that does it.
Other way: similar.
