Resolución manual de congruencias lineales: fracciones modulares e inversas

Question

Cuando me enfrento a una congruencia lineal simple como $$9x \equiv 7 \pmod{13}$$ y estoy trabajando sin ninguna ayuda de cálculo a mano, tiendo a hacer algo como lo siguiente:

"Aviso" de que añadir $13$ a la derecha y restando $13x$ a la izquierda da: $$-4x \equiv 20 \pmod{13}$$

para que $$x \equiv -5 \equiv 8 \pmod{13}.$$

Está claro que este proceso funciona y es fácil de justificar (aparte de no tener un algoritmo para "darse cuenta"), pero mi pregunta es la siguiente: Tengo un vago recuerdo de haber leído en alguna parte que este tipo de proceso era el método preferido de C. F. Gauss, pero ahora no encuentro ninguna prueba de ello, así que ¿alguien sabe algo al respecto, o podría aportar alguna referencia? (¿O me lo he imaginado todo?)

También me interesaría saber si alguien más hace algo parecido.

Answer 1

$bx\equiv a\pmod{\!m}$ tiene un único solución $\!\iff\!b\,$ es coprimo al módulo $m$ . Si es así, por Bezout $\,b\,$ es invertible $\!\bmod m,\,$ por lo que el escalado $\,bx\equiv a\,$ por $\,b^{-1}\,$ obtenemos la solución única $\,x\equiv b^{-1}a =: a/b.\,$ Podemos calcular rápidamente $\,b^{-1}\pmod{\!m}\,$ por el algoritmo euclidiano ampliado pero a menudo hay formas más convenientes para números más pequeños (p. ej. aquí y aquí son algunos de los métodos aplicados). A continuación describimos algunos de estos métodos $\, x\equiv b^{-1}a \equiv a/b\,$ como fracción modular. [Ver aquí para el método general cuando el la solución no es única es decir, cuando $\gcd(b,m)>1$ ].

---

La primera, Algoritmo de Gauss se basa en la demostración de Gauss del lema de Euclides mediante el descenso $\,p\mid ab\,\Rightarrow\, p\mid a(p\bmod b).\,$ Generalmente sólo funciona para módulos primos, pero también podemos ejecutar el algoritmo euclídeo general extendido también en forma de fracción (utilizando multivalores "fracciones").

Funciona escalando repetidamente $\rm\:\color{#C00}{\frac{A}B}\overset{\times\ N} \to \frac{AN}{BN}\: $ por el menos $\rm\,N\,$ con $\rm\, BN \ge 13,\, $ entonces reduciendo mod $13$

$$\rm\displaystyle \ mod\ 13\!:\,\ \color{#C00}{\frac{7}9} \,\overset{\times\ 2}\equiv\, \frac{14}{18}\, \equiv\, \color{#C00}{\frac{1}5}\,\overset{\times \ 3}\equiv\, \frac{3}{15}\,\equiv\, \color{#C00}{\frac{3}2} \,\overset{\times\ 7}\equiv\, \frac{21}{14} \,\equiv\, \color{#C00}{\frac{8}1}\qquad\!\! $$

Denominadores del $\color{#c00}{\rm reduced}$ las fracciones disminuyen $\,\color{#C00}{ 9 > 5 > 2> \ldots}\,$ así que alcance $\color{#C00}{1}\,$ (no $\,0\,$ de lo contrario el denominador sería a correcto factor del prime módulo; puede fallar para compuesto módulo)

Más sencillo: $ $ utilizando $\rm\color{#0a0}{least}$ residuos: $\displaystyle\ \ \frac{7}9\,\equiv\, \frac{7}{\!\color{#0a0}{-4}\!\ \,}\,\overset{\times\ 3}\equiv\,\frac{21}{\!\!-12\ \ \ \!\!}\,\equiv\, \color{#c00}{\frac{8}1}$

Esta optimización mediante $\rm\color{#0a0}{least\ magnitude}$ residuos $\,0,\pm 1, \pm 2.\ldots$ a menudo simplifica la aritmética mod. Aquí también podemos optimizar (a veces) cancelando los factores comunes obvios, o eliminando los factores obvios de los denominadores, etc. Por ejemplo

$$\frac{7}9\,\equiv\, \frac{\!-6\,}{\!-4\,}\,\equiv\frac{\!-3\,}{\!-2\,}\,\equiv\frac{10}{\!-2\,}\,\equiv\,-5$$

$$\frac{7}9\,\equiv\,\frac{\!-1\cdot 6}{\ \ 3\cdot 3}\,\equiv\,\frac{\!\,12\cdot 6\!}{\ \ \,3\cdot 3}\,\equiv\, 4\cdot 2$$

---

O gíralo como tú: $ $ comprobar si cociente $\rm a/b\equiv (a\pm\!13\,i)/(b\pm\!13\,j)\,$ es exacto para pequeños $\rm\,i,j,\,$ Por ejemplo

$$ \frac{1}7\,\equiv \frac{\!-12}{-6}\,\equiv\, 2;\ \ \ \frac{5}7\,\equiv\,\frac{18}{\!-6\!\,}\,\equiv -3$$

Cuando se trabaja con números más pequeños, hay más probabilidades de que se apliquen estas optimizaciones (ley de los números pequeños), por lo que merece la pena buscarlas en los cálculos manuales.

Generalmente podemos elegir un numerador congruente dando un cociente exacto por Reciprocidad inversa .

$\bmod 13\!:\ \dfrac{a}{b}\equiv \dfrac{a-13\left[\color{#0a0}{\dfrac{a}{13}}\bmod b\right]}b\,\ $ Por ejemplo $\,\ \dfrac{8}9\equiv \dfrac{8-13\overbrace{\left[\dfrac{8}{\color{#c00}{13}}\bmod 9\right]}^{\large\color{#c00}{ 13\ \,\equiv\,\ 4\ }}}9\equiv\dfrac{8-13[2]}9\equiv-2$

Tenga en cuenta que el valor $\,\color{#0a0}{x\equiv a/13}\,$ es exactamente lo que necesitamos para que el numerador sea divisible por $b,\,$ es decir

$\qquad\quad\bmod b\!:\,\ a-13\,[\color{#0a0}x]\equiv 0\iff 13x\equiv a\iff \color{#0a0}{x\equiv a/13}$

Esto es esencialmente una optimización del Algoritmo Euclidiano Extendido (cuando toma dos pasos).

Nota $ $ Algoritmo de Gauss es mi nombre de un caso especial del algoritmo euclidiano que es implícito en la de Gauss Disquisitiones Arithmeticae, Art. 13, 1801 . No sé si Gauss explícitamente utilizado este algoritmo en otro lugar (al parecer, optó por evitar el uso o la mención del algoritmo euclidiano en Disq. Arith. ). Gauss menciona brevemente las fracciones modulares en el Art. 31 en Disq. Arith .

La reformulación anterior en términos de fracciones no aparece en la obra de Gauss, que yo sepa. La ideé en mi juventud, antes de haber leído Disq. Arith. Es probable que sea muy antiguo, pero no recuerdo haberlo visto en ninguna publicación. Estaría muy agradecido por cualquier referencia histórica.

Véase aquí para más información, incluida una comparación detallada con el descenso empleado por Gauss y una prueba formal de la corrección del algoritmo.

Cuidado con $ $ La aritmética de fracciones modulares sólo es válida para fracciones con denominador coprimo al módulo. Ver aquí para seguir debatiendo.

Answer 2

Cuando el primo es razonablemente pequeño prefiero encontrar directamente la inversa: $$9^{-1}=\frac{1}{9}=3\pmod {13}\Longrightarrow 9x=7\Longrightarrow x=7\cdot 9^{-1}=7\cdot 3= 21=8\pmod {13}$$ Pero ...pruebo el método de Gauss cuando el primo es grande y/o la evaluación de los inversos es complicada.

Answer 3

9x = 7 mod 13

9x = 7 + 13n

9x = 20 para n = 1

9x = 33 para n = 2

9x = 46 para n = 3

9x = 59 para n = 4

9x = 72 para n = 5

Entonces x = 8 mod 13

Se llega a la respuesta correcta antes de n = 13.

Answer 4

Otro proceso poco convencional pero con potencial algorítmico.

Resuelva $9x \equiv 7 \pmod{13}$ .

$\quad 9x = 7 + 13y \implies 0 \equiv 1 + y \pmod{3} \implies y \equiv 2 \pmod{3}$

y

$\quad y : 2 \; \mid \; 7 + 13y = 33 \quad \quad \text{NO GOOD!}$
$\quad y : 5 \; \mid \; 7 + 13y = 72 \quad \quad \text{AND is divisible by } 9$

Así que..,

$\tag{ANS} x \equiv 8 \pmod{13}$

Answer 5

Cuando se le presenta

$\tag 1 ax \equiv b \pmod{n}$

si $a \mid b$ la solución está justo delante de ti.

Pero también hay una solución "plug in" si $a \mid n-1$ o $a \mid n+1$ :

Si $a \mid n-1$ entonces $x = \Large(\frac{n-1}{a}) \normalsize (-b)$ resuelve $\text{(1)}$ .

Si $a \mid n+1$ entonces $x = \Large(\frac{n+1}{a}) \normalsize (b)$ resuelve $\text{(1)}$ .

¿Podemos "hacer heno" con la congruencia lineal de la OP?

$\quad 9x \equiv 7 \pmod{13} \; \text{ iff } \; -4x \equiv 7 \pmod{13} \; \text{ iff }$
$ \quad 4x \equiv -7 \pmod{13} \; \text{ iff } \; 4x \equiv 6 \pmod{13}$

Ahora trabajamos con $4x \equiv 6 \pmod{13}$ desde $4 \mid 12$ una solución es

$\quad x = \Large(\frac{n-1}{a}) \normalsize (-b) = (3)(-6) = -18 \equiv 8 \pmod{13}$

---

He aquí un ejemplo en el que el $n + 1$ se puede utilizar la manipulación:

$\quad 5x \equiv 1 \pmod{17} \; \text{ iff } \; -12x \equiv 1 \pmod{17} \; \text{ iff }$
$ \quad 12x \equiv -1 \pmod{17} \; \text{ iff } \; 12x \equiv 16 \pmod{17} \; \text{ iff } \; 6x \equiv 8 \pmod{17}$

Ahora trabajamos con $6x \equiv 8 \pmod{17}$ desde $6 \mid 18$ una solución es

$\quad x = \Large(\frac{n+1}{a}) \normalsize (b) = (3)(8) = 24 \equiv 7 \pmod{17}$