Categorías
Qué es, Significado y Concepto

Algoritmo de Euclides

Algoritmo de Euclides, procedimiento para hallar el máximo común divisor de dos números. Se basa en la siguiente propiedad: “Si d es divisor común de p y q, y p > q, entonces d es divisor del resto de dividir p entre q”.

Esta propiedad justifica el siguiente razonamiento: para hallar el M.C.D.(p, q) se divide p entre q, obteniendo un cociente q1 y un resto r1. Entonces:

D = M.C.D.(p, q) = M.C.D.(q, r1)

Ahora se procede de forma análoga con q y r1: se hace la división entera entre q y r1, obteniendo un cociente q2 y un resto r2. Entonces:

D = M.C.D.(q, r1) = M.C.D.(r1, r2)

Se prosigue así sucesivamente obteniendo números cada vez menores. De esta forma se llegará a una división exacta. El divisor de dicha división, que es el resto de la anterior, es el M.C.D., D, buscado. Como ejemplo se obtiene el M.C.D.(520, 360):

Por tanto, M.C.D.(520, 360) = 40

Los cálculos sucesivos suelen disponerse del siguiente modo:

Para calcular el M.C.D. de tres números, a, b, c, se halla el M.C.D. de dos de ellos, D, y luego se halla el M.C.D. de D y el tercero, pues:

M.C.D.(a, b, c) = M.C.D.(D, c)

siendo D = M.C.D.(a, b).

Teniendo en cuenta que entre el máximo común divisor, D, y el mínimo común múltiplo, M, de dos números, a y b, se da la siguiente relación:

a · b = D · M

conociendo D se puede calcular M:

Por ejemplo, para hallar el m.c.m.(520, 360), cuyo máximo común divisor se ha calculado mediante el algoritmo de Euclides, D = 40, se procede así:

Escrito por :