How can I calculate the $n$-th root of a number modulo $m$? I have to calculate the $n$-th root of a number $x$ modulo $m$:
$$\sqrt[n]{x} =  a\quad \mod(m),$$ 
where $x$, $n$ as well as $m$ are known. The only unknown number is $a$.
It would already help me a lot, if I could convert it to a type of problem like
$$x^y = a \quad \mod(m)$$
where $x$, $y$ and $m$ are known.
 A: If $\gcd(a, m) = 1$, then by Euler's theorem we have, for any natural number $i$, that
$$
a^{i\phi(m) + 1} \equiv a \pmod m
$$
where $\phi(m)$ is the Euler totient of $m$. That means that if $a^n \equiv x$, then we are looking for some $i$ that makes $i\phi(m) + 1$ a multiple of $n$. In other words, we are looking for $i, j$ such that $jn =  i\phi(m) + 1$. Because if we find such a number, then $x^j = (a^n)^j = a^{nj} = a^{i\phi(m) + 1}\equiv a$. So taking the $n$-th root is the same as raising to the $j$-th power.
How do we find such a number $j$? We need $\phi(m)$, first and foremost. (Which is very hard work to do unless $m$ is relatively small, or you know the prime decomposition of $m$. This is the main source of security behind, for instance, the RSA algorithm. They supply $m$ and $n$ to anyone who wants to encrypt, which you do by raising your card number, say, to the $n$-th power modulo $m$, and then they keep $\phi(m)$ very secret so that they are the only ones who can calculate $j$.)
We need that $n$ to be such that $\gcd(n, \phi(m)) = 1$, because otherwise there are no $i, j$ such that $jn - i\phi(m) = 1$. Then we need to find $i$ and $j$ (technically we only need $j$, but they come in a pair). Once you've done that, you can take the $n$-th root of any $x$ you want, provided $\gcd(x, m) = 1$, by calculating $x^j$.
