0
$\begingroup$

I'm trying to compute the inverse $a^{-1} \mod n$ with Fermat's Theorem (if applicable) or Euler's Theorem:

$a$ = 6, $n$ = 13

I know that since n is prime, we can use Fermat's Theorem to compute the inverse, using the following formula:

$a^{-1} = a^{p-2} \mod p$

So in our case, $p$ = 13.

So here's what I got, but it's obviously incorrect.

$6^{13-2} \mod 13 =$ $6^{11} \mod 13 =$ $362797056 \mod 13$

Can someone please explain where I went wrong?

$\endgroup$
  • 2
    $\begingroup$ $6^{11} \equiv 11 \pmod{13}$, and $11\times 6 \equiv 1 \pmod{13}$. What's the problem? Of course, it's perfeclty acceptable to say that $362797056$ is also an inverse of $6$ mod $13$, but usually you reduce the result. $\endgroup$ – Jean-Claude Arbaut Nov 11 '15 at 23:50
  • $\begingroup$ $(6)(2)=12\equiv (-1)\pmod {13}\implies (6)(11)\equiv (6)(-2)\equiv 1 \pmod {13}.$ $\endgroup$ – DanielWainfleet Nov 12 '15 at 0:29
1
$\begingroup$

The remainder on dividing $362797056$ by $13$ is $11$. Showing this work in more detail and organizing it a little differently, and indicating the details of the reductions $\mathrm{mod} \ 13$...

$$\begin{align} 6 &\cong 6 \mod 13 \\ 6^2 &\cong 36 \cong_{{}-2\cdot 13} 10 \mod 13 \\ 6^3 &\cong 6 \cdot 6^2 \cong 6 \cdot 10 \cong 60 \cong_{{}-4 \cdot 13} 8 \mod 13 \\ 6^9 &\cong (6^3)^3 \cong (8)^3 \cong 64 \cdot 8 \cong_{64 \rightarrow 64 - 4\cdot 13} 12 \cdot 8 \cong 96 \cong_{{}-7\cdot 13} 5 \mod 13 \\ 6^{11} &\cong 6^9 \cdot 6^2 \cong 5 \cdot 10 \cong 50 \cong_{{}-3\cdot 13} 11 \mod 13 \end{align}$$

Then $a \cdot 11 \cong 6 \cdot 11 \cong 66 \cong_{{}-5\cdot 13} 1 \mod 13$.

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