Resolución de sistemas de ecuaciones de congruencias
Una congruencia de la forma:
ax ≡ b (mod m) |
donde m es un entero positivo, a y b son números enteros y x es una variable entera, se llama congruencia lineal o ecuación de congruencia lineal (lineal por aparecer la variable x como potencia de grado uno, únicamente).
Resolver esta ecuación consiste (como en el caso de la aritmética entera) en encontrar todos los enteros x que satisfagan la ecuación diofántica equivalente ax+my=b.
En el caso de Zm, la ecuación tendrá solución si y solo si mcd(a,m)|b , y en este caso tendrá exactamente d=mcd(a,m) soluciones distintas en Zm de la forma:
| x= x0 + (m.t)/d , t=0,1,2,...,d-1 |
En el apartado dedicado al algoritmo de Euclides se indica como puede utilizarse este algoritmo para calcular una solución particular de una ecuación diofántica.
El sistema de congruencias:
x ≡ c1 (mod m1)
x ≡ c2 (mod m2)
............
x ≡ cr (mod mr)
donde mcd(mi,mj)=1 para todo i , j distintos, tiene solución única en Zm1.m2...mr (es decir, hay una única solución x para 0<x<m y todas las demás soluciones válidas son congruentes con x)
Esta solución se construye de la siguiente forma:
Sea Mk = (m1.m2...mk...mr) / mk = m1.m2...mk-1.mk+1...mr
Como los mi son primos entre sí, es claro que mcd (Mk,mk) = 1. Por lo tanto Mk tendrá un inverso módulo mk. A este inverso le llamamos yk. Entonces
| x0 = c1M1y1 + c2M2y2 + ... + crMryr |
es solución del sistema inicial anterior. La solución general del sistema será x ≡ x0 (mod m1m2...mr)
El applet que figura a continuación permite resolver sistemas de congruencias de entre 2 y 6 ecuaciones, utilizando los resultados del teorema chino del resto.
|
Resolución de sistemas de ecuaciones de congruencias
|
 |
 |
 |
| Anterior | Arriba | Siguiente |