Encuentra la inversa de 15 módulo 88.

Question

Aquí la pregunta: Encontrar una inversa $a$ para $15$ modulo $88$ para que $0 \le a \le 87$ es decir, encontrar un número entero $a \in \{0, 1, ..., 87\}$ para que $15a \equiv1$ (mod 88).

Aquí está mi intento de respuesta:

Si utilizamos el Algoritmo Euclidiano, tenemos que encontrar $\gcd(88, 15)$ que debe ser igual a $1$ para poder encontrar una inversa de $15 \pmod{88}$ .

\begin{align*} 88 & = 5 \times 15 + 13\\ 15 & = 1 \times 13 + 2\\ 13 & = 6 \times 2 + 1\\ 2 & = 2 \times 1 + 0 \end{align*}

Así que, $$\gcd(88, 15) = 1$$

Ahora, tenemos que escribir esto en el formulario: $$\gcd(88, 15) = 88x + 15y.$$

Y encontrar $x$ y $y$ .

\begin{align*} 1 & = 13(1) + 2(-6)\\ & = 13(7) + 15(-6)\\ & = 88(7) + 15(-41) \end{align*}

Así que, $x = 7$ y $y = -41$ .

Así que, un inverso de $15 \pmod{88} = -41$ . Ahora, necesito encontrar un inverso que esté entre $0$ y $87$ . ¿Cuál es un buen enfoque fácil para encontrar otros inversos? ¿Alguna idea, por favor?

Answer 1

Según el comentario de Arthur, recuerda que las clases de congruencia identifican todos los elementos con una cantidad determinada de diferencia (por ejemplo $-1\equiv87\pmod{88}$ ). Así, basta con añadir $88$ a su inversa hasta que dé un elemento entre $0$ y $87$ .

Answer 2

$x$ es un inverso de $15 \pmod{88}$ si y sólo si $x=88n-41$ para un número entero (cualquiera) $n$ porque es necesario y suficiente que $15(-41+x)$ es divisible por $88$ pero esto equivale a $(-41+x)$ siendo divisible por $88$ .

Answer 3

Para una forma sistémica, hay que utilizar el Algoritmo euclidiano ampliado : si tiene una relación de Bézout: $$u\times 88+v\times 15=1$$ el sabes la inversa de $15$ es $v\bmod88$ .

A continuación se muestra cómo visualizar el cálculo, teniendo en cuenta que, en el algoritmo de Euclides, el resto en cada paso es una combinación lineal de $88$ y $15$ :

\begin{array}[t]{lrrrr} \text{Successive Divisions}& r_i & u_i & v_i & q_i\\ \hline & 88 & 1 & 0 & \\ 88 = {\color{red}5} \times 15 +\color{blue}{13} & 15 &0 & 1 & \color{red}5 \\ 15 = {\color{red}1} \times 13 + \color{blue}{2} & \color{blue}{13} & 1 & -5 & \color{red}1 \\ 13 = {\color{red}6} \times 2 + \color{blue}{1} & \color{blue}{2} & -1 & 6 & \color{red}6 \\ & \color{blue}{1} & 7 & -41\\[2ex] \hline \end{array} Así, la inversa de $15$ modulo $88$ es $\;-41\equiv 47\mod 88$ .

Answer 4

    work             Translation(unnecessary once you know how to do this.)
    | 88    1    0   88 = 1(88) +  0(15)
 -6 | 15    0    1   15 = 0(88) +  1(15), add -6 x this row to the above row
  7 | -2    1   -6   -2 = 1(88) -  6(15), add  7 x this row to the above row
    |  1    7  -41    1 = 7(88) - 41(15)

Por lo tanto -41(15) ≡ 1 (mod 88)

Answer 5

$15n=88k+1$ . Pero $15n$ termina en $0$ o en $5$ . Así que estamos buscando un múltiplo de $88$ que termina en $9$ o en $4$ . El primer caso es imposible, ya que $88$ es un número par. Ahora, ¿cuál es el primer múltiplo de $8$ para terminar en un $4$ ? Así que $k_0=3$ es nuestro primer sospechoso. Desafortunadamente, en este caso, $n_0\not\in\mathbb N$ . Así que vamos a comprobar $k_1=3+5=8$ ya que el ciclo de $8x\bmod10$ tiene pierna $5$ . ¡Bingo! Tenemos $n_1=47$ .