Reglas del álgebra para hallar el módulo inverso

Question

La idea es encontrar un módulo inverso para dos números, $660$ y $43$ en este caso. Me parece que el GCD es fácil de calcular, pero el paso después de eso, el cálculo del módulo inverso cuando se calcula de nuevo a través del cálculo GCD. Lo que no entiendo, es que 'por álgebra' siguen quitando ciertos números entre paréntesis, y me parece ilógico.

$\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}$

Ahora, estos son los pasos 1 a 5, y para el paso 6 (para calcular la inversa), dan esto:

$\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}$

Lo que no entiendo, por ejemplo, es cómo acaban con 20 en el paso 5. ¿Cuáles son exactamente las reglas a la hora de simplificar estos pasos? Parece como si estuvieran simplemente reemplazando cualquier número a su gusto .. Tengo esto para mi curso de matemáticas discretas, y no he tenido clases de álgebra básica antes de esto, por lo que podría ser muy fácil. ¡Toda ayuda es apreciada!

Editar: tal vez no hay pregunta real por encima, mi pregunta por lo tanto: ¿cuáles son las reglas para esto? ¿Pueden estos enteros dentro de los paréntesis sólo se barajan alrededor?

Answer 1

Me gusta describir el proceso de la siguiente manera:

Para hallar el DGC de dos números, empieza escribiendo una tabla en la que la primera fila sea el primer número que nos interesa, seguido de un 1 seguido de un 0. La segunda fila será el segundo número que nos interesa, seguido de un 0 seguido de un 1.

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

Continúe construyendo la tabla restando el mayor múltiplo de la fila más reciente de la anterior que aún dé como resultado un número no negativo para la primera entrada. En este caso $15$ . Tenemos $[660,1,0]-15[43,0,1] = [15,1,-15]$ así que nuestra mesa continúa como:

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

De nuevo, miramos cuántas copias de la última fila pueden caber en la anterior, en este caso dos veces: $[43,0,1]-2[15,1,-15]=[13,-2,31]$ así continúa

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

Este proceso continúa hasta que finalmente se llega a un cero para la primera entrada de una fila. El DGC es la primera entrada de la fila anterior. Observa también que estas columnas tienen significado. De la forma en que lo establecí, al encontrar $\gcd(A,B)$ el número de la izquierda de una fila es igual al número del medio multiplicado por $A$ más el número correcto de veces $B$ . En este ejemplo, $13 = -2\cdot 660 + 31\cdot 43$

Completar la tabla:

$$\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}$$

Esto implica que $1=-20\cdot 660 + 307\cdot 43$ que $\gcd(660,43)=1$ y que $660^{-1}\equiv -20\pmod{43}$

Answer 2

Estaba buscando una de mis otras respuestas sobre el algoritmo euclidiano ampliado para enlazarte, pero como no he encontrado ninguna, aquí tienes una tabla para tu pregunta:

$$\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}$$

Cada conjunto de $n,s,t$ (después de las dos primeras líneas de configuración) es generado por la función $q$ (el cociente entero de los anteriores $n$ sobre la corriente) de la última línea. Por lo tanto, subíndice para el número de fila de la tabla:
$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.

La última columna es sólo para mostrar cómo el $s$ y $t$ pueden interpretarse como coeficientes de esa ecuación para cada fila.

El último $n$ da el GCD, como era de esperar, pero también esta tabla ampliada da la ecuación para conseguirlo, La identidad de Bézout .
$-20\cdot 660 + 307\cdot 43 =1$

Esto se puede utilizar para obtener la inversa modular en ambas direcciones:
$307\cdot 43 \equiv 1\bmod 660\\ -20\cdot 660 \equiv 1 \bmod 43$

(y por supuesto $-20\equiv 23\bmod 43$ )