Cálculo del MCD: dividir una y otra vez -----------------------------------------
El teorema de la división euclídea proporciona un algoritmo —precisamente, el algoritmo de Euclides— que permite calcular el máximo común divisor, o MCD, de dos números. En casos elementales, ¡el valor del MCD salta a la vista! Así, el MCD de 21 y 15 es 3. Pero ¿qué decir del MCD de 1 597 y 987? El algoritmo de Euclides permite calcular el MCD de dos números naturales no nulos a y b mediante divisiones sucesivas: se divide a entre b; después, b entre el resto obtenido; luego, el primer resto entre el segundo; el segundo entre el tercero… y el último resto no nulo es el MCD. Así, el MCD de 1597 y 987 es 1; estos dos enteros son primos entre sí.
El teorema de Lamé: pocas divisiones que efectuar en la práctica ---------------------------------------------------
En cuanto se dispone de un algoritmo, interesa su eficacia. ¿Cómo «medirla»? ¿Cuál es el «tiempo de cálculo»? Esta cuestión es objeto de una nota, muy apreciada por los informáticos actuales, publicada en 1844 por Gabriel Lamé (1795-1870). Veamos lo que escribe este académico recién nombrado en los Comptes rendus hebdomadaires de l'Académie des sciences,: «En los tratados de aritmética, basta con decir que el número de divisiones que hay que efectuar, al buscar el máximo común divisor de dos enteros, no podrá superar la mitad del menor. Este límite, que puede superarse si los números son pequeños, queda muy lejos cuando tienen varias cifras.» A continuación establece: «El número de divisiones que hay que efectuar para hallar el máximo común divisor de dos enteros A y B < A es siempre menor que cinco veces el número de cifras de B [el divisor].»
Termina con un ejemplo que muestra la fuerza de su teorema: «Tomemos como ejemplo los dos números 1597 y 987. La búsqueda de su máximo común divisor constará de catorce divisiones. El límite fijado por el presente teorema es quince. El límite adoptado en los tratados de aritmética sería cuatrocientos noventa y tres.»