Halla la inversa de 17 mod 41

Question

Preguntas

(1) Halla la inversa de $17 \mod 41$ .

(2) Halla el menor número positivo n para que $17n \equiv 14 \pmod{41}$

---

Para la primera pregunta, mi intento es el siguiente:

$$41-17\cdot2=7$$

$$17-7\cdot2=3$$

$$7-3\cdot2=1$$

$$7-2(17-7\cdot2)=1$$

$$7-2\cdot17=1$$

$$41-17\cdot2-2\cdot17=1$$

$$41-4\cdot17=1$$

Por tanto, la inversa de $17$ es $-4$ .

Es decir, la inversa de $17$ es $37$

¿Estoy en lo cierto?

Answer 1

Los inversos modulares pueden calcularse mediante la función algoritmo euclidiano ampliado , así como otros métodos menos conocidos que a veces son más sencillos para números pequeños. Algunos de ellos son los siguientes.

En primer lugar, consideremos Algoritmo de Gauss, que escala la parte (superior e inferior) de la fracción para que la parte inferior sea más pequeña cuando se reduce mod. $41$ por ejemplo $\,2\cdot 17\equiv -7\,$ a continuación (todas las congruencias son mod $41)$

---

Algoritmo de Gauss: $\,\ \color{#0a0}{\dfrac{1}{17}}\equiv \dfrac{2}{34}\equiv \dfrac{2}{-7}\equiv \dfrac{-12}{42}\equiv \dfrac{\color{#c00}{-12}}1$

---

Ext. Euclides en fracciones: $\,\ \dfrac{1}{17}\equiv \dfrac{-2}{7}\equiv \dfrac{5}3\equiv\dfrac{\color{#c00}{-12}}1$

---

Factoring: $\,\ \color{#0a0}{\color{#0a0}{\dfrac{1}{17}}}\equiv \dfrac{42}{17}\equiv 6\cdot \dfrac{7}{17}\equiv 6\cdot\dfrac{-34}{17}\equiv 6(-2)\equiv\color{#c00}{-12}$

---

Por lo tanto $\ 17x \equiv 14\,\Rightarrow\, x\equiv (\color{#0a0}{1/17})14 \equiv(\color{#c00}{-12})14\equiv -4(3\cdot 14)\equiv -4$

---

Alternativamente, podemos calcular $\,14/17\,$ directamente mediante factorización como en el caso anterior

a saber $\,\ {\rm mod}\ 41\!:\,\ \dfrac{14}{17}\equiv 2\cdot \dfrac{7}{17}\equiv 2\cdot\dfrac{-34}{17}\equiv 2(-2)\equiv -4$

---

Cuidado con $ $ La aritmética de fracciones modulares sólo es válida para fracciones con denominador coprimo al módulo. Ver aquí para seguir debatiendo.

Answer 2

En virtud de la Algoritmo euclidiano ampliado Anota el proceso de búsqueda de un DGC y cómo has llegado a él. Esto se puede utilizar para encontrar inversos multiplicativos:

$$ \begin{array}{c|c|c|c|l} q & r & a & b & \text{implied equation} \\ \hline & 41 & 1 & 0 & 41 = 1\cdot 41 + 0\cdot 17\\ & 17 & 0 & 1 & 17 = 0\cdot 41 + 1\cdot 17\\ 2 & 7 & 1 & -2 & \;\; 7 = 1\cdot 41 + (-2)\cdot 17\\ 2 & 3 & -2 & 5 & \;\;3 = (-2)\cdot 41 + 5\cdot 17\\ 2 & 1 & 5 & \color{red}{-12} & \;\;1 = 5\cdot 41 + (-12)\cdot 17\\ \end{array} $$

Las dos primeras líneas establecen los números considerados como bases. Luego, en cada etapa, $q$ da el resultado de la división entera de los dos anteriores $r$ que, a su vez, determina cómo construir el $r$ , $a$ y $b$ valores de la fila actual: restar off $q$ multiplicado por el valor de la fila anterior. (La columna final aquí no es necesaria, es sólo para ayudar a la comprensión si no has visto esto antes).

Esto nos da la identidad relevante de Bezout, $5\cdot 41 + (-12)\cdot 17 = 1 $ lo que nos da inmediatamente $-12$ como la inversa de $17 \bmod 41$ :

$5\cdot 41 + (-12)\cdot 17 \equiv (-12)\cdot 17 \equiv 29\cdot 17 \equiv 1 \bmod 41$

es decir, $17^{-1} \equiv 29 \bmod 41$ .

La segunda cuestión se resuelve fácilmente, ya que $17n\equiv 14 \bmod 41$ $\implies$ $n\equiv -12\cdot 14 \bmod 41$ (es decir $n\equiv -168 \equiv -4 \equiv 37 \bmod 41$ ).

Answer 3

\begin{align*} 41 &= 2 \cdot 17 + 7 & 7 &= 1 \cdot 41 - 2 \cdot 17 \\ 17 &= 2 \cdot 7 + 3 & 3 &= 1 \cdot 17 - 2 \cdot (1 \cdot 41 - 2 \cdot 17) \\ && &= 5 \cdot 17 - 2 \cdot 41 \\ 7 &= 2 \cdot 3 + 1 & 1 &= 1 \cdot 7 - 2 \cdot 3 \\ && &= 1\cdot(1 \cdot 41 - 2 \cdot 17) - 2 \cdot (5 \cdot 17 - 2 \cdot 41) \\ && &= 5 \cdot 41 - 12 \cdot 17 \end{align*}

Por lo tanto $17^{-1} \cong -12 \cong 29 \pmod{41}$ .

Answer 4

El error que he detectado en tu respuesta está aquí:.

Tras llegar a $7-2(17-7*2)=1$ lo has simplificado erróneamente como $7-2*17=1$ la simplificación correcta es $5*7-2*17=1$ . Entonces procede.

Answer 5

$$17x\equiv 1\pmod{41}\\-24x\equiv -40\pmod{41}\\3x\equiv 5\pmod{41}\\3x\equiv-36\pmod{41}\\x\equiv -12\equiv29\pmod{41}$$ Multiplicar $x\equiv29\pmod{41}$ por $14$ también da una solución correcta aunque no estoy muy seguro de si es una coincidencia o no. $$\\17x\equiv14\pmod{41}\\-24x\equiv14\pmod{41}\\-12x\equiv 7\pmod{41}\\-12x\equiv-34\pmod{41}\\6x\equiv17\pmod{41}\\6x\equiv-24\pmod{41}\\x\equiv -4\equiv37\pmod{41}$$