Cómo resolver esta congruencia $17x \equiv 1 \pmod{23}$ ?

Question

Dado $17x \equiv 1 \pmod{23}$

¿Cómo resolver esta congruencia lineal? Todas las pistas son bienvenidas.

editar: Conozco el Algoritmo Euclidiano y sé resolver la ecuación $17m+23n=1$ pero no sé cómo calcular x con el uso de m o n.

Answer 1

A través de algoritmos se puede emplear el Algoritmo de Euclides Extendido a invertir $\,17\,$ modulo $\,23\,$ (posible ya que son coprime). Pero para números pequeños es generalmente más rápido para utilizar otros métodos, por ejemplo, la reescritura de $\,17^{-1} \equiv \frac{1}{17}$ como una fracción, entonces la adición de $\pm$módulo para el numerador y el denominador hasta que se obtiene un cociente exacto. Hacer esto $\rm\color{#c00}{first}$ a minimizar el valor absoluto del denominador (para aumentar la probabilidad de un cociente exacto), y $\rm\color{#0a0}{then}$ hacer lo mismo para el numerador, con el objetivo de obtener un múltiplo del denominador. Por ejemplo

$${\rm mod}\ 23\!:\,\ 17x\equiv 1\,\Rightarrow\,x \,\equiv\, \dfrac{1}{17} \,\color{#c00}\equiv\, \dfrac{1}{-6}\,\color{#0a0}\equiv\,\dfrac{24}{-6} \,\equiv\, -4 \,\equiv\, 19\qquad\qquad$$

Nota: se restan $23$ desde el denominador para obtener el mínimo entero $\,-6 \equiv 17\pmod {23},\,$ desde $\,23\equiv -1\pmod 6,\,$ añadimos el numerador $(= 1)$ hacer el numerador divisible por $6$.

Cuidado con $\ $ Para non-prime módulos uno debe asegurarse de restringir los denominadores que son coprime para el módulo (por lo invertible), por lo que para evitar el modular analógico de la división por cero.

En este ejemplo, el método descrito termina siendo esencialmente un caso especial de dicho algoritmo, reinterpretado en forma fraccionada. Pero esto no siempre es así. La ventaja de las fracciones de la forma es que se permite la utilización conocido fracciones de la aritmética (sujeto a dicha restricción), por ejemplo, la cancelación de los factores comunes. Uno puede encontrar muchos ejemplos de dimensionamiento es de mis anteriores posts.

Answer 2

Por el pequeño teorema de Fermat, $a^{p-1} \equiv 1$ (mod p) para un número primo p. Entonces $x=17^{21}$ debería funcionar seguro. Puede haber números más pequeños que satisfagan esto.

Answer 3

Sugerencia: Si no desea ver los resultados tratando de números,

Por el algoritmo de Euclides , usted puede encontrar $m,n$ tal que $$17m+23n=1$$ $$17m\equiv1 \ mod \ 23$$ so $m$ is the inverse of $17$, a continuación, el resultado de la siguiente manera.

Answer 4

Para hacer la división modular hago esto

an - bm = c donde c es dividendo, b es módulo y a es divisor, entonces n es cociente

17n - 23m = 1

A continuación, utilizando el algoritmo euclídeo, reduce a gcd(a,b) y registra cada cálculo

Como describe http://mathworld.wolfram.com/DiophantineEquation.html

17 23 $\quad$ 14 19

17 6 $\quad\;\;$ 14 5

11 6 $\quad\;\;\;\;$ 9 5

5 6 $\quad\;\;\;\;\;$ 4 5

5 1 $\quad\;\;\;\;\;$ 4 1

1 1 $\quad\;\;\;\;\;$ 0 1

La columna de la izquierda es el algoritmo euclidiano, la columna de la derecha es el procedimiento inverso

Por lo tanto $ 17*19 - 23*14 = 1$ es decir, n=19 y m=14.

El resultado es que 1/17 ≡ 19 mod 23

este método puede no ser tan rápido como los otros posts, pero esto es lo que he implementado en código. Los otros también podrían serlo, pero pensé en compartir mi método.

Answer 5

$$17x\equiv1\pmod{23}\\-6x\equiv-22\pmod{23}\\3x\equiv11\pmod{23}\\-20x\equiv-12\pmod{23}\\5x\equiv-20\pmod{23}\\x\equiv-4\pmod{23}\\x\equiv19\pmod{23}$$