Resolviendo Congruencias

Ejemplo.

, tendrá solución?

como , tiene inverso mult. módulo ,
Mult. por tenemos

Ent. es solución de .
Observamos que también, más allá, cualquier es solución:
Además, si es solución, ent. .
También . Entonces, , y por tanto,

Consideremos con . Ent. la congruencia

tiene solución. Una solución es , ya que como existe y mult por …;

Observación.

Sean la congruencia

tiene solución si y sólo si y cualesquiera dos soluciones son congruentes módulo .

Proof. Se debe a que es solución si y sólo si es un inverso de módulo .

Proposición 1.

Sean . Si , entonces la congruencia

tiene solución y cualesquiera dos soluciones son congruentes módulo .

Proof.

Sean
Como existe un inverso de módulo que denotamos por . Veamos que es solución de .
Como , multiplicando por

Así, es una solución de .
Sean soluciones de . Entonces

Así, . Como podemos cancelar y obtenemos que . Q.E.D.

Ejemplos.

1. 
   Buscamos un inverso de módulo

Asį y existe un inverso de módulo . Además,

Ent. es un inverso de mód .
Solución:

2. 
   Calculamos

Así, y además,

Ent. es un inv. de mod. . Multiplicando,

Solución.

Teorema.

Sean La congruencia

tiene solución si y sólo si .

Proof.

Sean
Supongamos que la congruencia tiene solución. Existe entonces tal que . Así o bien existe tal que . Tenemos entonces que

Como y , entonces

Supongamos que . Por el algoritmo de Euclides existen tales que

Como , entonces con .
Mult. por .

Así, y por lo tanto

Concluimos que es una solución de .

Observación.

Consideremos con , es solución de si y sólo si es solución de

Proof. Sup. que es solución de . Entonces y así con . Dividiendo entre tenemos

Así,

Supongamos ahora que es solución de

entonces.

Tenemos entonces que con . Multiplicando por , y así

Ejemplo.

, y tiene solución.
Por la obs. de las soluciones de son las mismas que las de .
Tenemos que
Solución de o bien

Pero módulo y son soluciones distintas.
Solución de con .

Teorema.

Sean con . La congruencia tiene soluciones distintas módulo , que son

con una solución particular de

Proof.

Sean
Denotemos por y por .
Veamos que los números de la lista son solución de .
Sea una solución de y por la observaición de .
Veamos ahora que los números de la lista son distintos módulo .
Sea con . Supongamos que

entonces
y así con . Entonces
y por tanto . Pero como sabemos que . Así y entonces .
Veamos ahora que toda soluci’on de es de esa forma.
Sea una solución de . Por la observación, también es solución de y entonces
Así,

Por el algritmo de la división.

Así,

Example

Teorema. (Teorema Chino de Residuo)

Sean con . Las congruencias

tienen una solución común y ésta es única módulo .

Proof.

Observación.

Una solución común de y , , es

Proof. De la prueba anterior sabemos que

Nota!

Generalizando, sean tales que . Una solución común de

es

con y
La solución es única módulo .