How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$?

How can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$?

Our method for solving something like $x^k \equiv b\pmod m$ is first to find the integers $u$ and $v$ satisfying $ku - \phi (m)v = 1$, and then the solution is $x\equiv b^u \pmod m$. However, we only showed that this works provided that $\gcd(b,m) = 1$, since we used Euler's formula $b^{\phi(m)} \equiv 1\pmod m$.

If $m$ is a product of distinct primes, how can I show that $x \equiv b^{u} \pmod m$ is always a solution to $x^{k} \equiv \pmod m$, even if $\gcd(b,m) \gt 1$ ?

Also, why doesn't this method work for the congruence $x^5 \equiv 6 \pmod 9$ ?

• Anyone understand? – user274933 Oct 2 '15 at 16:06
• Clearly you can't prove something for which you already have a counterexample. – lhf Oct 2 '15 at 16:13
• No the method I am asking about works. There is a reason that the example is different – user274933 Oct 2 '15 at 16:16
• The method does not work for $x^5 \equiv 6 \bmod 9$ because $5\cdot 5 \equiv \bmod 6 = \phi(9)$ but $6 ^5 \equiv 0 \not\equiv 6 \bmod 9$. The reason of course is that Euler's theorem does not apply in this case. – lhf Oct 2 '15 at 16:19
• Thank you. Now I just need to show that $x≡b^{u}(mod m)$ is a solution to $x^{k}≡(mod m)$ .. – user274933 Oct 2 '15 at 16:22