How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $? 
How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $?

I just asked this question, and it seems those methods are not really suitable for large numbers. Please give me some ideas. Thank you.
 A: As mentioned in comments, the Euclidean algorithm will be fastest in general for this kind of thing. But since you asked for something different, since $2011$ is prime, for $y\not\equiv0\mod2011$
$$y^{2009}\equiv y^{-1}\mod{2011}$$
So one answer to your question is $227^{2009}$. Reducing that mod $2011$ would be done most quickly by repeated squaring.
A: Fermat's Little Theorem states that

For any integer $a$, the number $a^p − a$ is an integer multiple of $p$ when $p$ is a prime.

Therefore, $a^{p - 1} \equiv 1 \text{ (mod p)}$
We have here $p = 2011$. Hence,
$a^{p-1} = 227^{p-1} = 227^{2010}$. But we already have it as $227x$. Therefore, $x = 227^{2009}$.
A: The extended Euclidean algorithm took $30$ secs by hand:
$\quad\begin{eqnarray} 
2011 =\ \ 1\cdot &2011& +\ \  \ 0\,\cdot &227&\\
227 =\ \ 0\cdot &2011& +\ \ \ 1\,\cdot &227&\\
32 = -1\cdot &2011&  + \ \ \  9\,\cdot &227&\\
 3 =\ \ 7\cdot &2011& -\ 62\cdot &227&\\
 1 = 78\cdot &2011&\! - 691\cdot &227&\\
\end{eqnarray}$
Hence $\rm\ mod\,\ 2011\!:\ {-}691\cdot 227\equiv 1$
I doubt you'll find any method more efficient than that. For large, general numbers, the extended Euclidean algorithm is almost always the most efficient method (whether by hand or machine).
A: Let's use the extended Euclidean algorithm. One way of arranging the calculation is to set up a matrix
$$ \begin{array}{cc|c} 1 & 0 & 2011 \\ 0 & 1 & 227 \end{array} \qquad \qquad (I) $$
The interpretation is that the left column is the coefficient on 2011 and the middle column is the coefficient on 227, and the right column is the number thus produced.
But 4 digit numbers are big! I'm lazy so I'll just look at the top 2 digits:
$$ \begin{array}{cc|c} 1 & 0 & 20 \\ 0 & 1 & 2 \end{array} $$
Ah, I can do the extended Euclidean algorithm on that. In fact, it's so easy I can do it in my head:
$$ \begin{array}{cc|c} 1 & -10 & 0 \\ 0 & 1 & 2 \end{array} $$
Now I know how to reduce the top digits, I'll take the original array and multiply it by the matrix $\left(\begin{matrix}1 & -10 \\ 0 & 1\end{matrix}\right)$, to get
$$ \begin{array}{cc|c} 1 & -10 & -259 \\ 0 & 1 & 227 \end{array} \qquad \qquad(II) $$
I'm lazy, I'll work on just the top 2 digits again
$$ \begin{array}{cc|c} 1 & 0 & -25 \\ 0 & 1 & 22 \end{array} $$
$$ \begin{array}{cc|c} 1 & 1 & -3 \\ 0 & 1 & 22 \end{array} $$
$$ \begin{array}{cc|c} 1 & 1 & -3 \\ 7 & 8 & 1 \end{array} $$
$$ \begin{array}{cc|c} 22 & 25 & 0 \\ 7 & 8 & 1 \end{array} $$
Now I'll multiply so now if I multiply (II) by the matrix $\left(\begin{matrix}22 & 25 \\ 7 & 8\end{matrix}\right)$, I'll get
$$ \begin{array}{cc|c} 22 & -195 & -23 \\ 7 & -62 & 3\end{array} \qquad \qquad(III) $$
Okay this isn't too bad. But I'm still lazy again:
$$ \begin{array}{cc|c} 1 & 0 & -23 \\ 0 & 1 & 3 \end{array} $$
$$ \begin{array}{cc|c} 1 & 8 & 1 \\ 0 & 1 & 3 \end{array} $$
$$ \begin{array}{cc|c} 1 & 8 & 1 \\ -3 & -23 & 0 \end{array} $$
I just want the top row, so I'll multiply (III) on the left by $(1\ 8)$:
$$ \begin{array}{cc|c} 78 & -691 & 1\end{array} \qquad \qquad(IV) $$
and now I know
$$ 78 \cdot 2011 - 691 \cdot 227 = 1$$
in particular,
$$ 227 \cdot (-691) = 1 \pmod{2011}$$
I could have saved myself some trouble by only using the second and third columns of (I), (II), (III), (IV) since I don't really care about 78. 
Computers use this idea to do very large gcd's; either Lehmer's GCD algorithm or the half-GCD algorithm depending on how much of an extreme you take the idea.
