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 a = q1b + r2 con
0 £ r1 < b. Si r1 = 0, entonces bïa y M.C.D.(a, b) = b. b) Si r1 ¹ 0 se divide b por r1 y se producen enteros q2y r2 que satisfacen b =q2 r1 + r2 con 0 £ r2< r1. Si r2 = 0 el proceso termina y M.C.D.(a, b) = r1. c) Si r2 ¹ 0 se procede a dividir r2 por r1 obteniendo r1 = q3 r2 + r3 con 0 £ r3 < r2. d) Este proceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia b > r1 > r2 > ..... ³ 0 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.
