| | |
Assuming that $\gcd(b,n)=\gcd(k,\phi(n))=1$, we can take advantage of the trick used in RSA encryption to find a value $x$ that solves the congruence $$x^k \equiv b \pmod{n}$$ Similar to what we did to find $M$ given $M^e\pmod{n}$, find $u \equiv k^{-1}\pmod{\phi(n)}$. This inverse $u$ exists of course, given that we know $\textrm{gcd}(k,\phi(n))=1$. Thus, $ku\equiv 1\pmod{\phi(n)}$. Equivalently, $ku = y\phi(n) + 1$ for some integer $y$.
But then, if $x=b^u$ we can appeal to Euler's Theorem (since $\textrm{gcd}(b,n)=1$) in a similar way to what was seen in RSA encryption to discover $$x^k \equiv (b^u)^k \equiv b^{ku} \equiv b^{y\phi(n) + 1} \equiv (b^{\phi(n)})^y \cdot b \equiv 1^y \cdot b \equiv b$$ So, $x=b^u$ is a $k^{th}$ root of $b$.