También aquí remitimos a otras páginas para entender las condiciones de esta ecuación. En primer lugar has de conocer la teoría elemental de las congruencias o Aritmética modular. Si no es así, puedes visitar
http://hojamat.es/parra/modular.pdf
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html
Dentro de esta teoría uno de los primeros temas importantes es el de la resolución de la ecuación lineal AxºB (mod m) y lo traemos aquí por su relación con el algoritmo de Euclides. En efecto, la ecuación dada equivale a exigir que Ax y B se diferencien en un múltiplo de m, es decir, que Ax+Cm=B. Si leíste la entrada anterior, esto te recordará la Identidad de Bezout.
¿Qué sabes de la estructura de anillo? La repasaremos en la siguiente entrada de esta serie. Por ahora sólo tienes que recordar que en el Álgebra Elemental la ecuación Ax=B para números reales se resuelve multiplicando por el inverso de A, si es que lo posee (siendo distinto de cero en este caso), con lo que tendremos A-1Ax=1x=x=A-1B, que es una solución para x.
En los anillos en general no todo elemento posee un inverso, es decir, otro elemento que multiplicado por él lo convierta en la unidad (si esa unidad existe – ver http://es.wikipedia.org/wiki/Anillo_unitario).
En el caso de las congruencias, el anillo Zm de las clases de restos módulo m está formado por las clases {0,1,2,3,…m-1} a las que llamaremos restos, y en ellos existen algunos que pueden no tener inverso. Por ejemplo, si m=9 los elementos de Z9 son los restos {0,1,2,3,…8} y si elegimos el 6, ningún múltiplo de 6 produce un 1 como resto módulo 9. Veamos (haz tú los cálculos mentalmente para practicar):
6*1º6 (mod 9); 6*2º3 (mod 9); 6*3º0 (mod 9); 6*4º6 (mod 9); 6*5º3 (mod 9); 6*6º0 (mod 9); 6*7º6 (mod 9); 6*8º3 (mod 9)
Nunca resulta un producto congruente con 1, luego el 6 carece de inverso.
Si repasas la teoría del anillo Zm (lo haremos también en la siguiente entrada) descubrirás que los elementos inversibles son los números primos con m. Como estamos hablando del conjunto de restos {0,1,2,3,…m-1}, el número de inversibles coincidirá con la indicatriz de Euler, como también veremos más adelante. Ya ves, todo se relaciona.
En la resolución de A*xºB (mod m) se presentan estos tipos:
1. Si A es primo con m, existe una sola solución x º A-1*B (mod m), por ser A inversible.
2. Si MCD(A,m)=d, con d mayor que 1, para que exista solución ha de ser B múltiplo de d. En ese caso se simplifican los tres números A, B y m con lo que se pasa al primer caso. Se puede encontrar una primera solución º A-1*B (mod m) y existirán en total d soluciones, que vienen dadas por la fórmula xr = x0+r*m/d (ver las páginas recomendadas)
En la segunda hoja de la herramienta que estamos usando (Euclides.ods o Euclides.xlsx en
http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm) se sigue este procedimiento. Escribimos los tres datos A,B y m. Sin usar macros, la hoja determina si tiene solución o no y si en caso de tenerla es única o múltiple. Si existe, simplifica los datos.
En la imagen se intenta resolver 6Xº4 (mod 10), que tomaremos como ejemplo. La hoja detecta que existen varias soluciones y simplifica 6, 4, 10 a 3, 2 y 5.
El truco está en las celdas I9, I10 y J10. Investiga y aprenderás.
Abajo figura la resolución, que se basa en la rutina Euclides(X,Y) ya explicada en la entrada anterior y en ella se dan estos pasos:
- Se calculan las reducidas y se toma el penúltimo denominador DEN(5)=2, que es un buen candidato a inverso de A (ver la identidad de Bezout en la entrada anterior).
- Se comprueba el último producto cruzado NUM(6)*DEN(5)-DEN(6)*NUM(5)=3*2-1*5=1 y como vale 1, DEN(5)=2 es el inverso por ser 3*2º1 (mod 5. Si el producto cruzado hubiera valido -1 deberíamos haber cambiado de signo.
- Según hemos explicado, la solución será igual a INV(A)*B=2*2=4. En efecto, 6*4º4 (mod 10)
- El MCD(6,4)=2, luego existirán dos soluciones a la ecuación (hablamos en Z10, porque en Z existirían infinitas). Según la teoría, bastará ir sumando el cociente 10/2=5 a las soluciones, lo que nos da (lo ves en la imagen) las soluciones 4 y 9.
Caso homogéneo
Si B es cero, esta ecuación queda como A*x º 0 (mod m) por lo que además de la solución trivial x=0 existirán otras si M.C.D(A,m)>1, y entonces A se confirmará como divisor de cero. Por ejemplo, resuelve con la hoja 6*x º 0 (mod 9) y obtendrás las soluciones 0, 3 y 6, ya que M.C.D(6,9)=3>1. Sin embargo, resuelve 6*x º 0 (mod 7) y sólo obtendrás x=0, ya que en este caso 6 es inversible.
Te proponemos una demostración o comprobación, según te atrevas.
Las diferencias existentes entre las soluciones de la ecuación A*x º B (mod m) son soluciones de la homogénea A*x º 0 (mod m). Inversamente: dada una solución de A*xºB (mod m), si le vamos sumando por separado las soluciones de la homogénea, resulta el conjunto de todas las soluciones de A*x º B (mod m
Nuestro único objetivo ha sido el que veas la relación de la resolución de esta ecuación con el algoritmo de Euclides y que recorras toda la resolución efectuada por la hoja para comprender mejor los detalles de la misma. Cualquier otro aspecto lo podrás ver en las páginas recomendadas, aunque tampoco se puede decir mucho más.
No hay comentarios:
Publicar un comentario