Reporte 1: Algoritmo euclidiano.

El Algoritmo euclidiano es un algoritmo eficiente y popular para hallar el máximo común divisor de dos enteros.

El máximo común divisor de dos enteros (positivos y no sean 0) es el entero positivo más grande que divide a estos dos números, sin tener un residuo. Esto se utiliza, por ejemplo, para simplificar fracciones.

En la escuela nos enseñan un metodo para calcular el MCD, es descomponiendo los dos números en factores primos, esto quiere decir, sacando mitades o tercias etc...., luego marcamos cuando sean comunes divisores y estos al final se multiplican, esto es, por ejemplo:

Cuando nosotros dividimos entre a y b(números enteros positivos), nos dará como un resultados un cociente q y un residuo r, entonces como sabemos, r = a % b, por lo tanto mcd(a,b) = mcd(b,r); por ejemplo:

• Como 18 % 12 = 6, utilizando mcd(a,b) = mcd(b,r):
• mcd(18,12) = mcd(12,6)
• Como 60 % 48 = 12, utilizando mcd(a,b) = mcd(b,r):
• mcd(60,48) = mcd(48,12)

Algo importante que debemos considerar es que para obtener el MCD correcto tenemos que sacar el residuo dividiendo el mas grande entre el mas pequeño.

Considerando también que el máximo común divisor de cualquier numero y 0 es ese mismo numero, esto quiere decir:

• Como 80 % 40 = 0, utilizando mcd(a,b) = mcd(b,r):
• mcd(80,40) = mcd(40,0) = 40

Podemos ver que los resultados que obtuvimos con nuestro metodo que vimos en la escuela y el algoritmo euclidiano, en ambos obtuvimos el máximo común divisor.

Si a es un entero no negativo, b es un entero positivo y r = a mod b, entonces mcd(a,b) = mcd(b,r), decimos que, por el teorema de cociente-residuo: a = bq + r  y  0 <= r < b, este teorema es demostrado, donde a y b son los números dados, q es el cociente, r es el residuo.

El pseudocódigo de este algoritmo lo hice de esta manera:

Teniendo como entrada dos enteros no negativos, diferentes a cero y obteniendo como salida, el máximo común divisor de ellos.

El Diagrama de flujo para este algoritmo, es el siguiente:

Hay que notar se en este procedimiento utilizo las funciones XOR para intercambiar los datos dados por si en alguna ocasión se ingresa el menor y el mayor invertidos, también ver que los valores en el bucle while (mientras), se van actualizando con valores cada vez mas chicos, hasta que en algún momento b se vuelve 0, cuando en este punto mcd(a,0) por lo tanto es igual a a, que es el mcd.

Ahora mostraré como funciona por pasos este algoritmo en diferentes ocasiones.

Sean a = 48 y b = 60, entra a la condición ya que 48 < 60, pasamos a la siguiente linea numero 3 en donde con 3 XOR intercambio el orden para que a sea 60 y b sea 48, se hace lo siguiente.

• a = 48 XOR 60
• a = 12
• b = 12 XOR 60
• b = 48
• a = 12 XOR 48
• a = 60

Ahora estamos preparados para entrar el mientras, como b != 0, se hace lo siguiente.

• r = 60 % 48
• a = b
• a = 48
• b = r
• b = 12

Volvemos a entrar a el mientras y tenemos.

• r = 48 % 12
• a = b
• a = 12
• b = r
• b = 0

No entra al mientras y vamos a la linea 13 en donde regresa a a, que viene siendo el correcto MCD.

Hice un programa pequeño en C,  implementando el algoritmo:

Bibliografia:

MATEMATICAS DISCRETAS. Sexta edición.

Johnsonbaugh, Richard

PEARSON EDUCACION, México, 2005

Área: Universitarios.

PD. es el libro que utilizamos en la materia de Mates discretas, la pagina donde viene esta información es en la 205. Lo pueden conseguir en google books. en este link