Ecuaciones diofánticas

Instituto O’Higgins
Departamento de
´
Matematicas

Exposici´n:
o
Algoritmo de euclides y
Ecuaciones Diof´nticas
a
Juan Narv´ez
a

2 ALGORITMO DE EUCLIDES

1.

Introducci´n
o

Diofanto de Alejandr´ (griego antiguo: Di´phantos ho Alexandre´s), nacido alrededor del
ıa
o
u
200/214 y fallecido alrededor de 284/298, fue un antiguo matem´tico griego. Es considerado “el
a
padredel algebra”.
´
Se llama ecuaci´n diof´ntica a cualquier ecuaci´n algebraica, generalmente de varias variables,
o
a
o
planteada sobre el conjunto de los n´meros enteros o los n´meros naturales , es decir, se trata de
u
u
ecuaciones cuyas soluciones son n´meros enteros1 .
u
En nuestro caso estudiaremos las ecuaciones diof´nticas de la forma
a
ax + by = c
donde a, b y c son n´merosenteros, y buscamos las parejas de enteros x e y que cumplen esta
u
igualdad.
En este apunte estudiaremos un m´todo para resolver ecuaciones de esta naturaleza utilizando los
e
conocimientos de ense˜anza media. Ser´ de suma importancia conocer el algor´
n
a
ıtmo de Euclides
antes de comenzar con la resoluci´n de ecuaciones.
o

2.

Algoritmo de Euclides

Este algoritmo permiteencontrar el m´ximo com´n divisor entre dos n´meros enteros.
a
u
u
Dados dos n´meros a y b enteros, es posible encontrar otros dos enteros q y r tales que
u
a = bq + r.
Es claro que los t´rminos q y r corresponden al cociente y resto de la divisi´n a : b. Entonces usaree
o
mos s´lo los conocimientos de suma, resta y multiplicaci´n para aplicar este algoritmo sin necesidad
o
o
de dividir.Haciendo este procedimiento repetidas veces nos encontraremos con el MCD(a, b).

2.1.

Procedimiento

Sin p´rdida de la generalidad, supongamos que a > b. Entonces existen q1 y r1 enteros, tales
e
que
a = q1 b + r1
Si r1 = 0 hemos terminado el proceso y entonces b es el MCD entre a y b.
Si r1 = 0 entonces existen q2 y r2 enteros, tales que
b = q2 r1 + r2
Ahora si r2 = 0 hemos terminado elproceso y entonces r1 es el MCD entre a y b.
Si r2 = 0 entonces existen q3 y r3 enteros, tales que
r1 = q3 r2 + r3
1

Referencia de Wikipedia

2
CERMACH-2011

2.1 Procedimiento

2 ALGORITMO DE EUCLIDES

Si r3 = 0 hemos terminado el proceso y entonces r2 es el MCD entre a y b.
Si r3 = 0 entonces se repite el proceso con q4 y r4 .
Seguiremos as´ hasta que alg´n rk = 0 y entonces elMCD entre a y b ser´ rk−1 .
ı
u
a
Para la siguiente parte llamaremos d al MCD(a, b). Entonces nos centramos en encontrar p y q
enteros, tales que2
ap + bq = d.
Como d = rk−1 entonces se cumplir´ que
a
a = q1 b + r1
b = q2 r1 + r2
r1 = q3 r2 + r3
r2 = q4 r3 + r4
.
.
.
rk−4 = qk−2 rk−3 + rk−2
rk−3 = qk−1 rk−2 + rk−1 = qk−1 rk−2 + d
rk−2 = qk rk−1 + rk = qk d + 0
Ahora vamos ahacer un procedimiento similar, pero en sentido inverso, partiendo por
∧

rk−3 = qk−1 rk−2 + d

rk−4 = qk−2 rk−3 + rk−2

Entonces tenemos que
d = rk−3 − qk−1 rk−2 ⇒ d = rk−3 − qk−1 (rk−4 − qk−2 rk−3 )
As´ sucesivamente vamos despejando rk−1 usando la ecuaci´n anterior, luego rk , etc. Finalmente
ı
o
obtendremos la expresi´n ap + bq = d.
o
Para comprender mejor este procedimiento veamosel siguiente
Ejemplo 2.1 Calculemos el MCD entre a = 18 y b = 46. Primero podemos ver que
46 = 2 · 18 + 10
18 = 1 · 10 + 8
10 = 1 · 8 + 2
8=4·2
Por lo tanto el ultimo resto no nulo es esl MCD, en este caso el 2.
´
Ahora veremos el proceso inverso para encontrar los p y q.
10 = 1 · 8 + 2
2 = 10 − 1 · 8
2 = 10 − 1 · (18 − 1 · 10) = −1 · 18 + 2 · 10
2 = −1 · 18 + 2 · (46 − 2 · 18) = −5 ·18 + 2 · 46
Lo que significa que entonces p = −5 y q = 2.
2

Mas adelante veremos que estos n´meros son fundamentales para resolver una ecuaci´n diof´ntica.
u
o
a

3
CERMACH-2011

´
3 ECUACIONES DIOFANTICAS

3.

Ecuaciones Diof´nticas
a

Definici´n 3.1 Una ecuaci´n diof´ntica es una ecuaci´n de dos inc´gnitas con coeficientes eno
o
a
o
o
teros, y que solo exige soluciones...