PDF de programación - El Algoritmo de Euclides

El Algoritmo de Euclides

Pablo L. De Nápoli

Departamento de Matemática

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

25 de abril de 2014

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

1 / 23

Parte I

El algoritmo de Euclides

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

2 / 23

El algoritmo de Euclides

El algoritmo de Euclides es un algoritmo para el cálculo del máximo común
divisor. Sean a, b ∈ N0. Para calcular mcd(a, b) podemos suponer a ≥ b
(sino intercambiamos los roles pues mcd(a, b) = mcd(b, a)

Efectuamos entonces la división entera de a por b obteniendo un primer
cociente q1 y un primer resto r1

a = q1b + r1

0 ≤ r1 < b

Si r1 = 0 el algorimo termina. Sino, dividimos a b por r1 obteniendo un
segundo cociente q2 y un segundo resto r2

b = q1r1 + r2

0 ≤ r2 < r1

Si r2 = 0 el algorimo termina. Sino, dividimos a r1 por r2 obteniendo un
tercer cociente q3 y un tercer resto r3

r1 = q2r2 + r3

0 ≤ r3 < r2

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

3 / 23

El algoritmo de Euclides (continuación)

Repitiendo (inductivamente) el procedimiento, supongamos que ya
calculamos rk . Si rk = 0 el algoritmo termina. Si no dividimos a rk−1 por
rk , obteniendo que

rk−1 = qk rk + rk+1

0 ≤ rk+1 < rk

Notamos que por construcción la sucesión de restos

r1 > r2 > r3 > . . .

es una sucesión de enteros no negativos estrictamente decreciente. Se
deduce que esta sucesión no puede continuar indefinidamente. En
consecuencia, siempre existe un N ∈ N tal que

es decir que el algoritmo de Euclides siempre termina.

rN = 0

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

4 / 23

El algoritmo de Euclides (continuación)

Teorema
El algoritmo de Euclides siempre termina y el último resto no nulo rN−1
que se obtiene es el máximo común divisor entre a y b.

Ejemplo: Calculemos el máximo común divisor entre 32 y 17 por el
algoritmo de Euclides:

32 = 1 * 17 + 15
17 = 1 * 15 + 2
15 = 7 * 2 + 1
2 = 2 * 1 + 0

El algoritmo de Euclides termina: El mcd entre 32 y 17 es 1.

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

5 / 23

El invariante del Algoritmo de Euclides

Para demostrar el teorema, usamos el siguiente lema que expresa un
invariante del algoritmo (una propiedad que se mantiene a lo largo de las
iteraciones del algoritmo.

Lema
Si efectuamos la división entera de a por b, obteniendo un cociente q y un
resto r , entonces

mcd(a, b) = mcd(b, r )

La prueba del lema es inmediata: si d es un divisor común entre a y b,
entonces d también divide a r = a − qb, en consecuencia d es un divisor
común entre b y r .

Recíprocamente si d divide a b y r , también dividirá a a pues a = bq + r .
Se deduce que b y r tienen los mismos divisores comunes que los que
tenían a y b, y en consecuencia tienen el mismo máximo común divisor.

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

6 / 23

Prueba de la correctitud del Algoritmo de Euclides

Usando el lema vemos que la sucesión de restos construida por el
algoritmo de Euclides, cumple que

mcd(a, b) = mcd(b, r1) = mcd(r1, r2) = mcd(r2, r3) = . . .

. . . = mcd(rN−2, rN−1) = mcd(rN−1, 0) = rN−1

(pues para cualquier entero c ∈ N0, mcd(c, 0) = c )
Es decir que hemos demostrado que el algoritmo de Euclides calcula
correctamente el máximo común divisor.

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

7 / 23

Programita recursivo (en Python 3) para el Algorimo de
Euclides

def mcd (a , b ):

if b > a :

return mcd (b , a )

if b ==0:

print ( " El a l g o r i t m o de E u c l i d e s termina : " )
print ( " El mcd es " ,a )
return a

else :

q , r = divmod (a , b )
print (a , " = " ,q , " * " ,b , " + " ,r )
return mcd (b , r )

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

8 / 23

Parte II

Una consecuencia del algoritmo de Euclides: El

máximo común divisor se escribe como

combinación lineal

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

9 / 23

El MCD como combinación lineal

Una consecuencia muy importante del algoritmo de Euclides es el siguiente
teorema:

Teorema
El máximo común divisor entre a y b se puede escribir como una
combinación lineal de ellos: es decir, existen enteros α = α(a, b) y
β = β(a, b) tales que

αa + βb = mcd(a, b)

El algoritmo de Euclides nos permite dar una prueba constructiva de este
teorema, construyendo las funciones α(a, b) y β(b, a) de manera recursiva.
De nuevo, podemos suponer a ≥ b.

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

10 / 23

Definiendo α(a, b) y β(a, b) recursivamente

Para encontrar la recurrencia, efectuamos la división entera de a por b,
obteniendo un cociente q = q(a, b) y un resto r = r (a, b), como antes.
Entonces por el invariante del algoritmo de Euclides sabemos que

mcd(a, b) = mcd(b, r )

Ahora supongamos que sabemos encontrar α(b, r ) y β(b, r ) tales que

Sustituyendo r = a − bq, encontramos que

α(b, r ) b + β(b, r ) r = mcd(b, r )

α(b, r ) b + β(b, r ) [a − bq] = mcd(b, r )

y efectuando la distributiva:

β(b, r ) a + (α(b, r ) − β(b, r )q)b = mcd(b, r )

Esto sugiere definir las funciones α y β recursivamente por:
β(a, b) = α(b, r ) − β(b, r )q

α(a, b) = β(b, r ),

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

11 / 23

Definiendo α(a, b) y β(a, b)(continuación)

Para que esta recurrencia funcione, debemos definir α y β cuando el
algoritmo de Euclides termina, es decir α(a, 0) y β(a, 0).

Queremos

α(a, 0) a + β(a, 0) 0 = mcd(a, 0) = a

Una manera de lograrlo es definiendo

α(a, 0) = 1

β(a, 0) = 0

(Esta elección es arbitraria, pero necesaria si querememos que β sea una
función bien definida)
Por inducción global en a ∈ N0, se prueba facilmente que α, β : D → Z
quedan bien definidas en el dominio

D = {(a, b) ∈ N0 × N0 : a ≥ b}

y que cumplen que:

α(a, b) a + β(a, b) b = mcd(a, b)

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

12 / 23

Ejemplo

Escribamos al mcd(32, 17) como combinación lineal entre ellos:

alfa( 1 , 0 )= 1, beta( 1 , 0 )= 0, mcd( 1 , 0 )= 1
1 = 1 * 1 + 0 * 0
alfa( 2 , 1 )= 0, beta( 2 , 1 )= 1, mcd( 2 , 1 )= 1
1 = 0 * 2 + 1 * 1
alfa( 15 , 2 )= 1, beta( 15 , 2 )= -7, mcd( 15 , 2 )= 1
1 = 1 * 15 + -7 * 2
alfa( 17 , 15 )= -7, beta( 17 , 15 )= 8, mcd( 17 , 15 )= 1
1 = -7 * 17 + 8 * 15
alfa( 32 , 17 )= 8, beta( 32 , 17 )= -15, mcd( 32 , 17 )= 1
1 = 8 * 32 + -15 * 17

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

13 / 23

Otro Ejemplo

Escribamos al mcd(360, 28) = 4 como combinación lineal entre ellos:

alfa( 4 , 0 )= 1, beta( 4 , 0 )= 0, mcd( 4 , 0 )= 4
4 = 1 * 4 + 0 * 0
alfa( 24 , 4 )= 0, beta( 24 , 4 )= 1, mcd( 24 , 4 )= 4
4 = 0 * 24 + 1 * 4
alfa( 28 , 24 )= 1, beta( 28 , 24 )= -1, mcd( 28 , 24 )= 4
4 = 1 * 28 + -1 * 24
alfa( 360 , 28 )= -1, beta( 360 , 28 )= 13, mcd( 360 , 28 )= 4
4 = -1 * 360 + 13 * 28

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

14 / 23

¿y el programita ?

Para implementar esto en un programa de computadora (en Python 3)
será conveniente en realidad implementar una funcion ecl que calcula la
terna

(α(a, b), β(a, b), mcd(a, b))

recursivamente (¡todo al mismo tiempo!), dado que las definiciones de α y
β no son independientes sino que están cruzadas.

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

15 / 23

Programa para el MCD como combinacion lineal

def ecl (a , b ):

if b > a :

return ecl (b , a )

if b ==0:

a l f a _ a _ b =1
b e t a _ a _ b =0
mcd_a_b = a

else :

q , r = divmod (a , b )
alfa_b_r , beta_b_r , mcd_b_r = ecl (b , r )
a l f a _ a _ b =
b e t a _ a _ b = a l f a _ b _ r - b e t a _ b _ r * q
mcd_a_b = mcd_b_r

b e t a _ b _ r

c h e q u e a _ i n v a r i a n t e (a ,b , alfa_a_b , beta_a_b , mcd_a_b )
return ( alfa_a_b , beta_a_b , mcd_a_b )

Pablo L. De Nápoli (Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires )

El Algoritmo de Euclides

25 de abril de 2014

16 / 23

Función que chequea el invariante del algoritmo

La condición

α(a, b) a + β(a, b) b = mcd(a, b)

es ahora el invariante del algoritmo. La siguiente función (en el sentido
informático del término), permite chequearla en cada paso. Es decir nos
ayuda a comprobar la correctitud de nuestro algoritmo:

def c h e q u e a _ i n v a r i a n t e (a ,b , alfa_a_b , beta_a_b , mcd_a_b ):

print ( "