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?

Solution 1:

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

Solution 2:

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.

Solution 3:

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.