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

Para la primera Q.

Sea $17=x_1.$ Para cada $n,$ si $|x_n|>1,$ tomar entero positivo $K_n$ tal que $$|K_nx_n|<41<|(1+K_n)x_n| .$$ Toma $x_{n+1}$ con $41>|x_{n+1}|$ donde: ...

(i). Si $41-|K_nx_n|<|(1+K_n)x_n|-41$ entonces $x_{n+1}\equiv K_nx_n \pmod {41}$ ...

(ii). En caso contrario $x_{n+1}\equiv (1+K_n)x_n \pmod {41}.$

(Esto es más rápido que simplemente tomar $x_{n+1}\equiv 41- K_nx_n \pmod {41},$ ya que garantiza que si $|x_n|>1$ entonces $|x_{n+1}|\leq |x_n|/2.)$

Si $|x_n|=1$ entonces para.

Tenemos $17=x_1$ y $34=17\cdot 2<41<17\cdot 3=51$ así que $K_1=2.$ Tenemos $41-34<51-41$ así que tomamos $x_2\equiv 17\cdot 2 \pmod {41}$ . Es decir, $x_2=-7$ . Ahora tenemos $35=5|x_2|<41<6|x_2|=42$ así que $K_2=5$ . Y $41-35>42-41$ así que tomamos $x_3\equiv (1+K_2)x_2 \pmod {41}.$ Eso es, $x_3= -1.$

Ahora modulo 41 tenemos $-1\equiv (1+k_2)\cdot k_1\cdot 17 \equiv 6\cdot 2\cdot 17 \equiv 12\cdot 17.$ Por lo tanto $1\equiv (-12)17\equiv 29\cdot 17.$

Answer 2

Decir que x es el inverso multiplicativo de 17 mod 41 significa que 17x= 1 (mod 41), lo que equivale a decir que 17x= 1+ 41n para algún número entero n. Esto es lo mismo que la "ecuación diofantina" 17x- 41n= 1.

Para resolverlo, utiliza el "algoritmo de la división euclidiana": 17 se divide en 41 dos veces con resto 7: 41- 2(17)= 7. 7 se divide en 17 dos veces con resto 3: 17- 2(7)= 3 3 se divide en 7 dos veces con resto 1: 7- 2(3)= 1.

Sustituye el 3 de esa última ecuación por 17- 2(7): 7- 2(17- 2(7))= 5(7)- 2(17)= 1 Sustituye el 7 de esa ecuación por 41- 2(17): 5(41- 2(17))- 2(17)= 5(41)- 12(17)= 1.

Por tanto, una solución de 17x- 41n= 1 es x= -12, n= -5. Pero x= -12+ 41k,n= -5+ 17k también es una solución para cualquier número entero k: 17(-12+ 41k)- 41(-5+ 17k)= -204+ (17)(41)k+ 205- (41)(17)k= 1.

Aquí, x debe ser no negativo y menor que 41: toma k= 1: x= -12+ 41= 29

Answer 3

Usando el pequeño teorema de Fermat, $$17^{40}\equiv 1\pmod{41}\Rightarrow 17^{39}\cdot17\equiv 1\pmod{41}$$ Por lo tanto $17^{39}$ es el inverso buscado. Tenemos $$17^2\equiv 2\pmod{41}\Rightarrow 17^{30}\equiv 2^{15}\equiv 9\pmod{41}$$ $$17^9\equiv(17^2)^4\cdot 17\equiv 16\cdot17\equiv26\pmod{41}$$ Por lo tanto $$17^{39}\equiv9\cdot26\equiv 29\pmod{41}$$ Por lo tanto, la inversa es $29$ .