Computing the inverse a^-1 mod n using Euler or Fermats Theorem

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?

• $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. – Jean-Claude Arbaut Nov 11 '15 at 23:50
• $(6)(2)=12\equiv (-1)\pmod {13}\implies (6)(11)\equiv (6)(-2)\equiv 1 \pmod {13}.$ – DanielWainfleet Nov 12 '15 at 0:29

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