2
$\begingroup$

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 ? enter image description here

Which coefficient is the inverse ? Or is this approach wrong ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I dont really have a problem with finding the coefficients...i dont know which of the coefficients is the inverse ? $\endgroup$ – Gdgames Gamers Dec 22 '13 at 0:16
  • $\begingroup$ @Gda See the final line. I highly recommend you use the linked method instead of the back-substitution method, since the latter is highly error prone. $\endgroup$ – Bill Dubuque Dec 22 '13 at 0:28
  • $\begingroup$ So the inverse can be found for both or just the smaller number ? $\endgroup$ – Gdgames Gamers Dec 22 '13 at 0:41
  • $\begingroup$ Yes, the final Bezout equation can be used either way, as I said above. Reducing it modulo one of the numbers in one summand yields the inverses of the numbers multiplied in the other summand. $\endgroup$ – Bill Dubuque Dec 22 '13 at 0:47
0
$\begingroup$

To find the inverse you need Extended Euclide algorithm.

$\endgroup$
  • $\begingroup$ Can you check if I applied it correctly ? $\endgroup$ – Gdgames Gamers Dec 21 '13 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.