Question

EJEMPLOS DEL ALGORITMO DE EUCLIDES

Answer 1

4.1. Algoritmo de Euclides. El máximo común divisor de dos enteros puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay un proceso más eficiente que utiliza repetidamente el algoritmo de la división. Este método se llama algoritmo de Euclides. El algoritmo de Euclides se describe de la forma siguiente: dados dos enteros a y b, cuyo máximo común divisor se desea hallar, y asumiendo que a b > 0, (El método funciona también si a y b son negativos. Basta trabajar con los valores absolutos de estos números, debido a que M.C.D(| a |, | b |) = M.C.D (a,b)) se siguen los siguientes pasos: a) Se usa el algoritmo de la división para obtener b + con < b. Si = 0, entonces, b|a y M.C.D.(a, b) = b. b) Si se divide b por y se producen enteros y que satisfacen b = + con . Si = 0 el proceso termina y M.C.D.(a, b) = . c) Si se procede a dividir por , obteniendo . d) Este proceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia no puede haber más de b enteros. Es decir el proceso es finito. e) En estas circunstancias, el máximo común divisor de a y b no es más que el último residuo no cero del proceso anterior. Esto lo garantiza la aplicación reiterada del siguiente teorema. 4.1.1. Teorema. Si a y b son enteros positivos con entonces M.C.D.(a, b) = M.C.D.( b, r ).

Answer 2

Un algoritmo es una secuencia de pasos para conseguir un resultado.

El algoritmo de Euclides es un procedimiento para calcular el m.c.d. de dos números. Los pasos son:

1 Se divide el número mayor entre el menor.

2 Si:

1 La división es exacta, el divisor es el m.c.d.

2 La división no es exacta, dividimos el divisor entre el resto obtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

Ejemplo: 

m.c.d. (72, 16) = 8