How to identify an inverse of 101 modulo 4620 I use Euclidean Algorithm:
4620 = 101 * 45 + 75. long story short. I get 3 = 2 * 1 + 1. After that 2 = 1 * 2 + 0.
gcd(101,4620) = 1.
So I use back substitution.
1 = 3 - 1 * 2. Long story short, I work my way up to express the remainders as the remaining terms of the equation arriving to - 35* 4620 + 1601 * 101. How do I test which one is the inverse based on -35 * 4620 + 1601 * 101?
I tried 1601 but 1601 = 101 (modulo 4620) does not seems right because 4620 does not divide 1601 -101 or 1500. 
 A: I think you're confused as to what an inverse is.  First, we take your equation
$$-35(4620)+1601(101)=1$$
and now look at this mod $4620$
$$1601(101)\equiv1\pmod{4620}$$
By this equation, $1601$ and $101$ are inverses of one another mod $4620$.  When we multiply one by the other, the result is equivalent to $1$.
A: Hint $\ $ modular reducing Bezout identity  $\ a\,b + c\,m = 1\,\Rightarrow\, {\rm mod}\ m\!:\ ab\equiv 1\,\Rightarrow\, a\equiv b^{-1}$
Remark $\ $ The "$\rm\color{#c00}{back}$-substitution method" for the extended gcd is notoriously error-prone. Simpler to compute and easier to remember is the $\rm\color{#c00}{forward}$ method described at length here. Executing that algorithm, optimized using least magnitude (vs. least positive) remainders, yields
$$\begin{array}{rrr}
4620 &  1 &    0\\
101 &  0 &  1\\
 -26 &  1 & -46\\
  -3 & 4&   -183\\
  \color{#c00}1 & \!\!\color{#0a0}{-35} & \!\!\!\color{#90f}{1601}\end{array}\qquad\quad$$
where each line $\,\ a\ \ b\ \ c\ \,$ means that $\ a = 4620\, b + 101\, c.\ $ Therefore
$$ \begin{eqnarray} \color{#0a0}{-35}\cdot\, &4620& +\, \color{#90f}{1601}\cdot 101 = \color{#c00}1\\[.2em] 
\Rightarrow\ \  {\rm mod}\ \ & 4620&\!:\ \ 1601\cdot 101\equiv 1\end{eqnarray}\ \ \ $$
The linked post described the algorithm in great detail, in a way that is easy to remember.
Remark $ $ Note that using least magnitude residues has halved the number of steps compared to using the traditional least nonnegative residues (here $\,3\,$ steps vs. $\,6\,$ steps in robjohn's answer).
A: Using the Euclid-Wallis Implementation of the Exrended Euclidean Algorithm
$$
\begin{array}{r}
&&45&1&2&1&7&1&2\\\hline
1&0&1&-1&3&-4&31&-35&101\\
0&1&-45&46&-137&183&-1418&1601&-4620\\
4620&101&75&26&23&3&2&1&0
\end{array}
$$
we get that $1601\cdot101-35\cdot4620=1$. Therefore,
$$
1601\times101\equiv1\pmod{4620}
$$
