Resolución de ecuaciones modulares usando el Método de Blankinship

Al final del artículo se puede descargar un fichero que permite resolver ecuaciones modulares del tipo ax$\equiv$b(mód n) . Para realizar las divisiones de números enteros se hace uso del paquete xlop de LaTeX, lo que provoca que existan algunas limitaciones en los valores permitidos de a y b (deben ser números naturales).

El fichero está preparado para generar las soluciones en los diferentes casos que se pueden presentar: no exista solución, tenga una sola solución o tenga varias soluciones. A partir de los valores $a$, $b$ y $n$ siempre se generan dos ejercicios de la forma:

1. $ax\equiv1\,\pmod n$
2. $ax\equiv b\,\pmod n$

Además, en todos ellos se añade un poco de teoría sobre qué se está haciendo. Para algunos valores de entrada los cálculos realizados pueden ser redundantes.

• Lo único que tendremos que adecuar en el fichero es:

  # Datos a modificar del programa. Tienen que ser enteros positivos y sus valores
  # están condicionados por lo permitido por el paquete xlop de LaTeX
  a = 1323
  b = 49
  n = 85085
  

Con los datos anteriores de entrada, se obtiene de salida:

Identidad de Bezout Si $a$ y $n$ son números enteros no nulos ambos entonces $\exists\,u,v\,\in\mathbb{Z}$ tales que $mcd(a,n)=a\cdot u+n\cdot v$

Por tanto:

Por otro lado, sabemos que

• Si $mcd(a,n)=1$ la solución es única y además, si encontramos $u$ y $v$ tales que $au+nv=1$ entonces $u$ es una solución particular de la ecuación $ax\equiv 1 \pmod{n}$.
• Si $mcd(a,n)=d>1$ y $d|b$ su solución es cualquier $x\equiv x_{0}+\dfrac{t\cdot n}{d}\pmod n,\,t=0,1,\ldots,d-1$ donde $x_{0}$ es una solución particular en la ecuación equivalente a la primera $a/d\equiv b/d\pmod{n/d}$

Dados dos números $a$ y $n$ queremos expresar a su máximo común divisor como una combinación lineal de ellos $au+nv=mcd(a,b)$ .

Método de Blankinship

Para ello consideraremos el sistema compatible y determinado de ecuaciones

$\begin{cases} 1\cdot x+0\cdot y$& =a\\ 0\cdot x+1\cdot y & =n \end{cases}

cuya única solución es $x=a$ e $y=n$ .

Además, usaremos el algoritmo de Euclides

A partir de la expresión anterior en la que obtenemos el resto como una combinación lineal del dividendo y el divisor, usaremos operaciones elementales por fila para obtener sistemas equivalentes, en su forma matricial, en los que los restos $r_{i}$ estén en la última columna.

Finalizamos el proceso cuando llegamos a una matriz con un cero en la última columna.

$\begin{cases} u\cdot x+v\cdot y$& =mcd(a,n)\\ -n\cdot x+a\cdot y & =0 \end{cases}

En ese caso tendremos en la fila correspondiente el $mcd$ y los coeficientes $u$ y $v$ de la combinación lineal

• Resuelve la ecuación modular: $1323x\,\equiv\,1\,\pmod{85085}$

Partimos del sistema $\begin{cases} 1\cdot x+0\cdot y$& =1323\\ 0\cdot x+1\cdot y & =85085 \end{cases} que tiene como soluciones $x=1323$ e $y=85085.$ Su forma matricial es:

Paso 0

$\Rightarrow$ 85085 = 64 · 1323 + 413 $\Rightarrow$ 85085 - 64 · 1323 = 413 $\Rightarrow$ Restamos a la segunda fila 64 veces la primera

Paso 1

$\Rightarrow$ 1323 = 3 · 413 + 84 $\Rightarrow$ 1323 - 3 · 413 = 84 $\Rightarrow$ Restamos a la primera fila 3 veces la segunda

Paso 2

$\Rightarrow$ 413 = 4 · 84 + 77 $\Rightarrow$ 413 - 4 · 84 = 77 $\Rightarrow$ Restamos a la segunda fila 4 veces la primera

Paso 3

$\Rightarrow$ 84 = 1 · 77 + 7 $\Rightarrow$ 84 - 1 · 77 = 7 $\Rightarrow$ Restamos a la primera fila 1 veces la segunda

Paso 4

$\Rightarrow$ 77 = 11 · 7 + 0 $\Rightarrow$ 77 - 11 · 7 = 0 $\Rightarrow$ Restamos a la segunda fila 11 veces la primera

Paso 5

Obtenemos el sistema equivalente al primero de ecuaciones:

$\begin{cases} \left(1029\right)\cdot x+\left(-16\right)\cdot y$& =7\\ \left(-12155\right)\cdot x+\left(189\right)\cdot y & =0 \end{cases}

En consecuencia

$\left({\color{red}1029}\right)\cdot1323+\left(-16\right)\cdot85085={\color{red}7}\,\,\Rightarrow\begin{cases} mcd(1323,85085)$& =7\\ u & =1029 \end{cases} No tiene solución ya que el mcd(a,n) no es 1

• Resuelve la ecuación modular: $1323x\,\equiv\,49\, \pmod{85085}$

$\Rightarrow$ $49=7\cdot7$

En este caso, mcd(a,n) (por el apartado anterior) divide a b. La ecuación anterior es equivalente a resolver $189x\,\equiv\,7\,\pmod{12155}$. Resolvamos primero la ecuación $189x\equiv1\pmod{12155}$

Paso 0

$\Rightarrow$ 12155 = 64 · 189 + 59 $\Rightarrow$ 12155 - 64 · 189 = 59 $\Rightarrow$ Restamos a la segunda fila 64 veces la primera

Paso 1

$\Rightarrow$ 189 = 3 · 59 + 12 $\Rightarrow$ 189 - 3 · 59 = 12 $\Rightarrow$ Restamos a la primera fila 3 veces la segunda

Paso 2

$\Rightarrow$ 59 = 4 · 12 + 11 $\Rightarrow$ 59 - 4 · 12 = 11 $\Rightarrow$ Restamos a la segunda fila 4 veces la primera

Paso 3

$\Rightarrow$ 12 = 1 · 11 + 1 $\Rightarrow$ 12 - 1 · 11 = 1 $\Rightarrow$ Restamos a la primera fila 1 veces la segunda

Paso 4

$\Rightarrow$ 11 = 11 · 1 + 0 $\Rightarrow$ 11 - 11 · 1 = 0 $\Rightarrow$ Restamos a la segunda fila 11 veces la primera

Paso 5

Por tanto

$mcd(189,12155)=1$

$u=1029$

Si $x_{0}$ es una solución de $ax\equiv1\ \pmod n$, entonces $x_{0}\cdot b$ es una solución de la ecuación $ax\equiv b\ \pmod n$. A partir de lo anterior tenemos que:

$1029\cdot7\pmod{12155}\equiv7203\pmod{12155}\equiv7203\pmod{12155}\Rightarrow x_{0}=7203\Rightarrow x\equiv7203,19358,31513,43668,55823,67978,80133\pmod{85085}$

Enlaces al fichero fuente y al pdf final de una posible compilación.

• Fichero en formato LyX con el código python necesario para hacerlo.
• Fichero en formato pdf que se obtiene como resultado de compilar el fichero anterior.