Algebra rules when finding inverse modulo

Question

The idea is to find an inverse modulo for two numbers, $660$ and $43$ in this case. I find that the GCD is easy to calculate, but the step after that, calculating the inverse modulo when calculating back trough the GCD calculation. The thing I do not get, is that 'by algebra' they keep removing certain numbers between parentheses, and it seems illogical to me.

$\begin{array}{rcl}660 & = & 43 \cdot 15 + 15 \\ 43 & = & 15 \cdot 2 + 13 \\ 15 & = & 13 \cdot 1 + 2 \\ 13 & = & 2 \cdot 6 + 1 \\ 2 & = & 1 \cdot 2 + 0 \end{array}$

Now, these are steps 1 trough 5, and for step 6 (to calculate the inverse), they give this:

$\begin{array}{rcl} (1) & = & 13 - 2 \cdot 6 \\ (2) & = & 13 - (15 - 13) \cdot 6 \\ (3) & = & 7 \cdot 13 - 6 \cdot 5 \\ (4) & = & 7 \cdot (43 - 15 \cdot 2) - 6 \cdot 15 \\ (5) & = & 7 \cdot 43 - 20 \cdot 15 \\ (6) & = & 7 \cdot 43 − 20 \cdot (660 − 43 \cdot 15) \\ (7) & = & 307 \cdot 43 - 20 \cdot 660 \end{array}$

The thing I do not get, for example, is how they end up with 20 at step 5. What exactly are the rules here when simplifying these steps? It seems like they are just replacing any numbers to their liking .. I have this for my discrete math course, and have not had basic algebra lessons before this, so it could be really easy. All help is appreciated!

Edit: perhaps there is no real question above, my question thus: what are the rules for this? Can these integers within the parentheses just be shuffled around?

Answer 1

The way I like to describe the process is this:

When finding the GCD of two numbers, begin writing a table where the first row is the first number we are interested in, followed by a 1 followed by a 0. The second row will be the second number we are interested in, followed by a 0 followed by a 1.

$$\begin{array}{c|c|c}660&1&0\\43&0&1\end{array}$$

Continue building the table by subtracting the largest multiple of the most recent row from the one before it that still results in a non-negative number for the first entry. In this case $15$. We have $[660,1,0]-15[43,0,1] = [15,1,-15]$ so our table continues as:

$$\begin{array}{c|c|c}660&1&0\\43&0&1\\15&1&-15\end{array}$$

Again, we look at how many copies of the last row can fit into the one previous, in this case twice: $[43,0,1]-2[15,1,-15]=[13,-2,31]$ so it continues

$$\begin{array}{c|c|c}660&1&0\\43&0&1\\15&1&-15\\13&-2&31\end{array}$$

This process continues until you eventually arrive at a zero for the first entry of a row. The GCD is the first entry in the row previous. Note also that these columns have significance. The way I set it up, in finding $\gcd(A,B)$ the number on the left of a row is equal to the middle number times $A$ plus the right number times $B$. In this example, $13 = -2\cdot 660 + 31\cdot 43$

Completing the table:

$$\begin{array}{c|c|c}660&1&0\\43&0&1\\15&1&-15\\13&-2&31\\ 2&3&-46\\1&-20&307\\0\end{array}$$

This implies that $1=-20\cdot 660 + 307\cdot 43$, that $\gcd(660,43)=1$, and that $660^{-1}\equiv -20\pmod{43}$

Answer 2

I was looking for one of my other answers on the extended Euclidean algorithm to link you to, but since I couldn't find one, here's a table for your question:

$$\begin{array}{|c|c|} \hline n & s & t & q & \text{equation; }n=\\ \hline 660 & 1 & 0 & & 1\cdot 660 + 0\cdot 43\\ \hline 43 & 0 & 1 & 15 & 0\cdot 660 + 1\cdot 43\\ \hline 15 & 1 & -15 & 2 & 1\cdot 660 -15\cdot 43\\ \hline 13 & -2 & 31 & 1 & -2\cdot 660 + 31\cdot 43\\ \hline 2 & 3 & -46 & 6 & 3\cdot 660 - 46\cdot 43\\ \hline 1 & -20 & 307 & 2 & -20\cdot 660 + 307\cdot 43\\ \hline \end{array}$$

Each set of $n,s,t$ (after the first two setup lines) is generated by the $q$ (the integer quotient of the previous $n$ over the current) of the last line. So subscripting for table row number:
$q_2 = \left\lfloor \frac{\large n_1}{\large n_2} \right\rfloor = \left\lfloor \frac{\large 660}{\large 43} \right\rfloor = 15 \\ n_3 = n_1-15\cdot n_2 = 660 - 15\cdot 43 = 15 \\ s_3 = s_1-15\cdot s_2 = 1-0 = 1 \\ t_3 = t_1-15\cdot t_2 = 0-15 = -15 \\ q_3 = \left\lfloor \frac{\large n_2}{\large n_3} \right\rfloor = \left\lfloor \frac{\large 43}{\large 15} \right\rfloor = 2 \\ n_4 = n_2 - 2\cdot n_3 = 43 - 2\cdot 15 = 13 \\ s_4 = s_2 - 2\cdot s_3 = 0 - 2\cdot 1 = -2 \\ t_4 = t_2 - 2\cdot t_3 = 1 - 2\cdot (-15) = 31 \\ $
etc.

The final column there is just to show how the $s$ and $t$ can be interpreted as coefficients in that equation for each row.

The last $n$ gives the GCD, as expected, but also this extended table gives the equation to achieve that, Bézout's identity.
$-20\cdot 660 + 307\cdot 43 =1$

This can be used to get the modular inverse in both directions:
$307\cdot 43 \equiv 1\bmod 660\\ -20\cdot 660 \equiv 1 \bmod 43$

(and of course $-20\equiv 23\bmod 43$)