El algoritmo de euclides (originalmente formulado varias sustracciones en lugar de divisiones) se puede aplicar a cualquier par de cantidades comparables (dos longitudes, dos misas, dos frecuencias): basta restar el menor de un par de los más grandes y, a continuación, reemplace el más grande por la diferencia encontrada; pare cuando la diferencia se convierte en $0$, volviendo los más pequeños (que ahora es también el más grande) se conserva la cantidad como MCD. Aunque en realidad no lo he leído Euclides, me sorprendería si la formulación original no era, en realidad, en términos de geométrica longitudes, dado que los matemáticos griegos estaban más a gusto con la geometría de los números. La única salvedad es que con longitudes no es un algoritmo en el sentido de que está garantizado para terminar, dos longitudes son, por definición, "conmensurables" si el procedimiento de terminar, y, a continuación, devuelve el mayor unidad de longitud para que tanto inicial longitudes son múltiplos enteros. Uno puede mostrar fácilmente (sin utilizar cualquier aritmética) que el procedimiento de hecho nunca terminar (porque uno llega de nuevo a la original relación de longitudes, pero en una escala menor) cuando se comienza con la longitud de un lado y con una cuerda de un pentágono regular (dando la proporción áurea) o para un lado y una diagonal de un cuadrado (relación de $1:\sqrt2$); este es un buen ejercicio en la geometría.
![Pentagon]()
$\qquad$
![A4 paper]()
Ahora si aplicamos esto a los números racionales, se ve que no hay problema, ya que pueden ser comparados, resta, y cualquier par de ellos es necesariamente proporcionales (uno sobre el producto de los denominadores da una medida común, aunque no necesariamente el más grande). La reunión de ambos números racionales a este denominador común, uno ve que la fórmula adivinaste es la correcta. Si usted tiene el primer factorizations de $a,b,c,d$ disponible, usted puede también encontrar los $\gcd(\frac ab,\frac cd)$, tomando el primer número $p$ a un poder que es el mínimo de las valoraciones de $p$ en $\frac ab$ y $\frac cd$, donde la valoración en $\frac ab$ es su multiplicidad en $un$ menos su multiplicidad en $b$ (posiblemente un entero negativo). Sin embargo, su fórmula combina con el algoritmo de Euclides para enteros (o directamente el algoritmo de Euclides para números racionales) es un método más eficiente de la informática.
Agregó en respuesta al comentario de @Michael Hardy: Cuando digo que los matemáticos griegos estaban más a gusto con la geometría que con los números, yo no digo que el no sabe de números, pero que prefieren que indica y el tratamiento de una declaración sobre los números en términos geométricos, todo lo contrario a nuestra moderna tendencia a traducir problemas geométricos en términos numéricos. Un caso típico es el de Euclides prueba de lo que podríamos formular como el infinito de la serie de los números primos (él nunca utiliza los términos "finito" o "infinito", y no creo que estas nociones se utiliza incluso en el momento, pero ese no es mi punto aquí). Creo que la mayoría de la gente estaría de acuerdo en que esto es puramente número teórico de la declaración con absolutamente ninguna geométrica de contenido, sin embargo, Euclides estados y demuestra geométricamente (esencialmente por la construcción de un mínimo común múltiplo de un dado (finito) conjunto de primer múltiplos de una unidad de longitud). Y por este motivo geométrico de preferencia creo que tal vez es históricamente inexacto usar el término "algoritmo de Euclides" por un procedimiento restringido para el caso de un par de enteros positivos (y por lo tanto seguro para terminar) en lugar de un par de tallas (que podría no terminar); sin embargo, voy a repetir mi ignorancia exacta de las fuentes aquí.
Añadió más tarde Gracias @Robert Isreal para la referencia a la traducción de los Elementos. Así Euclides opera en su descripción de su algoritmo, en el Libro VII de las Proposiciones 2,3, en números, que son enteros múltiplos alguna unidad velado en el misterio ("que por virtud de la cual cada una de las cosas que existen se llama una"). Sin embargo, el lenguaje sugiere que los números son considerados como longitudes; si no, ¿por qué indican los números individuales por $AB$, $CD$, hablar de un número de la medición de otro, etc.? Por otra parte, en el libro X, la Proposición 2 se encuentra el mismo procedimiento, pero con números sustituido por el de "magnitudes", tratados exactamente igual que los números son (también denotado $AB$ etc.) pero con la diferencia de que no tienen una medida común. Así que en lugar de la relativamente primos/relativamente compuesto distinción, uno tiene una (muy diferente) conmensurables/inconmensurables distinción de magnitudes. Y en el inconmensurable caso, durante el procedimiento ", lo que es la izquierda nunca medidas que el anterior", lo que implica que el procedimiento nunca termina. Tal vez no he buscado bien, pero parece que Euclides no es muy fuerte en la demostración de la existencia de magnitudes inconmensurables. El ejemplo dado (el mismo que me dio anteriormente) no parece ser de Euclides, y el Libro X, la Proposición 10, aparte de no ser genuino, no puede probar la existencia de (entero) de razones que no son el cociente de dos números al cuadrado. Por ejemplo, no se muestran (al menos no en que la proposición) por $1:2$, no puede ser el cociente de dos números al cuadrado, incluso a pesar de que la prueba iba a ser fácil.
$\qquad$
