Cómo encontrar la inversa del módulo $m$ ?

Question

Por ejemplo: $$7x \equiv 1 \pmod{31} $$ En este ejemplo, la inversa modular de $7$ con respecto a $31$ es $9$ . ¿Cómo podemos saber que $9$ ? ¿Cuáles son los pasos que debo seguir?

Actualización
Si tengo una ecuación general de módulo:
$$5x + 1 \equiv 2 \pmod{6}$$

¿Cuál es la forma más rápida de resolverlo? Mi pensamiento inicial fue: $$5x + 1 \equiv 2 \pmod{6}$$ $$\Leftrightarrow 5x + 1 - 1\equiv 2 - 1 \pmod{6}$$ $$\Leftrightarrow 5x \equiv 1 \pmod{6}$$

A continuación, resuelva la inversa de $5$ módulo 6. ¿Es un enfoque correcto?

Gracias.

Answer 1

1. Un método es simplemente el algoritmo euclidiano: \begin{align*} 31 &= 4(7) + 3\\\ 7 &= 2(3) + 1. \end{align*} Así que $ 1 = 7 - 2(3) = 7 - 2(31 - 4(7)) = 9(7) - 2(31)$ . Viendo la ecuación $1 = 9(7) -2(31)$ modulo $31$ da $ 1 \equiv 9(7)\pmod{31}$ por lo que la inversa multiplicativa de $7$ modulo $31$ es $9$ . Esto funciona en cualquier situación en la que se quiera encontrar la inversa multiplicativa de $a$ modulo $m$ Siempre y cuando, por supuesto, exista tal cosa (es decir, $\gcd(a,m) = 1$ ). El Algoritmo Euclidiano le da una forma constructiva de encontrar $r$ y $s$ tal que $ar+ms = \gcd(a,m)$ pero si consigues encontrar $r$ y $s$ alguna otra forma, eso también lo hará. En cuanto tenga $ar+ms=1$ , lo que significa que $r$ es la inversa modular de $a$ modulo $m$ ya que la ecuación da como resultado inmediato $ar\equiv 1 \pmod{m}$ .

2. Otro método es jugar con las fracciones El método de Gauss: $$\frac{1}{7} = \frac{1\times 5}{7\times 5} = \frac{5}{35} = \frac{5}{4} = \frac{5\times 8}{4\times 8} = \frac{40}{32} = \frac{9}{1}.$$ Aquí se reduce el módulo $31$ en su caso, y lo único que hay que tener cuidado es que sólo se debe multiplicar y dividir por cosas relativamente primarias al módulo. En este caso, ya que $31$ es primo, esto es fácil. En cada paso, me limité a multiplicar por el menor número que diera lugar a una reducción; así que primero multipliqué por $5$ porque es el menor múltiplo de $7$ que es mayor que $32$ y más tarde lo multipliqué por $8$ porque era el menor múltiplo de $4$ que es mayor que $32$ . Añadido: Como señala Bill, el método puede fallar para los módulos compuestos.

Los dos métodos anteriores funcionan para módulos generales, no sólo para un módulo primo (aunque el método 2 puede fallar en esa situación); por supuesto, sólo se pueden encontrar inversos multiplicativos si el número es relativamente primo al módulo.

Actualización. Sí, su método para las congruencias lineales generales es el estándar. Tenemos un método muy sencillo para resolver congruencias de la forma $$ax \equiv b\pmod{m},$$ es decir, tiene soluciones si y sólo si $\gcd(a,m)|b$ en cuyo caso tiene exactamente $\gcd(a,m)$ soluciones modulo $m$ .

Para resolver estas ecuaciones, primero se considera el caso con $\gcd(a,m)=1$ , en cuyo caso $ax\equiv b\pmod{m}$ se resuelve encontrando la inversa multiplicativa de $a$ modulo $m$ o como lo hice en el método $2$ por encima de mirar $\frac{b}{a}$ .

Una vez que sepa cómo resolverlos en el caso de que $\gcd(a,m)=1$ se puede tomar el caso general de $\gcd(a,m) = d$ y de $$ax\equiv b\pmod{m}$$ ir a $$\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},$$ para obtener la solución única $\mathbf{x}_0$ . Una vez que se tiene esa solución única, se obtienen todas las soluciones de la congruencia original considerando $$\mathbf{x}_0,\quad \mathbf{x}_0 + \frac{m}{d},\quad \mathbf{x}_0 + \frac{2m}{d},\quad\ldots, \mathbf{x}_0 + \frac{(d-1)m}{d}.$$

Answer 2

Sabemos que $(7,31) = 1$ . Así que puede utilizar el algoritmo euclidiano ampliado . En particular, se pueden encontrar dos enteros $s,t$ tal que $7s+31t = 1$ . Así que $7s \equiv 1 \pmod {31}$ .

Answer 3

Una pista: intenta utilizar el teorema de Fermats:

$a^{p-1}=1 \mod p$ para $p$ primo, y todos $a\in \mathbb{Z}$ .

Answer 4

Podemos visualizar la solución de $7x \equiv 1 \pmod{31}$ como la intersección de las dos "líneas"

$\ \ \ \ \ y \equiv 7x \pmod{31}$ y $y \equiv 1 \pmod{31}$ .

La primera línea se cierra bajo la suma y la resta, ya que pasa por el origen. Si $(x_1, y_1)$ y $(x_2, y_2)$ son puntos de la línea $y \equiv 7x \pmod{31}$ entonces también lo son $(x_1+x_2, y_1+y_2)$ y $(x_1-x_2, y_1-y_2)$ .

Para encontrar un punto de intersección de las líneas, partimos de los dos puntos $(1, 7)$ y $(0,31)$ en la primera línea, y restar repetidamente un punto de otro hasta que el $y$ -coordinación es 1.

$\ \ \ \ \ (0,31) - (1,7) = (-1, 24)$

$\ \ \ \ \ (-1, 24) - (1,7) = (-2, 17)$

$\ \ \ \ \ (-2, 17) - (1, 7) = (-3, 10)$

$\ \ \ \ \ (-3, 10) - (1, 7) = (-4, 3)$

$\ \ \ \ \ (1,7) - (-4, 3) = (5, 4)$

$\ \ \ \ \ (5,4) - (-4, 3) = (9,1)$

Por lo tanto, $x \equiv 9 \pmod{31}$ .

Puedes acelerar este procedimiento restando un múltiplo de un punto a otro punto. Esto nos lleva al algoritmo euclidiano.

Answer 5

Hay muchos métodos disponibles, por ejemplo, el algoritmo euclidiano ampliado , $ $ o un caso especial del algoritmo de Euclides que calcula los inversos en módulo de los primos que llamo Algoritmo de Gauss . $ $ Los cálculos suelen ser más sencillos utilizando aritmética de fracciones modulares Por ejemplo, véase aquí y aquí y aquí para alrededor de $20$ motley trabajó ejemplos a través de un puñado de métodos (y ver las listas de preguntas "enlazadas" de la barra lateral para muchos más).

O $ $ por Euler $\rm\ (a,m)=1 \Rightarrow\ a^{-1} \equiv a^{\phi(m)-1}\pmod{\! m},\,$ rápidamente computable por cuadratura repetida .

Nota: $ $ Esto último da lugar a una forma cerrada sencilla para el TRC (Teorema del Resto de China)

$\quad$ si $\rm\,\ (m,n)=1\,\ $ entonces $\rm\quad \begin{eqnarray}\rm x\!&\equiv&\rm a\ \ (mod\ m)\\ \rm x\!&\equiv&\rm b\ \ (mod\ n)\end{eqnarray} \iff\ x\equiv a\,n^{\phi(m)}\!+b\,m^{\phi(n)}\ \ (mod\ mn)$

De forma más general, véase el Descomposición de Peirce.

---

Actualización $ $ Marzo $16, 2020\!:\,$ Para completar, aplicamos algunos de los métodos vinculados a continuación.

---

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv \dfrac{4}{28}\equiv\dfrac{-27}{-3}\equiv 9\ $ por Algoritmo de Gauss .

---

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv \dfrac{1}{-6}\,\dfrac{1}{4}\equiv \dfrac{-30}{-6}\,\dfrac{32}{4}\equiv 5\cdot 8\equiv 9$

---

Como aquí: $ $ la libertad de elegir $\rm\color{#c00}{even}$ repeticiones de residuos $\!\bmod\!$ las probabilidades hacen división por 2 fácil:

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv\dfrac{\color{#c00}{32}}{\color{#c00}{-24}}\equiv\dfrac{4}{-3}\equiv\dfrac{-27}{-3}\equiv 9$

---

Por el fraccionado algoritmo euclidiano ampliado o asociados forma ecuacional

$ \begin{align} \bmod 31\!:\ \ \dfrac{0}{31}\overset{\large\frown}\equiv\color{#c00}{\dfrac{1}7}\ \, &\!\!\!\overset{\large\frown}\equiv\color{#0a0}{\dfrac{-4}3}\overset{\large\frown}\equiv\color{#90f}{\dfrac{9}1}\\[.7em] \text{said equationally}\ \ \ \ [\![1]\!]\ \ \ \ 31\, x&\,\equiv \ 0\ \\ [\![2]\!] \ \ \ \ \ \ \color{#c00}{7\,x}&\ \color{#c00}{ \equiv\ 1}\!\!\!\\ [\![1]\!]-4\,[\![2]\!] \rightarrow [\![3]\!]\ \ \ \ \ \ \color{#0a0}{3\,x} &\ \color{#0a0}{\equiv\ {-}4}\ \\ [\![2]\!] - 2\,[\![3]\!] \rightarrow [\![4]\!]\, \ \ \ \ \ \ \ \ \color{#90f}{x}&\ \color{#90f}{ \equiv\ 9} \end{align}$

---

A continuación explicamos la idea básica del método de Reciprocidad inversa .

$\!\!\bmod 31\!:\,\ n \equiv \dfrac{1}7\equiv \dfrac{1+31\color{#c00}k}7.\ $ Para un exactamente cociente que buscamos $\,k\,$ con $\,7\mid 1\!+\!31k,\,$ es decir

$\!\!\bmod 7\!:\,\ \begin{align}0&\equiv 1\!+\!31k\\ &\equiv 1 + 3k\end{align}\!$ $\iff\! \begin{align}3k&\equiv-1\\ &\equiv\,\ 6\end{align}\!$ $\iff \color{#c00}{k\equiv 2},\ $ así que $\ n \equiv \dfrac{1\!+\!31(\color{#c00}2)}7\equiv 9\pmod{\!31}$