El mcd de dos enteros positivos r₀ y r₁ se denota por

mcd(r₀ , r₁)

y es el número positivo más grande que divide ambos r₀ y r₁. Para números pequeños, el mcd es fácil de calcular por la factorización de ambos números y encontrando el factor común más alto.

Para números más grandes a menudo no es posible factorizar, y un algoritmo más eficiente es usado para calcular el mcd, el Algoritmo de Euclides.

La principal observación de este algoritmo es que se puede reducir el problema de encontrar el mcd de dos números dados al mcd de 2 números más pequeños. Este proceso puede ser aplicado recursivamente hasta que finalmente se obtenga mcd(r_l , 0) = r_l

Se explicará el funcionamiento del algoritmo con un ejemplo.

Sea r₀ = 973 y r₁ = 301

Se toma el número mayor y se expresa en términos del menor.

973 = 3*301 + 70

Por lo tanto

mcd(973 , 301) = mcd(301, 70)

Se toma el ahora nuevo número mayor y se expresa en términos del nuevo menor.

301 = 4*70 + 21 mcd(301 , 70) = mcd(70, 21)

Se repiten los pasos hasta que el número menor sea 0.

70 = 3*21 + 7 mcd(70 , 21) = mcd(21, 7)
21 = 3*7 + 0 mcd(21 , 7) = mcd(7, 0)

Una vez que se llegó a la ronda con el número menor igual a 0, el número mayor de esa misma ronda es el mcd de los números originales.

mcd(973, 301) = mcd (7, 0) mcd(973, 301) = 7

---

Referencias

1. Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.