25-8-2021 Ecuaciones Diofanticas-Algoritmo de Euclides

Vista previa del material en texto

Ecuaciones Diofanticas-Algoritmo de Euclides
Aux. I. Mamani
August 25, 2021
MAT-120 2-2021
Ejemplo.- Calcular el máximo comun divisor de b = 963 y c = 657
Sol.- Para esto identificamos el número mayor, en este caso b = 963, y lo dividimos por el menor que seria
c = 657 y calculamos su resto. Este seria el primer paso:
963 = 657︸︷︷︸
c
· 1 + 306︸︷︷︸
r1
(1)
Vemos que r1 < b. Luego dividimos c entre r1 calculando un nuevo resto. Este seria el segundo paso.
657︸︷︷︸
c
= 306︸︷︷︸
r1
· 2 + 45︸︷︷︸
r2
(2)
Podemos notar que r2 < r1. Ahora dividimos r1 entre r2 calculando un nuevo resto. Este seria el tercer paso.
306︸︷︷︸
r1
= 45︸︷︷︸
r2
· 6 + 36︸︷︷︸
r3
(3)
Observamos que r3 < r2. Ahora dividimos r2 entre r3 calculando un nuevo resto, este seria el cuarto paso.
45︸︷︷︸
r2
= 36︸︷︷︸
r3
· 1 + 9︸︷︷︸
r4
(4)
Al final se ve que r4 < r3. Ahora dividimos r3 entre r4 calculando un nuevo resto, este seria el cuarto paso.
36︸︷︷︸
r3
= 9︸︷︷︸
r4
· 4 + 0︸︷︷︸
r5
Si al hacer el proceso de division, encontramos un resto igual a 0 (en nuestro ejemplo r5 = 0), entonces ahí
finaliza el proceso. El máximo comun divisor entonces de los dos números es el ultimo anterior resto encontrado,
que en nuestro caso seria r4 = 9.
Ejemplo.- Expresar mcd(963, 657) como una combinacion lineal de dichos números.
Tenemos las ecuaciones (1)-(4) del anterior ejemplo, usemoslas para poder encontrar dicha combinacion lineal.
De (4) tenemos una forma equivalente
1
9 = 45− 36 · 1
De (3) tenemos que
36 = 306− 45 · 6 (a)
Reemplazemos (a) en (4), así tenemos
9 = 45− (306− 45 · 6) (b)
De (2) tenemos que
45 = 657− 306 · 2 (c)
Reemplazamos (c) en (b)
9 = (657− 306 · 2)− (306− (657− 306 · 2) · 6) (d)
De (1) tenemos que
306 = 963− 657(e)
Reemplazamos (e) en (d)
9 = (657− (963− 657) · 2)− (963− 657− (657− (963− 657) · 2) · 6)
Al final tenemos,
9 = 657− 2 · 963 + 2 · 657− 963 + 657 + 6 · 657− 12 · 963 + 12 · 657
22 · 657 + (−15) · 963 = 9
Ejemplo.- Encontrar el máximo comun divisor de a = 252 y b = −180.
Sol.- Para esto recordemos la siguiente propiedad.
mcd (a, b) =mcd (−a, b) =mcd (a,−b) =mcd (−a,−b)
Por lo que podemo calcular el mcd(a,−b) y a la vez estariamos calculando el mcd(a, b). Ahora usemos el
algoritmo de Euclides con a = 252 y −b = 180. Como a > b por el algoritmo de la division tenemos como primer
paso
252 = 180︸︷︷︸
−b
· 1 + 72︸︷︷︸
r1
(1)
2
Vemos que r1 < b. Luego dividimos b entre r1 calculando un nuevo resto. Este seria el segundo paso.
180︸︷︷︸
b
= 72︸︷︷︸
r1
· 2 + 36︸︷︷︸
r2
(2)
Podemos notar que r2 < r1. Ahora dividimos r1 entre r2 calculando un nuevo resto. Este seria el tercer paso.
72︸︷︷︸
r1
= 36︸︷︷︸
r2
· 2 + 0︸︷︷︸
r3
Como en el anterior ejercicio, si al hacer el proceso de division, encontramos un resto igual a 0 (en este ejemplo
r3 = 0), entonces ahí finaliza el proceso. El máximo comun divisor entonces de los dos números es el ultimo anterior
resto encontrado, que en nuestro caso seria r2 = 36.
Ejemplo.- Expresar el mcd(252,−180) como combinacion lineal de 252 y −180.
Sol.- Tenemos las ecuaciones (1) y (2) del anterior ejemplo. Tratemos la ecuacion (2) notando que
36 = 180− 72 · 2 (a)
Por otro lado de (1) tenemos que
72 = 252− 180 · 1 (b)
Reemplazando (b) en (a) tenemos
36 = 180− (252− 180 · 1) · 2
Que es igual a
36 = 180− 252 · 2− 180 · 2
36 = 180 · 3− 252 · 2
Así tenemos
−180 · (−3) + 252 · (−2) = 36
la cual es la respuesta a nuestro problema
Ejemplo.- En el siguiente ejercicio encontrar x e y tales que se cumpla la siguiente igualdad
145x + 58y = 87
Sol.- ¿Tiene sentido esta ecuacion diofantica? Si deseamos saber si tiene solucion o no, debemos calcular el
máximo comun divisor de los coeficientes que acompañan a su respectiva variable, el cual en nuestro caso serian los
números 145 y 58. Primero calculamos el mcd(145, 58) utilizando el algoritmo de Euclides.
Tenemos así, que:
3
145 = 58︸︷︷︸
b
· 2 + 29︸︷︷︸
r1
(1)
Por otro lado tambien tenemos que
58 = 29︸︷︷︸
r1
· 2 + 0︸︷︷︸
r2
Como ya encontramos un resto que es igual 0, el cual es r2,entonces el mcd(145, 58) es 29, que seria el último
anterior resto no nulo encontrado. Como 29 | 87 entonces esta ecuacion diofantina si tiene soluciones enteras.
De (1), no es dificil encontrar números enteros que satisfagan la ecuacion, así, tenemo que
29 = 145 + (−2) · 58
A esta última ecuacion, multiplicamos ambos lados por 3,así obtenemos
29 · 3 = 145 · 3 + (−6) · 58
87 = 145 · 3 + (−6) · 58
Entonces una solucion a nuestra ecuacion diofantina es x = 3 y y = −6
Ejercicio.- Demostrar que si a = qb + r entonces mcd(a, b) =mcd(b, r)
Dem.- Sea m =mcd(a, b) y n =mcd(b, r)
Entonces b = mx y a = my, de lo que se sigue que my − qmx = r, vale decir que m | r. Como m | b y m | r se
sigue que m ≤ n.
Por otro lado, como n =mcd(b, r) entonces r = nz y b = nw, de lo que se sigue que a = qnw + nz, de donde se
sigue que n | a. Como n | a y n | b entonces se sigue que n ≤ m. De aqui se infiere que m = n.
Teorema 1.- Si a1, a2, ..., an son enteros positivos con n ≥ 3, entonces
mcd(a1, a2, ..., an) =mcd(mcd (a1, ..., an−1) , an)
Ejemplo.- Encontrar el máximo comun divisor de los números indicados usando el algorítmo de Euclides:
mcd(624, 504, 90)
Sol.- Para resolver este ejercicio hacemos uso del teorema 1 de la siguiente manera
mcd(624, 504, 90) =mcd(mcd (624, 504) , 90)
Ahora sí podemos usar el algoritmo de Euclides para calcular mcd
 624︸︷︷︸
a
, 504︸︷︷︸
b
.
624︸︷︷︸
a
= 504︸︷︷︸
b
· 1 + 120︸︷︷︸
r1
(1)
4
Como r1 6= 0 continuamos el proceso.
504︸︷︷︸
b
= 120︸︷︷︸
r1
· 4 + 24︸︷︷︸
r2
(2)
r2 6= 0, por lo que
120︸︷︷︸
r1
= 24︸︷︷︸
r2
· 5 + 0︸︷︷︸
r3
Entonces, como ya encontramos un resto nulo, que en nuestro caso es r3, el máximo comun divisor de ambos
números es el ultimo anterior resto de r3, el cual debe ser no nulo. En este caso seria r2 = 24 Así, mcd
 624︸︷︷︸
a
, 504︸︷︷︸
b
 =
24 .
El siguiente paso consiste ahora en calcular el mcd (mcd (624, 504) , 90) = mcd
 24︸︷︷︸
d
, 90︸︷︷︸
c
. Para esto hacemos
uso del algoritmo de Euclides. Así, por el algoritmo de la division tenemos que
90︸︷︷︸
c
= 24︸︷︷︸
d
· 3 + 18︸︷︷︸
r1
(3)
24︸︷︷︸
d
= 18︸︷︷︸
r1
· 1 + 6︸︷︷︸
r2
(4)
18︸︷︷︸
r1
= 6︸︷︷︸
r2
· 3 + 0︸︷︷︸
r3
Entonces, como ya encontramos un resto nulo, que en nuestro caso es r3, el máximo comun divisor de ambos
números es el ultimo anterior resto de r3, el cual debe ser no nulo. En este caso seria r2 = 6. Por lo que
mcd(624, 504, 90) = 6
2.- Expresar mcd(624, 504, 90) como una combinacion lineal de estos números.
Sol.- Tenemos las ecuaciones (1)-(4) del anterior ejemplo. Así tenemos que mcd (mcd (624, 504) , 90) =
mcd
 24︸︷︷︸
d
, 90︸︷︷︸
c
 y mcd
 24︸︷︷︸
d
, 90︸︷︷︸
c
 = 6. Primero expresamos 6 como combinacion lineal de 24 y 90. Gra-
cias a (4) tenemos que
6 = 24 + (−1) · 18 (a)
De (3) tenemos que
18 = 90 + (−3) · 24 (b)
Reemplazamos (b) en (a), así tenemos:
5
6 = 24 + (−1) · (90 + (−3) · 24)
6 = 4 · 24 + (−1) · 90 (*)
Ahora expresemos mcd (624, 504) = 24 como una combinacion lineal de estos números. Para esto de (2) obten-
emos que
24 = 504 + (−4) · 120 (c)
De (1) tenemos que
120 = 624 + (−1) · 504 (d)
Reemplazamos (d) en (c)
24 = 504 + (−4) · (624 + (−1) · 504)
24 = 5 · 504 + (−4) · 624 (**)
Reemplazando (**) en (*) obtenemos
6 = 4 · (5 · 504 + (−4) · 624) + (−1) · 90
6 = 20 · 504 + (−16) · 624 + (−1) · 90
Esa seria la respuesta a nuestro problema
3.- Encontrar x, y y z tales que cada enunciado se cumpla
9 = 6x + 3y + 15z
Sol.- Para resolver este ejercicio debemos calcular en primer lugar mcd (6, 3, 15). En este caso, no es dificil
calcularlo de manera directa
mcd (6, 3, 15) = mcd(mcd (6, 3) , 15)=mcd (3, 15) = 3
Tampoco es dificil expresar 3 como combinacion lineal de 3 y 15
3 = 15 + (−4) · 3 (1)
Tambien podemos expresar 3 como combinacion lineal de 6 y 3
3 = 6 + (−1) · 3 (2)
Reemplazando (2) en (1)
6
3 = 15 + (−4) · (6 + (−1) · 3)
3 = 15 + (−4) · 6 + 4 · 3 (*)
A (*) lo multiplicamos por 3 y asi obtenemos
9 = 3 · 15 + (−12) · 6 + 12 · 3
5.-¿Tiene la siguiente ecuacion diofantica soluciones en los enteros?
1 = 21w + 9x + 3y + 6z
Sol.- Factorizando un factor comun de cada coeficiente de la ecuacion diofantica obtenemos que
1 = 3 · (7w + 3x + y + 2z)
Encontrando una contradiccion.
6.- Determinar todas las soluciones enteras a la ecuacion
58x− 87y = 290
Sol.- Para resolver este problema primero calculamos mcd (58, 87). No es dificil encontrar que mcd (58, 87) = 29,
tampoco lo es determinar una combinacion lineal para poder encontrar enteros u, v tales que
58u + 87v = 29
En nuestro caso, una solucion particular a esta ecuacion diofantinca es u = −1 y v = 1
58 (−1) + 87 · 1 = 29 (1)
Multiplicando ambos lados de (1) tenemos que
58 (−10) + 87 · 10 = 290
O tambien
58 (−10) + (−87) · (−10) = 290 (2)
Por lo que, una solucion particular de (2) seria x0 = −10 y y0 = −10. La solucion general tendria la forma:
x = x0 + bg t y x = y0 −
a
g t
que en nuestro caso seria, con a = 58 y b = −87 y g = mcd (58, 87)
x = −10 + (−87)29 t y x = −10−
58
29 t
7