La solución de $ax \equiv c \pmod b$ eficiente al $a,b$ no coprime

Question

Sé cómo calcular modular inversos multiplicativos para el co-primer variables$a$$b$, pero hay un método eficiente para calcular la variable $x$ donde $x < b$ $a$ $b$ no son co-prime, dado variables $a$, $b$ y $c$, como se describe por la siguiente ecuación?

$ a x \equiv c \mod b $

Por ejemplo, dada

$ 154x \equiv 14 \mod 182 $, hay un método eficiente para calcular todas las posibilidades de $x$, sin pura fuerza bruta?

Por favor, tenga en cuenta que no estoy pidiendo una solución directa, sólo una más optimizado.

No creo que el Algoritmo de Euclides Extendido va a trabajar aquí, porque $a$ $b$ no son co-prime.

Editar: Pregunta de seguimiento, ya que el primero había un acceso directo:

Podría el ser calculada de manera eficiente?

$12260x \equiv 24560 \mod 24755$.

$107$ tiene que ser uno de los calculada respuestas.

Answer 1

La solución de $154x \equiv 14 \pmod{182}$ es lo mismo que encontrar todas las soluciones a $$ 154x + 182y = 14.$$ En este caso, se podría pensar en esto como la búsqueda de todas las soluciones para $$14(11x + 13y) = 14(1),$$ o más bien $$11x + 13 y = 1.$$ Finalmente, la resolución de este es la misma que la resolución de $11x \equiv 1 \pmod {13}$, que tiene solución $x \equiv 6 \pmod{13}$.

Así nos enteramos de que $x \equiv 6 \pmod{13}$ es la solución. Por supuesto, no se trata de un único residuo de la clase de mod $182$. El pensamiento modulo $182$, vemos que las soluciones se $x \equiv 6, 6+13,6+26,6+39, \ldots, 6+13*13 \equiv 6, 19, 32, \ldots, 175.$

Este enfoque funciona en general --- factor fuera el máximo común divisor, considerar el resultado modular problema, y luego traerlo de vuelta hasta que el problema original.

Answer 2

Nota:$\ \gcd( 154,182)=\color{#c00}{14}\,$, por lo que la factorización y cancelación de los rendimientos

$$ \color{#c00}{14}\cdot 13\,\mid\, \color{#c00}{14}\,(11x\!-\!1)\!\overset{\rm\ cancel\ \color{#c00}{14}_{\phantom{I_I}}\!\!\!\!}\iff\ 13\mid 11x\!-\!1\iff {\rm mod}\ \ 13\!:\ x\equiv \dfrac{1}{11}\equiv \dfrac{-12}{-2}\equiv 6 $$

A continuación se derivan de la solución general en las fracciones de la forma, que a menudo se simplifica enormemente mattters.

---

En general, vamos a considerar la solución de $\ B\, x \equiv A\pmod M.\ $ Si $\,d=(B,M)\,$ $\, d\mid B,\,\ d\mid M\mid B\,x\!-\!A\,\Rightarrow\, d\mid A\ $ es una condición necesaria para una solución de $\,x\,$ a existir.

Si es así, entonces vamos a $\ m, a, b \, =\, M/d,\, A/d,\, B/d.\ $ Luego cancelar $\,d\,$ a lo largo de yelds

$$\ x\equiv \dfrac{A}B\!\!\!\pmod{\!M}\iff M\mid B\,x\!-\!A \overset{\rm\large cancel \ d}\iff\, m\mid b\,x\! -\! a \iff x\equiv \dfrac{a}b\!\!\!\pmod{\!m}$$

donde la fracción $\ x\equiv a/b\pmod m\,$ denota todas las soluciones de $\,ax\equiv b\pmod m,\, $ al igual que para la fracción $\ x\equiv A/B\pmod M.\ $ Nota no puede ser cero, una o varias soluciones.

Lo anterior implica que si existen soluciones, entonces podemos calcular ellos por la cancelación de $\,d = (B,M)\,$ desde el numerador $\,A,\,$ el denominador $\,B\,$ y el módulo de $\,M.\,$, En otras palabras

$$ x\equiv \dfrac{ad}{bd}\!\!\pmod{md}\iff x\equiv \dfrac{a}b\!\!\pmod m$$

Si $\, d>1\, $ la fracción $\, x\equiv A/B\pmod{\!M}\,$ es de múltiples valores, que denota la $\,d\,$ soluciones

$$\quad\ \begin{align} x \equiv a/b\!\!\pmod m\, &\equiv\, \{\, a/b + k\,m\}_{\,\large 0\le k<d}\!\!\pmod{M},\,\ M = md\\ &\equiv\, \{a/b,\,\ a/b\! +\! m,\,\ldots,\, a/b\! +\! (d\!-\!1)m\}\!\!\pmod M \end{align}$$ $ {\rm e.g.} \overbrace{\dfrac{6}3\pmod{\!12}}^{{\rm\large cancel}\ \ \Large (3,12)\,=\,3}\!\!\!\!\equiv \dfrac{2}{1}\!\pmod{\!4}\equiv \!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\{2,6,10\}}^{\qquad\ \ \Large\{ 2\,+\,4k\}_{\ \Large 0\le k< 3}}\!\!\!\!\!\!\!\!\!\!\!\!\!\pmod{12}$

---

Comentario $ $ Estos valores múltiples fracciones surgen con frecuencia en el algoritmo de Euclides extendido cuando se realiza en forma fraccionada. Lo vamos a usar para calcular los $\, x\equiv \color{#0a0}{9/5}\pmod{18}.\,$ obtenemos

$${\rm mod}\ 18\!:\ \ \ \underbrace{\overbrace{\dfrac{0}{18}\overset{\large\frown}\equiv \color{#0a0}{\dfrac{9}5} \overset{\large\frown}\equiv \dfrac{9}3}^{\Large\ \ 0\,-\,3(\color{#0a0}9)\ \equiv\ 9\ }}_{\Large 18\,-\,3(\color{#0a0}5)\ \equiv\ 3}\overset{\large\frown}\equiv \dfrac{0}{2}\overset{\large\frown}\equiv \color{#c00}{\dfrac{9}{1}}\overset{\large\frown}\equiv\dfrac{0}0\qquad\quad $$

por lo $\ {\rm mod}\ 18\!:\ x\equiv\color{#0a0}{9/5}\equiv\color{#c00}{ 9/1}\equiv 9.\,$ Cheques $\, 5x\equiv 5\cdot9\equiv 45\equiv 9,\,$ es de hecho verdad.

Encima de cada Euclidiana paso de reducción esencialmente mods sucesivas denominadores de la siguiente manera

$$ \dfrac{a}{b}\overset{\large\frown}\equiv\dfrac{c}d\overset{\large\frown}\equiv\dfrac{a-qc}{b-qd}\ \ {\rm where}\ \ q = \lfloor b/d \rfloor,\ \ {\rm so }\ \ b\!-\!qd = b\bmod d$$

es decir, los denominadores son los valores que ocurren en el algoritmo de Euclides para $\,\gcd(18,\color{#0a0}5),\,$ pero podemos realizar estas operaciones en paralelo en los numeradores también, por ejemplo, el primer paso por encima de ha $\, q =\lfloor 18/\color{#0a0}5\rfloor = 3\,$ por lo que el denominador es $\, 18-3(\color{#0a0}5)\equiv 3.\,$ Ejecutar la misma operación en los numeradores de los rendimientos de la siguiente numerador, se $\ 0-3(\color{#0a0}9)\equiv 9.\,$ Los siguientes pasos proceder de la misma manera, pero todos los cocientes (excepto la final $\,q=2)$ $\,q=1,\,$ así que simple resta sucesiva de los numeradores y denominadores.

El invariante en el algoritmo es que el común de las soluciones de cada uno de los vecinos par de fracciones permanece constante. Se inicia como la solución común de $\,0/18\overset{\large\frown}\equiv 9/5$ $\,:= 18x\equiv 0,\ 5x\equiv 9.\,$ que es equivalente a $\,5x\equiv 9,\,$ desde $\,18x\equiv 0\,$ es cierto para todos los $\,x\,$ $\,18\equiv 0.\,$ Asimismo se termina con la solución común de $\,9/1 \overset{\large\frown}\equiv 0/0\,$ $:= 1x\equiv 9,\ 0x\equiv 0,\,$ y de nuevo el último eliminado.

La prueba de que la distancia Euclídea reducción conserva el conjunto solución es la siguiente.

$\qquad\ \ $ Si $\,\ dx\!-\!c \equiv 0\,\ $ $\,\ bx\!-\!a \equiv 0\! \iff\! \overbrace{(bx\!-\!a)-q(dx\!-\!c)}^{\Large (b-qd)\,x\,-\,(a-qc)}\!\equiv 0$

Esto implica inmediatamente que $\ \ \begin{align}bx&\equiv a\\ dx&\equiv c\end{align}$ $\!\iff\!\! \begin{align}(b\!-\!qd)x&\equiv a\!-\!qc\\ dx&\equiv c\end{align}$

Es instructivo mirar el sistema intermedio $\, 9/3\overset{\large\frown}\equiv 0/2.\,$ Por encima sabemos que

$$\begin{align} &\overbrace{\dfrac{9}3\!\!\!\pmod{18}}^{{\rm\large cancel}\ \ \Large (3,18)\,=\,3}\!\!\!\equiv\, \dfrac{3}{1}\!\!\!\pmod{6}\,\equiv\, \{3,\color{#c00}9,15\}\!\!\!\pmod{18} \\ \\ & \underbrace{\dfrac{0}2\!\!\!\pmod{18}}_{{\rm\large cancel}\ \ \Large (2,18)\,=\,2}\!\!\!\equiv\, \dfrac{0}{1}\!\!\!\pmod{9}\,\equiv\, \{0,\color{#c00}9\}\ \ \ \pmod{18} \end{align}\quad\ \ $$

Observe que la solución común de ambos es, de hecho, $\,\ x\equiv \color{#c00}9\pmod{18},\, $ como vimos anteriormente. Tenga en cuenta también que aunque comenzamos con una fracción $\,9/5\,$ cuyo denominador $\,5\,$ es coprime para el módulo de $\,18\,$ (de modo que la fracción es de valor único), el algoritmo de Euclides pasa a través de varias de múltiples valores de fracciones (con la no-coprime denominadores), incluso en sistemas con ambas fracciones de valores múltiples, tales como $\, 9/3\overset{\large\frown}\equiv 0/2\,$ anterior, es decir, el sistema de $\, 3x\equiv 9,\ 2x\equiv 0\pmod{18}.$

Estos cálculos son más comúnmente expresada sin fracciones en lugar de realizar operaciones en los sistemas de ecuaciones - la generalización de las operaciones de eliminación Gaussiana y triangularization, por ejemplo, la reducción de matrices para Hermite /Smith forma normal. Estos temas son estudiados de manera más abstracta en la teoría de los módulos en álgebra abstracta (esencialmente la generalización de álgebra lineal para permitir que los escalares de un anillo, no sólo un campo).

Answer 3

A continuación calculamos el $\ x\,\equiv\, \dfrac{24560}{12260}\,\pmod{\!24755}\ $ por la edición, $ $ por el método en mi primera respuesta.

${\rm mod}\,\ 24755\!:\,\ \dfrac{0}{24755}\overset{\large\frown}\equiv\dfrac{24560}{12260}\overset{\large\frown}\equiv\dfrac{390}{235}\overset{\large\frown}\equiv\dfrac{4280}{40}\overset{\large\frown}\equiv\color{#c00}{\dfrac{-535}{-5}}\overset{\large\frown}\equiv\dfrac{0}0$

$\begin{align}{\rm Therefore}\ \ \ x\equiv {\color{#c00}{\dfrac{535}5}\!\!\!\pmod{24755}}&\equiv \,107\!\!\pmod{\!4951},\ \ {\rm via\ canceling}\ \ 5\\ &\equiv\, 107+4951k\!\!\pmod{\!24755},\ \ 0\le k\le 4\\[0.5em] &\equiv \{107,\, 5058,\, 10009,\, 14960,\, 19911\}\!\pmod{\!24755}\end{align} $

Answer 4

Para solucionar $ax\equiv c \mod b$, $\;d=a\wedge b$, $\;a=a'd, \;b=b'd$. Esta congruencia implica $c$ es divisible por $d$. En realidad, es fácil ver que $$ax\equiv c\mod b\iff \begin{cases}c\equiv 0\mod a\wedge b\\\text{and}\\a'x\equiv c'=\dfrac{c}{a\wedge b} \mod b' \end{casos}$$ Por lo tanto el problema se reduce al caso de $a$ $b$ coprime, después de una compatibilidad condición ha sido comprobada.

Añadido: soluciones de la segunda congruencia

Primero revisamos con el algoritmo de Euclides que $\gcd(12260,24755)=5$, e $$\frac{12260}5=2452,\quad\frac{24755}5=4951,\quad\frac{24560}5=4912. $$ Así, el dado es equivalente a la congruencia $ \; 2452 x\equiv 4912\mod 4951$, y tenemos que encontrar la inversa de a $2452$ modulo $4951$. Esto significa que tenemos que encontrar una *de Bézout la relación entre el$2452$$4951$. Puede ser obtenido con el algoritmo de Euclides extendido: $$\begin{array}{rrrr} r_i&u_i&v_i&q_i\\ \hline 4951&0&1\\ 2452&1&0&2\\\hline 47&-2&1&52\\ 8&105&-52&5\\ 7&-527&261&1\\ 1&632&-313\\\hline \end{array}$$ Por lo tanto $632\cdot2452-313\cdot4951=1$, de donde $2452^{-1}=632\bmod4951$, y la solución es $$x\equiv 632\cdot4912\equiv 107\mod4951.$$

Answer 5

Por tu pregunta, supongo que usted sabe cómo utilizar el algoritmo de Euclides extendido para calcular el inverso modular $a^{-1} \pmod b$ al $a$ es coprime a $b$. Incluso cuando $a$ es no coprime a $b$, en realidad se puede solucionar $ax \equiv c \pmod b$ en casi exactamente de la misma manera, suponiendo que existe una solución.

Lo que el algoritmo de Euclides extendido en realidad calcula, dado que las entradas $a$$b$, un triple de números enteros $(\bar a, \bar b, g)$ tal que $g$ es el máximo común divisor de a$a$$b$, e $a\bar a + b\bar b = g$. Al$g = 1$,$\bar a = a^{-1} \pmod b$, y se puede usar para calcular la solución de $x \equiv c \bar a \pmod b$ a modular la congruencia $ax \equiv c \pmod b$.

Al $g$ no $1$, que se podría llamar el par $(\bar a, g)$ el pseudoinverse* de $a$ modulo $b$, como se satisface la congruencia $a \bar a \equiv g \pmod b$ donde $g$ es el menor número positivo para los cuales existe congruencia. Así, dada la congruencia $ax \equiv c \pmod b$, podemos multiplicar ambos lados por $\bar a$ obtener $gx \equiv c \bar a \pmod b$. Si (y sólo si) $c$ es divisible por $g$, también podemos, a continuación, divide ambos lados por $g$ (uso normal de división de enteros!) para obtener la solución $x \equiv c\bar a / g \pmod b$. Por supuesto, esta solución sólo es único modulo $b/g$.

De lo contrario, si $c$ no es divisible por $g$, no existe ninguna solución.

^{*) No vas a encontrar el término "modular pseudoinverse" en los libros de texto, ya que acabo de hacer. No estoy al tanto de más plazo establecido para este concepto útil, sin embargo, y al menos es descriptivo, así que permítame para usarlo aquí.}