Modular Exponentiation with unknown base

Question

Consider $x^a\equiv1 \pmod n$.

Is there a general way to solve for $x$, given $a$ and $n$?

Would knowing the factorization of $n$ make it easier?

Answer 1

If $n=p_1^{e_1}\cdots p_r^{e_r}$ is the factorization of $n$ into prime powers, then you can solve simultaneously (by the Chinese remainder theorem) $$x^a\equiv 1\mod p_i^{e_i},\quad 1\leq i\leq r,$$ and then assemble the solutions together. This solution is unique in the range of $0$ to $n-1$.

In particular, if $e_i=1$, then you can use Fermat's little theorem, $x^{p_i-1}\equiv 1\mod p_i$ to simplify the associated congruence.