Ecuaciones de congruencias lineales

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 donde x0 es una solución particular de la ecuación diofántica ax + my = b.

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.

Sistemas de congruencias: el teorema chino del resto

El sistema de congruencias:

x c1 (mod m1)

xc2 (mod m2)

............

xcr (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.

Correr aplicación Resolución de sistemas de ecuaciones de congruencias


Anterior Arriba Siguiente