Algoritmo de Euclides

Euclides en su libro Elementos, dio este método para calcular el máximo común divisor de dos números, con el que no es necesario descomponer el número en factores primos (esta descomposición puede ser muy difícil cuando los números son muy grandes).

El algoritmo es así:

Sean a y b los números de los que queremos calcular el máximo común divisor. Hacemos las siguientes divisiones hasta que el resto de una de ellas sea cero.

a = bq₁ + r₁
b = r₁q₂ + r₂
r₁ = r₂q₃ + r₃
r₂ = r₃q₄ + r_{4
............................}
r_{n - 1} = r_nq_{n + 1} + 0

Siendo q1, q2, ... los cocientes y r1, r2, ... los restos. El máximo común divisor es r_n

Máximo común divisor de varios números

Para calcular el MCD de varios números (a₁, a₂, ... a_n) con el algoritmo de Euclides procedemos así:

Calculamos el MCD de los números a₁, a₂. Sea este número M₁.
Después calculamos el MCD de los números M₁, a₃. Sea este número M₂.
Repetimos el proceso hasta el último elemento. El MCD de los números M_{n - 1}, a_n, será el MCD de a₁, a₂, ... a_n