Finding the $k^{th}$ root modulo m We know that method of finding $k^{th}$ root modulo $m$, i.e. if $$x^k\equiv b\pmod m,\tag {$\clubsuit$}$$ with $\gcd (b,m)=1$, and $\gcd(k,\varphi(m))=1$, then $x\equiv b^u\pmod m$ is a solution to $(\clubsuit)$, where $ku-v\varphi(m)=1$.  Because
$$\begin{array}
{}x^k &\equiv \left(b^u\right)^k\pmod m\\
&\equiv b^{uk}\pmod m\\
&\equiv b^{1+v\varphi (m)}\pmod m\\
&\equiv b\cdot b^{v\varphi(m)}\pmod m\\
&\equiv b\cdot \left(b^{\varphi (m)}\right)^v\pmod m\\
&\equiv b\pmod m
\end{array}$$
Thus $x\equiv b^u\pmod m$ is a solution to $(\clubsuit)$.
Here we use $\gcd(b,m)=1$, since we used Euler's theorem that $b^{\varphi(m)}\equiv1\pmod m$.

But I am asked to prove that if $m$ is the product of distinct primes, then $x\equiv b^u \pmod m$ is always a solution, even if $\gcd (b,m)\gt1.$

What I did, is say $m=p_1p_2$. Then $\varphi(m)=(p_1-1)(p_2-1)$
$$\begin{array}
{}b^{uk}&\equiv b\cdot b^{\varphi (m)}\pmod m\\
&\equiv b\cdot b^{(p_1-1)(p_2-1)}\pmod m
\end{array}$$
Now, we just have to compute $b^{(p_1-1)(p_2-1)}\pmod {p_i}$. Here I got stuck, because I really can't use the little theorem for every $p_i$'s, since some $p_i$ can exist in $b$.
Can someone help me?
 A: In your case of $m=p_1p_2$. If $\gcd(b,m)>1$, then $\gcd(b,m) \in \{p_1,p_2,m\}$. Without the loss of generality, say $\gcd(b,m)=p_1$. Then 
\begin{align*}
b^{ku} & \equiv b \, . b^{(p_1-1)(p_2-1)}\\
& \equiv 0 \pmod{p_1} & (\because \gcd(b,m)=\gcd(b,p_1)=p_1)\\
&  \equiv b \pmod{p_1}
\end{align*}
Likewise
\begin{align*}
b^{ku} & \equiv b \, . b^{(p_1-1)(p_2-1)}\\
& \equiv b .1 \pmod{p_2} & (\because \gcd(b,p_2)=1 \text{ so Fermat's little theorem works})\\
&  \equiv b \pmod{p_2}
\end{align*}
Thus
$$b^{ku} \equiv b \pmod{p_1p_2}$$
A: $b^{\large ku}\!\equiv b\pmod{\!pq}\,$ is case $\,i,j,k=1\,$ of this generalization of the Fermat Euler $\color{blue}{\rm (E)}$ theorem.
${\bf Theorem}\,\ \   n^{\large k+\phi}\equiv n^{\large k}\pmod{\!p^i q^j}\ \ $ if $\,p\ne q\,$ are prime, $ \ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\, $  $\, i,j \le k\ \ \ $ 
${\bf Proof}\,\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^{\large i}\!:\  n^{\large  \phi}\!\equiv 1\,\Rightarrow\, n^{\large k + \phi}\equiv n^{\large k},\ $ by $\,\  n^{\large \color{#0a0}\phi} = (n^{\color{#0a0}{\large \phi(p^{\Large i})}})^{\large \color{#0a0}\ell}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large \ell}\equiv 1$ 
$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^{\large i}\!:\  n^{\large k}\!\equiv 0\,\equiv\, n^{\large k + \phi}\ $ by $\ n^{\large k} = n^{\large k-i} \color{#c00}n^{\large i} = n^{\large k-i} (\color{#c00}{mp})^{\large i}$ and $\,k\ge i$
So $\ p^{\large i}\mid n^{\large k+\phi}\!-n^{\large k}.\,$ By symmetry $\,q^{\large j}$ divides it too, thus so too does their lcm $ = p^{\large i} q^{\large j}\,\ $ QED
Remark $\ $ The above  proof immediately extends to an arbitrary number of primes, see this answer.  See also Carmichael's Lambda function, a generalization of Euler's phi function.
