Find $x$ for $x^{701} \equiv 3 \pmod {139}$ using Fermat's Little Theorem.
I believe the answer is $x = 88$.
Since 139 is prime, I use: $a^{p - 1} \equiv 1 \pmod p$
$$701 = 5 \times 138 + 11$$
$$\begin{align}(x^{138})^5 \times x^{11} &\equiv 3 \pmod {139}\\ (1)^5 \times x^{11} &\equiv 3 \pmod {139}\\ x^{11} &\equiv 3 \pmod {139}\end{align}$$
At this step, I don't know what to do next. If the mod value was small, I could make a table and exhaustively try the values. But with mod 139, there must be a better way?
I have similar questions to this, so I need to understand the process.
Thanks!
To solve $x^n = a\pmod p$ if $u \equiv n^{-1} \pmod {p-1}$ exists, it follows from Euler's theorem that $x = a^u \pmod p$. In your case you get $$u \equiv n^{-1} \equiv 701^{-1} \equiv 113 \pmod {138}$$ $$x \equiv 3^{113} \equiv 88 \pmod {139}$$
Check: $88^{701}\equiv 3 \pmod {139}$
For your reduced calculation $x^{11}\equiv 3\pmod {139}$ you would get the same $u$ $$u \equiv 11^{-1} \equiv 113 \pmod {138}$$ and as a consequence the same $x$.
Some details about the first claim: If $u \equiv n^{-1} \pmod {p-1}$ you have $nu = 1 + k(p-1)=1+k\varphi(p)$ and therefore $$x^n\equiv a^{nu}\equiv a^{1+k\varphi(p)} \equiv a \times (a^{\varphi(p)})^k\equiv a \pmod p$$