# Find unknown base value with large exponent and Fermat's Little Theorem

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!

• For $139$, you can make a table in a spreadsheet easily to try them all. Make a column with the numbers $0$ to $138$, then =mod(a1^11,139) and copy down. This is even reasonable for a few thousand, though you might have to spread over several columns. Yes, $88$ is correct. – Ross Millikan Sep 12 '16 at 13:45

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$$

• This seems good but I don't understand the notation $n^{-1}$. What does this (-1) mean? Also, I've looked in my book for Euler's Theorem and the only thing mentioned is the $\Phi()$ function. – mkstreet Sep 12 '16 at 16:08
• It is the multiplicative inverse: $n^{-1} n \equiv 1 \pmod {p-1}$. It exists if $\gcd(n,p-1)=1$. – gammatester Sep 13 '16 at 6:37
• Ok, thanks. I just wanted to be sure. So many different notations floating about. – mkstreet Sep 14 '16 at 0:49

The only way I can see is heavy calculation. You do have $$88^{11}=17\space 631\space 716\space466\space782\space292\space631\cdot 139+3$$ which say that $x=\color{red}{88}$