Problemas para encontrar el módulo inverso

Question

Posible duplicado:
encontrar el inverso de $x\\bmod y$

Hola a todos

Unos amigos y yo estamos estudiando para un examen discreto y estamos teniendo algunos problemas para encontrar el módulo inverso de las cosas. La pregunta que nos chupamos es "cuál es el inverso de 8 mod 29".

¡Muchas gracias!

Answer 1

La inversa de $8$ modulo $29$ es un número entero $k$ tal que $8k \equiv 1\pmod{29}$ .

Hay muchas formas de encontrar ese número entero. La forma estándar es utilizar la función Algoritmo euclidiano ampliado pero a veces se puede hacer sin utilizar este algoritmo.

Por ejemplo $8\times 3 = 24 = -5\bmod 29$ y $-5\times -6 =30=1\bmod 29$ entonces $8\times(3\times-6) = 1\bmod 29$ . Ahora sólo tienes que ajustar añadiendo múltiplos de $29$ para obtener una respuesta entre $0$ y $28$ .

Answer 2

Utilizando Algoritmo de Gauss tenemos $\rm\displaystyle\ \frac{1}8\ \to\ \frac{4}{32}\ \equiv\ \frac{4}{3}\ \to\ \frac{40}{30}\ \equiv\ \frac{11}{1}\ \ (mod\ 29)$

Es decir, escala $\rm A/B\ \to AN/BN\ $ por el menos $\rm\:N\:$ para que $\rm\ BN > 29\:.\ $ A continuación, reduzca el numerador y el denominador $\rm\ mod\ 29,\:$ e iterar. Al final obtendrá un denominador de $1$ ya que cada paso reduce el denominador. ¿No es estupendo? Esa es la idea clave que llevó a Gauss a la primera demostración del Teorema Fundamental de la Aritmética, es decir, la factorización única de los números enteros.