I know that when gcd(a,b) = 1, a and b are relatively prime. This allows you to write the linear combination aS + bT = 1, where S and T are Bezouts's coefficients. As I understand, one of these coefficients is the inverse. Beyond that I dont understand how to find inverses. For example, gcd(101, 4620)
4620 = 45 101 + 75
101 = 1 75 + 26
75 = 2 26 + 23
26 = 1 23 + 3
23 = 7 3 + 2
3 = 1 2 + 1
2 = 2 1
1
And then after applying Euclid's Algorithm, I get the following ?
Which coefficient is the inverse ? Or is this approach wrong ?
Best Answer
Generally the extended Euclidean algorithm is easiest to perform manually as described here. Executing that algorithm yields the following
$$\begin{array}{rrr} 4620 & 1 & 0\\ 101 & 0 & 1\\ 75 & 1 & -45\\ 26 & -1 & 46\\ 23 & 3 & -137\\ 3 & -4 & 183\\ 2 & 31 & -1418\\ 1 & \color{#c00}{-35} & \color{#0a0}{1601}\end{array}$$
where each line $\,\ a\ \ b\ \ c\ \,$ means that $\ a = 4620\, b + 101\, c.\ $ Hence the final row yields
$$\quad\ \ 1 \,=\, {-}\color{#c00}{35}\cdot 4620 +\color{#0a0}{1601}\cdot 101$$
Thus the above yields $\begin{align} \rm\ mod\ 101\!:\,\ &1\,\equiv {-}35\cdot 4620\ \Rightarrow\ 1/4620\equiv -35\\ \rm\, mod\,\ 4620\!:\,\ &1\,\equiv 1601\cdot 101\ \ \Rightarrow\ 1/101\equiv 1601\end{align}$
Remark $\ $ There are various optimizations we can exploit to simplify calculations.
For example, the computation is simpler if we use "signed" remainders, i.e. least magnitude
$$\begin{array}{rrr} 4620 & 1 & 0\\ 101 & 0 & 1\\ -26 & 1 & -46\\ -3 & 4 & -183\\ 1 & -35 & 1601\\ \end{array}$$
Another optimization is that we can omit the 2nd or 3rd column since the value of $\,b\,$ or $\,c\,$ can be obtained from the others using $\, a = 4620\, b + 101\, c,\,$ e.g. $\, c = (a-4620\,b)/101\,$ allows us to recover the numbers in the 3rd column. The numbers in the 2nd column are smaller than the 3rd, so the computation is easier using only them, and we only need the final $\color{#c00}{35}\,$ in the 2nd column when computing the inverse of $4620\pmod{\!101}.\,$
Ignoring the coefficients $\,c\,$ of $101$ in the 3rd column is equivalent to working modulo $101,\,$ so the rows denote $\,a_i \equiv 4020\,b_i \pmod{\!101},\,$ i.e. $\,1/4020 \equiv b_i/a_i,\,$ and the algorithm continually reduces the denominators $\,a_i\,$ till $\,a_i\equiv 1,\,$ yielding the sought inverse. So this inversion algorithm can be viewed as a way of computing modular fractions using (Euclidean) division with remainder to reduce denominators. For more on this fractional form of the extended Euclidean algorithm see this answer, and see Gauss's algorithm for the special case when the modulus is prime.