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.

Solution 1:

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

Solution 2:

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