Congruencias lineales

Una congruencia lineal es una “ecuación” de la forma ax \equiv b \mod m. En general, pediremos que (a,m) =1, la razón para hacer esto tiene que ver con la unicidad de las soluciones.
Resolver esta congruencia equivale a resolver una ecuación diofantina asociada, la cual se obtiene como sigue:

ax \equiv b \mod m \iff m \mid (ax-b) \iff \exists y \in \mathbb{Z} \text{ tal que } ax-b = my

Lo anterior es equivalente a que la ecuación diofantina ax-my =b tenga solución en los enteros; que claramente es el caso si (a,m)=1.

Por ejemplo:
Si deseamos resolver 13x \equiv 5 \mod 77 entonces debemos considerar resolver la ecuación diofantina 13x-77y = 5; ustedes pueden verificar que las soluciones de la ecuación anterior son \{(x,y) \in \mathbb{Z}\times \mathbb{Z}\mid x = 30 + 77t;\ y = 5+13t; \ t \in \mathbb{Z}\} por lo que las soluciones a la congruencia deben ser x \equiv 30 \mod 77; noten que en realidad son una infinidad de enteros (todos de la forma 30 + 77t) pero que representan una única clase de congruencia.

About these ads
Esta entrada fue publicada en Uncategorized. Guarda el enlace permanente.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s