Let $x = a^e \mod p$, where...
- $p$ is a prime number
- $e$ is an integer and $e < p$
- $a$ is any integer
If the values of $(p, e, x)$ are given, can $a$ be determined?
I am approaching this problem using Fermat's Little Theorem, which states that $\forall a \in \{0, 1, ..., p-1\}$, $a^{p-1} \equiv 1 \mod p$
I try to argue that $a \cdot a^{k(p-1)} \equiv a \mod p$, because $a^{k(p-1)} \mod p$ appears to always be equivalent to $1$ (although I do not have a good justification for this, only experimental data). Then it can be said that $$(a \mod p) \cdot (a^{k(p-1)} \mod p) \equiv (a \mod p) \cdot 1 \equiv a \mod p$$
I then argue that using the numbers we are given, we can say that $x^{p-1} \equiv a^{{(p-1)}^e} \equiv 1 \mod p$, but I don't see how to get back to $a$.
From Fermat's little theorem, if $u\equiv v\bmod p-1$, then $x^u\equiv x^v\bmod p$. This is because if we write $u=v+k(p-1)$ then we can calculate
$$x^u\equiv x^{v+k(p-1)}\equiv x^v (x^k)^{p-1}\equiv x^v \cdot 1\equiv x^v\bmod p.$$
Therefore, if we can compute $e$'s modular inverse $e^{-1}\bmod p-1$ using the extended Euclidean algorithm, then we can then compute
$$ x^{e^{-1}}\equiv (a^e)^{e^{-1}}\equiv a^{ee^{-1}}\equiv a^1\equiv a\mod p $$
because $ee^{-1}\equiv 1$ mod $p-1$.