0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 12 '16 at 13:45
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mkstreet Sep 12 '16 at 16:08
  • $\begingroup$ It is the multiplicative inverse: $n^{-1} n \equiv 1 \pmod {p-1}$. It exists if $\gcd(n,p-1)=1$. $\endgroup$ – gammatester Sep 13 '16 at 6:37
  • $\begingroup$ Ok, thanks. I just wanted to be sure. So many different notations floating about. $\endgroup$ – mkstreet Sep 14 '16 at 0:49
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.