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í: