<s>[INST] 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? 
 [/INST] 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$.
</s>