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