Encuentra la inversa modular de $19\pmod{141}$

Question

Estoy haciendo una pregunta que dice que hay que encontrar la inversa de $19 \pmod {141}$ .

Hasta ahora esto es lo que tengo:

Desde $\gcd(19,141) = 1$ existe un inverso para que podamos utilizar el algoritmo euclidiano para resolverlo.

$$ 141 = 19\cdot 7 + 8 $$ $$ 19 = 8\cdot 2 + 3 $$ $$ 8 = 3\cdot 2 + 2 $$ $$ 3 = 2\cdot 1 + 1 $$ $$ 2 = 2\cdot 1 $$ El libro de texto dice que la respuesta es 52, pero no tengo ni idea de cómo han obtenido la respuesta y no estoy seguro de estar en el camino correcto. Se agradecería una explicación. Gracias.

Answer 1

Sugerencia $\, $ La aplicación de la $\rm\color{#940}{Euclidean}$ algoritmo para $\rm\color{#C00}{LHS}$ la columna produce $\rm\: \color{#0A0}{52\cdot 19}\,\equiv\, 1\pmod{141}.\:$
$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$

Ver esta respuesta para saber más sobre esto algoritmo euclidiano ampliado.

Answer 2

Estás en el camino correcto; como dice mixedmath, ahora tienes que "retroceder" tus pasos así: $$\begin{eqnarray}1\;\;\;\;&&=3-2\cdot 1\\ 1=&3-(8-3\cdot 2)\cdot 1&=3\cdot 3-8\\ 1=&(19-8\cdot 2)\cdot 3-8&=19\cdot 3-8\cdot 7\\ 1=&19\cdot 3-(141-19\cdot 7)\cdot 7&=19\cdot52-141\cdot 7\end{eqnarray}$$ Esta última ecuación, cuando se toma como módulo 141, da $1\equiv 19\cdot 52\bmod 141$ demostrando que 52 es la inversa de 19 módulo 141.

Answer 3

HINT

Se puede retroceder a través del algoritmo euclidiano para encontrar el gcd de de $19$ y $141$ como una combinación lineal de $19$ y $141$ . Es decir, puede encontrar $19x + 141 y = 1$ o posteriormente $19x \equiv 1 \mod 141$ . Entonces $x$ será su inversa.

Answer 4

Si $\phi(m)$ denota el número de primos $\leq m$ entonces $b^{-1}\pmod m = b^{\phi(m)-1}\pmod m$ .

Answer 5

Utilizando el método de Gauss y el módulo 141: 1/19 = 8/152 = 8/11 = 104/143 = 104/2 = 52

A petición de Nate Eldredge, lo explico en detalle:

Tenemos que encontrar 1/19 (mod 141). Entonces, tomamos la fracción 1/19, ahora multiplicamos 19 con un número que sea el más cercano a 141. Si multiplicamos 19 por 8, obtenemos 1/19 = 8/152. Al tomar el módulo 141, 8/152 se convierte en 8/11. Ahora, multiplica 11 por un número que se acerque a 141. Este número es el 13. Así, al multiplicar 8/11 por 13, obtenemos 104/143. Tomando el módulo 141, obtenemos 104/2 = 52.

Esto también se puede resolver de la siguiente manera: Sea x = 1/19 (mod 141). Entonces, 19x = 141y + 1. Esto se puede escribir como 19x - 1 = 141y. Ahora podemos calcular y = -1/141 (mod 19) = -1/8 = -2/16 = -2/-3 = 2/3 = 12/18 = -12 = +7.

Como y = 7, x = (141*7+1)/19 = 52. De este modo, obtenemos la misma respuesta pero utilizando un cálculo mucho más sencillo.