IMD-IS 2011–2012. Sesión de laboratorio 4. El algoritmo de Euclides La hoja de SAGE que corresponde a la práctica puede obtenerse de: http: // personal. us. es/ ebriand/ practica4. sws En esta práctica estudiamos algunos aspectos del algoritmo de Euclides para hallar el Mcd de dos enteros.

La división euclídea En SAGE, el resto en la división de a por b con b > 0 se obtiene con: a %b, y el cociente, con a//b. Por ejemplo:

341//23 14

Figura 1: Euclides de Alejandria.

341%23 19 En efecto, la división euclídea de 341 entre 23 es: 341 = 14 × 23 + 19. Podemos obtener el cociente y el resto de una división euclídea a la vez, con el comando quo_rem:

(q,r)=341.quo_rem(23) print q,r 14 19 Ejercicio 1. Calcular, primero a mano y luego comprobando con SAGE, el cociente y el resto en: la división de −341 entre 23. la división de 341 entre −23. la división de −341 entre −23. Lo que da SAGE, ¿ Corresponde bien a la definición de división euclídea en todos los casos ?

Algoritmo de Euclides Recordamos en un ejemplo el funcionamiento del algoritmo de Euclides, que calcula el Mcd de dos enteros a y b. Aquí a = 1482, b = 517 y se obtiene 1 como Mcd. 1483 = 2 × 517 + 449, 517 = 1 × 449 + 68, 449 = 6 × 68 + 41, 68 = 1 × 41 + 27, 41 = 1 × 27 + 14, 27 = 1 × 14 + 13, 14 = 1 × 13 + 1, 13 = 13 × 1 + 0,

por lo tanto Mcd(1483, 517) = Mcd(517, 449) por lo tanto Mcd(517, 449) = Mcd(449, 68) por lo tanto Mcd(449, 68) = Mcd(68, 41) por lo tanto Mcd(68, 41) = Mcd(41, 27) por lo tanto Mcd(41, 27) = Mcd(27, 14) por lo tanto Mcd(27, 14) = Mcd(14, 13) por lo tanto Mcd(14, 13) = Mcd(13, 1) por lo tanto Mcd(13, 1) = Mcd(1, 0).

Como quotient y remainder.

2

La función siguiente implementa el algoritmo de Euclides para a y b (se supone que b > 0) y además imprime la sucesión de los restos.

def euclides(a,b): (penultimoResto,ultimoResto)=(a,b) while not (ultimoResto == 0): print penultimoResto (penultimoResto,ultimoResto)=(ultimoResto, penultimoResto % ultimoResto) return penultimoResto Explicación: cada etapa del algoritmo de Euclides consiste en dividir el penultimo resto por el ultimo resto. Esto produce un nuevo resto. Luego se cambian los papeles: El nuevo resto pasa a llamarse “ultimo resto” y al mismo tiempo, lo que era el “ultimo resto” pasa a llamarse “penultimo resto”. Ejercicio 2. Utilizar esta función euclides para calcular los Mcd y los mcm de los pares de enteros siguientes: 729 y 243. 729 y 512. 210 + 1 y 310 + 1 21000 + 1 y 31000 + 1. Calcular también esta función los Mcd de dos enteros aleatorios de N cifras para N = 100, N = 1000, N = 10000 . . . hasta que el ordenador tarde un poco (digamos unos segundos). ¿ Es eficiente el algoritmo de Euclides ? Para producir un entero entre p y q se utiliza randint(p,q). Para producir un entero de N cifras (es decir entre 10 N y 10 N +1 ) se utiliza por lo tanto randint(10^N,10^(N+1)).

Pares de números coprimos Recordamos que dos enteros a y b son coprimos si su Mcd vale 1. Si elegimos dos enteros aleatoriamente ¿ es muy probable que sean coprimos ? Queremos evaluar la probabilidad que dos enteros sean coprimos. Para esto, construimos M pares de enteros ( a, b) entre 1 y N (M es el tamaño de la muestra, N es el valor máximo de los enteros), calculamos el Mcd de cada par ( a, b) y contamos los Mcd iguales a 1. La proporción de pares coprimos de la muestra estima la proporción de pares de enteros inferiores o igual a N que son coprimos. El bucle siguiente realiza este plan:

El mcm de a y b se deduce de su Mcd gracias a la relación: Mcd( a, b) × mcm( a, b) = a × b.

3

N=100 ## valor maximo para a y b c=0 ## contador de pares coprimos M=10000 ## tamaño de la muestra for i in [1..M]: a=randint(1,N) b=randint(1,N) d=euclides(a,b) if d == 1: c=c+1 print float(c/M) ## proporción de pares coprimos Ejercicio 3. Ejecutar el bucle varias veces, con valoes más y más grandes de N. ¿ Se observa alguna tendencia ? Jugamos al juego siguiente: elegimos dos grandes enteros aleatoriamente. Si son coprimos, pierdes un euro. Si no, ganas un euro. ¿ Jugarías unos cien partidos ?

El algoritmo de Euclides extendido Recordamos en un ejemplo el algoritmo de Euclides extendido, que calcula el Mcd de dos enetros a y b y al mismo tiempo una identidad de Bézout para a y b, es decir una descomposición de Mcd( a, b) de la forma xa + yb. División

Aislar el nuevo resto

1483 = 2 × 517 + 449 449 = 1483 − 2 × 517 517 = 1 × 449 + 68 68 = 517 − 449 449 = 6 × 68 + 41 41 = 449 − 6 × 68 68 = 1 × 41 + 27 27 = 68 − 41 41 = 1 × 27 + 14 14 = 41 − 27 27 = 1 × 14 + 13 13 = 27 − 14 14 = 1 × 13 + 1 1 = 14 − 13 13 = 13 × 1 + 0

Sustituir

Simplificar

= a−2b = b − ( a − 2b) = ( a − 2b) − 6(3b − a) = (3b − a) − (7a − 20b) = (7a − 20b) − (−8a + 23b) = (−8a + 23b) − (15a − 43b) = (15a − 43b) − (−23a + 66b)

= − a + 3b = 7a − 20b = −8a + 23b = 15a − 43b = −23a + 66b = 38a − 109b

La identidad de Bézout obtenida es: 1 = 38a − 109b. A cada etapa del algoritmo se ha obtenido una descomposición del ultimo resto como combinación lineal de a y b. Las descomposisiones del ultimo resto y del penultimo resto sirven para calcular la descomposición del ultimo resto. Ejercicio 4. Programar el algoritmo de Euclides extendido, de manera que devuelva, en vez de solamente el Mcd de a y b, también los coeficientes x e y en la identidad de Bézout Mcd( a, b) = xa + yb. Utilizar esta función para calular identidades de Bézout para los pares de enteros del ejercicio 2. Comprobar, en todas las identidades de Bézout obtenidas, que | x | < | b | e | y | < | a |. Indicaciones: en el algoritmo de Euclides “simple” en cada paso

4

considerabamos un par: (penultimoResto,ultimoResto)

que se modifica a cada paso. Aquí necesitaremos considerar una familia de 6 números: (penultimoResto,penultimo_x, penultimo_y,ultimoResto, ultimo_x, ultimo_y)

que se modifica a cada paso, y tal que:

penultimoResto = penultimo_x · a ultimoResto = ultimo_x · a

+ penultimo_y · b, + ultimo_y · b

El teorema de Euclides (por si haz acabado todo lo anterior) En teoría hemos demostrado que hay una infinidad de números primos (el “Teorema de Euclides”), produciendo una sucesión infinita de primos distintos. Esta sucesión es definida recursivamente por las condiciones siguientes: p1 = 2 para cualquier n ≥ 2, pn es el menor factor primo del entero p1 p2 · · · pn−1 + 1. Este algoritmo esta implementado en SAGE por la función siguiente:

def DemoDeEuclides(N): res=[] producto=1 for i in [1..N]: n=producto+1 factores=n.prime_factors() p=factores[0] producto=producto*p res.append(p) return res

# Lista de los divisores primos de n, en orden creciente # El primer elemento de esta lista. Es el menor divisor prim

Ejercicio 5. Obtener los primeros números primos producidos de esta manera, hasta obtener por lo menos 2, 3, 5, 7 y 11. ¿ Vienen en orden ?

La criba de Eratostenes La función siguiente devuelve la lista de los números primos p inferiores o igual a N, por medio del criba de Eratistenes.

def criba(N): L=[2..N] res=[]

Figura 2: Eratóstenes.

5

while L[]: p=L[0] res.append(p) for x in L: if x%p == 0: L.remove(x) return res

## seleccionamos el primer elemento ## Lo ponemos en la lista-resultado ## quitamos de L todos sus multiplós

Ejercicio 6. Utilizarla para contar los primos inferiores a N = 100, N = 1000, y N = 10 000 (la longitud de una lista L se obtiene con len(L)). Comprobar en cada caso que una buena estimación de este número viene dada por N/ log( N ), y que una aproximación aún mejor viene dado por: Z N 1 dt 2 log( t ) La integral del ejercicio se calcula de la manera siguiente con SAGE:

var('t') numerical_integral(1/log(t),2,N) La función devuelve dos números: el primero es una aproximación del valor del integral, el segundo es una cota del error.