Matemáticas discretas: Encontrar la inversa de (natural) módulo (natural)

Question

Básicamente el estilo de la pregunta es así:

Encuentre la inversa de $24$ , modulo $35$ .

La respuesta que obtengo es $-16$ mientras que wolframalpha obtiene 19. Sé que $35 - 16 = 19$ .

La pregunta no es necesariamente cómo encontrar la inversa, sino más bien (ya que mi examen es mañana), ¿cómo sé cuándo convertir una inversa negativa en una positiva? ¿Y siempre utilizo la regla de sumar el negativo al número mayor para obtener la inversa deseada?

Lo pregunto sobre todo porque creo que he estado recibiendo las inversiones incorrectas, pero es que la clave de respuestas de mi libro convierte el negativo en un inverso positivo. Sin embargo, no recuerdo que mi profesor haya mencionado nada de esto, así que no estoy seguro de qué respuesta debería poner en mi examen de mañana, y no sé si el contexto importa (¿está bien poner la inversa aunque sea negativa a veces?).

TLDR; Si el Algoritmo Euclidiano extendido da una inversa negativa: ¿Cómo puedo saber qué respuesta busca mi instructor o alguien más? Gracias.

Answer 1

Hay que dejar de pensar en los valores como números individuales distintos, sino como clases de equivalencia. -19 y 16 y 51 y 86 son todos valores equivalentes bajo el módulo 35 y debe pensarse que son la misma cosa. A veces, valores como -1 son útiles. Pero normalmente se prefieren los positivos.

Answer 2

Si busca un número que sea el multiplicativo inverso de $24 \mod 35$ la inversa $x$ se define $$ 24 \cdot x \mod 35 = 1 $$ desde $24 \cdot 19 = 456$ y $456 \mod 35 = 1$ wolfram tenía razón.

Answer 3

La mayor parte de su pregunta ya ha sido respondida adecuadamente, pero quería abordar esta parte:

¿Y siempre utilizo la regla de sumar el negativo al número mayor para obtener la inversa deseada?

No. En la mayoría de los casos esto será correcto. (Casi todos, a no ser que el redactor del examen intente ponerte la zancadilla.) Pero es conseguir la respuesta correcta para no del todo las razones correctas.

La regla que puedes seguir siempre es: Para convertir una respuesta negativa, o una respuesta positiva demasiado grande, sume o reste el módulo repetidamente para llevar tu respuesta a un rango con el que estés satisfecho.

Ejemplo de ejercicio en el que la regla del "número mayor" dará una respuesta incorrecta:

Encuentra la inversa de 200 módulo 31.

Verás, el truco es que esto equivale en realidad a preguntar "Encuentra la inversa de 14 módulo 31". La clase de equivalencia para 14 aquí es $\{...14, 14+31, 14+(2\times31), 14+(3\times31)...\}$ .

¿Tiene esto sentido?

Así, se aplica el algoritmo euclidiano a mi problema de ejemplo, se encuentra $-11$ como su respuesta, y añada el módulo es decir, 31, para obtener la respuesta 20.