Clase 8

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Clase 8
Temario
1. Ecuación Diofántica
2. Ecuación de congruencia
3. Sistema de congruencias simultáneas.
Teorema: Condición necesaria y suficiente para que la ecuación 
diofántica ax + by = c tenga solución es que d = mcd(a, b) | c
 x0 = k * s = (c*s)/d
y0 = k * t = (c*t)/d.
Solución general:
x = x0 + k b/d
y = y0 - k a/d
Ecuación lineal de congruencia en una variable
Inverso de 7 en Z16 
7 *X =1 en Z16
7*x ≡ 1 mod 16
16|7x-1
7x-1=16y
7x-16y = 1 
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Encontrar una solución a la congruencia: -645x ≡2406 30
a.x ≡m b admite solución ⇔ 
Ecuación lineal de congruencia en una variable
Si a y m son primos relativos la congruencia ax≡b (mod m) siempre tiene 
soluciones, y todas las soluciones son congruentes módulo m
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m, x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod 
(mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod (mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod (mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod (mcd(a,m))
Ecuación lineal de congruencia en una variable
Lema: Sean a,m x0, n1,n2 ∈ Z y m ∈ Z
+ se tiene que x1 ≡m x2 ⇔ n1 ≡ n2 mod (mcd(a,m))
Sistema de congruencia simultáneas
Sistema de congruencia simultáneas
x≡a1 mod m1
x≡a2 mod m2
Sistema de congruencia simultáneas: Teorema 
Chino del resto
Ejemplo
x≡2 mod 3
x≡3 mod 5
x≡2 mod 7
Problemas
● mcd(a,b)
● mcm(a,b)
● ax+by=c
● ax ≡m b
● x ≡m1 a1
x ≡m2 a2
x ≡mn an