Dados dos números no primos entre sí, hallar su máximo común divisor.
Sean AB, CD los dos números dados no primos entre sí .
Así pues, hay que hallar el máximo común divisor de AB, CD.
Si en efecto CD | AB, y como CD|CD, entonces CD es divisor común de CD, AB. Y está claro que
también es el máximo, pues ninguno mayor que CD dividirá a CD.
Pero si CD ∤ AB, entonces, restándose sucesivamente el menor de los números AB, CD del mayor, quedará un
número que dividirá al anterior. Pues no quedará una unidad: porque en otro caso AB, CD serán primos entre sí
[Prop. VII.1], que es precisamente lo que se ha supuesto que no. Así pues, quedará un número que dividirá al anterior.
Ahora bien, CD, al dividir a BE, deje EA de resto , y EA, al dividir a DF, deje FC de resto ,
y divida CF a AE. Así pues, como CF | AE, y AE | DF, entonces CF | DF; pero CF | CF; entonces CF | CD. Pero CD | BE; luego CF | BE; y CF | EA;
por tanto CF | BA; pero CF | CD; entonces CF | AB, CF |CD.
Por tanto, CF es divisor común de AB, CD.
Digo ahora que también es el máximo.
Pues, si CF no es el máximo común divisor de AB, CD, un número que
sea mayor que CF dividirá a los números AB, CD. Divídalos un número y sea G . Y como G | CD y CD | BE,
entonces G | BE; pero también CD | BA; entonces CD | AE.
Pero AE | DF; por tanto, G | DF y G | DC; luego G | CF,
esto es: el mayor al menor, lo cual es imposible; así pues, no dividirá a los números AB, CD un número que
sea mayor que CF.
Por consiguiente, CF es el máximo común divisor de AB, CD.
Q. E. D.