Algoritmo euclidiano

En matemáticas , el algoritmo de Euclides ^, o algoritmo de Euclides , es un método eficiente para calcular el máximo común divisor (MCD) de dos números enteros (números), el número más grande que los divide a ambos sin dejar resto . Recibe su nombre del antiguo matemático griego Euclides , quien lo describió por primera vez en sus Elementos ( c.  300 a. C. ). Es un ejemplo de algoritmo , un procedimiento paso a paso para realizar un cálculo de acuerdo con reglas bien definidas, y es uno de los algoritmos más antiguos de uso común. Se puede utilizar para reducir fracciones a su forma más simple , y es parte de muchos otros cálculos criptográficos y teóricos de números.

El algoritmo de Euclides se basa en el principio de que el máximo común divisor de dos números no cambia si el número mayor se reemplaza por su diferencia con el número menor. Por ejemplo, 21 es el MCD de 252 y 105 (ya que 252 = 21 × 12 y 105 = 21 × 5) , y el mismo número 21 es también el MCD de 105 y 252 − 105 = 147. Como este reemplazo reduce el mayor de los dos números, repetir este proceso da pares de números sucesivamente más pequeños hasta que los dos números se vuelven iguales. Cuando eso ocurre, ese número es el MCD de los dos números originales. Invirtiendo los pasos o utilizando el algoritmo euclidiano extendido , el MCD puede expresarse como una combinación lineal de los dos números originales, es decir, la suma de los dos números, cada uno multiplicado por un entero (por ejemplo, 21 = 5 × 105 + (−2) × 252 ). El hecho de que el MCD siempre pueda expresarse de esta manera se conoce como identidad de Bézout .

La versión del algoritmo euclidiano descrita anteriormente (que sigue la presentación original de Euclides) puede realizar muchos pasos de resta para encontrar el MCD cuando uno de los números dados es mucho mayor que el otro. Una versión más eficiente del algoritmo acorta estos pasos, reemplazando en su lugar el mayor de los dos números por su resto cuando se divide por el menor de los dos (con esta versión, el algoritmo se detiene al llegar a un resto cero). Con esta mejora, el algoritmo nunca requiere más pasos que cinco veces el número de dígitos (base 10) del entero más pequeño. Esto fue demostrado por Gabriel Lamé en 1844 ( Teorema de Lamé ), ^{[1] [2]} y marca el comienzo de la teoría de la complejidad computacional . En el siglo XX se desarrollaron métodos adicionales para mejorar la eficiencia del algoritmo.

El algoritmo de Euclides tiene muchas aplicaciones teóricas y prácticas. Se utiliza para reducir fracciones a su forma más simple y para realizar divisiones en aritmética modular . Los cálculos que utilizan este algoritmo forman parte de los protocolos criptográficos que se utilizan para proteger las comunicaciones por Internet y en los métodos para romper estos criptosistemas mediante la factorización de números compuestos grandes . El algoritmo de Euclides se puede utilizar para resolver ecuaciones diofánticas , como encontrar números que satisfagan congruencias múltiples según el teorema del resto chino , para construir fracciones continuas y para encontrar aproximaciones racionales precisas a números reales. Finalmente, se puede utilizar como una herramienta básica para demostrar teoremas en teoría de números como el teorema de los cuatro cuadrados de Lagrange y la unicidad de las factorizaciones primas .

El algoritmo original fue descrito únicamente para números naturales y longitudes geométricas (números reales), pero en el siglo XIX se generalizó a otros tipos de números, como los enteros gaussianos y los polinomios de una variable, lo que dio lugar a nociones algebraicas abstractas modernas como los dominios euclidianos .

El algoritmo de Euclides calcula el máximo común divisor (MCD) de dos números naturales a y b . El máximo común divisor g es el número natural más grande que divide a a y b sin dejar residuo. Los sinónimos de MCD incluyen máximo común divisor (MCD ), máximo común divisor (MCD) y máximo común divisor (MCD). El máximo común divisor se escribe a menudo como mcd( a ,  b ) o, más simplemente, como ( a ,  b ) , ^[3] aunque la última notación es ambigua, también se utiliza para conceptos como un ideal en el anillo de números enteros , que está estrechamente relacionado con MCD.

Si mcd( a ,  b ) = 1 , entonces se dice que a y b son coprimos (o primos relativos). ^[4] Esta propiedad no implica que a o b sean en sí mismos números primos . ^[5] Por ejemplo, 6 y 35 se factorizan como 6 = 2 × 3 y 35 = 5 × 7, por lo que no son primos, pero sus factores primos son diferentes, por lo que 6 y 35 son coprimos, sin factores comunes distintos de 1.

Sea g = mcd( a ,  b ) . Puesto que a y b son ambos múltiplos de g , pueden escribirse a  =  mg y b  =  ng , y no hay ningún número mayor G  >  g para el que esto sea cierto. Los números naturales m y n deben ser coprimos, puesto que cualquier factor común podría factorizarse de m y n para hacer que g sea mayor. Por lo tanto, cualquier otro número c que divida tanto a a como b también debe dividir a g . El máximo común divisor g de a y b es el único divisor común (positivo) de a y b que es divisible por cualquier otro divisor común c . ^[6]

El máximo común divisor se puede visualizar de la siguiente manera. ^[7] Considere un área rectangular a por b , y cualquier divisor común c que divida a y b exactamente. Los lados del rectángulo se pueden dividir en segmentos de longitud c , que dividen el rectángulo en una cuadrícula de cuadrados de longitud de lado c . El MCD g es el valor más grande de c para el cual esto es posible. A modo de ilustración, un área rectangular de 24×60 se puede dividir en una cuadrícula de: cuadrados de 1×1 , cuadrados de 2×2 , cuadrados de 3×3 , cuadrados de 4×4 , cuadrados de 6×6 o cuadrados de 12×12 . Por lo tanto, 12 es el MCD de 24 y 60 . Un área rectangular de 24×60 se puede dividir en una cuadrícula de cuadrados de 12×12 , con dos cuadrados a lo largo de un borde ( 24/12 = 2 ) y cinco cuadrados a lo largo del otro ( 60/12 = 5 ).

El máximo común divisor de dos números a y b es el producto de los factores primos compartidos por los dos números, donde cada factor primo puede repetirse tantas veces como divida a a y b . ^[8] Por ejemplo, dado que 1386 puede factorizarse en 2 × 3 × 3 × 7 × 11 , y 3213 puede factorizarse en 3 × 3 × 3 × 7 × 17 , el MCD de 1386 y 3213 es igual a 63 = 3 × 3 × 7 , el producto de sus factores primos compartidos (con 3 repetido ya que 3 × 3 divide a ambos). Si dos números no tienen factores primos comunes, su MCD es 1 (obtenido aquí como una instancia del producto vacío ); en otras palabras, son coprimos. Una ventaja clave del algoritmo euclidiano es que puede encontrar el MCD de manera eficiente sin tener que calcular los factores primos. ^{[9] [10] Se cree que} la factorización de números enteros grandes es un problema computacionalmente muy difícil, y la seguridad de muchos protocolos criptográficos ampliamente utilizados se basa en su inviabilidad. ^[11]

Otra definición del MCD es útil en matemáticas avanzadas, particularmente en la teoría de anillos . ^[12] El máximo común divisor g de dos números distintos de cero a y b es también su combinación lineal integral positiva más pequeña, es decir, el número positivo más pequeño de la forma ua  +  vb donde u y v son números enteros. El conjunto de todas las combinaciones lineales integrales de a y b es en realidad el mismo que el conjunto de todos los múltiplos de g ( mg , donde m es un número entero). En el lenguaje matemático moderno, el ideal generado por a y b es el ideal generado solo por  g (un ideal generado por un solo elemento se llama ideal principal , y todos los ideales de los números enteros son ideales principales). Algunas propiedades del MCD son de hecho más fáciles de ver con esta descripción, por ejemplo, el hecho de que cualquier divisor común de a y b también divide el MCD (divide ambos términos de ua  +  vb ). La equivalencia de esta definición de MCD con las otras definiciones se describe a continuación.

El MCD de tres o más números es igual al producto de los factores primos comunes a todos los números, ^[13] pero también se puede calcular tomando repetidamente los MCD de pares de números. ^[14] Por ejemplo,

mcd( a ,  b ,  c ) = mcd( a , mcd( b ,  c )) = mcd(mcd( a ,  b ),  c ​​) = mcd(mcd( a ,  c ),  b ).

Por tanto, el algoritmo de Euclides, que calcula el MCD de dos números enteros, es suficiente para calcular el MCD de un número arbitrario de números enteros.

Wikifunctions tiene una función de algoritmo euclidiano .

El algoritmo euclidiano puede considerarse como la construcción de una secuencia de números enteros no negativos que comienza con los dos números enteros dados y y finalmente terminará con el número entero cero: con . El número entero será entonces el MCD y podemos afirmar . El algoritmo indica cómo construir los residuos intermedios mediante la división con residuo en el par anterior hallando un cociente entero de modo que:$estilo de visualización r_{-2}=a}$$estilo de visualización r_{-1}=b$${\displaystyle \{r_{-2}=a,\r_{-1}=b,\r_{0},\r_{1},\cdots,\r_{n-1},\r_{n}=0\}}$${\displaystyle r_{k+1}<r_{k}}$$estilo de visualización r_{n-1}}$${\displaystyle {\text{mcd}}(a,b)=r_{n-1}}$$estilo de visualización r_{k}}$${\estilo de visualización (r_{k-2},\r_{k-1})}$$estilo de visualización q_ {k}}$

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, con }}\ r_{k-1}>r_{k}\geq 0.}$

Como la secuencia de números enteros no negativos es estrictamente decreciente, eventualmente debe terminar en . En otras palabras, dado que para cada , y cada uno es un número entero que es estrictamente menor que el anterior , eventualmente no puede haber un número entero no negativo menor que cero y, por lo tanto, el algoritmo debe terminar. De hecho, el algoritmo siempre terminará en el paso n-ésimo con igual a cero. ^[15]${\displaystyle \{r_{k}\}}$${\displaystyle r_{k}\geq 0}$${\estilo de visualización k}$$estilo de visualización r_{k}}$$estilo de visualización r_{k-1}}$$estilo de visualización r_{n}$

Para ilustrarlo, supongamos que se solicita el MCD de 1071 y 462. La secuencia es inicialmente y para encontrar , necesitamos encontrar números enteros y tales que:${\displaystyle \{r_{-2}=1071,\r_{-1}=462\}}$$estilo de visualización r_{0}$$estilo de visualización q_{0}}$$estilo de visualización r_{0}<r_{-1}}$

${\displaystyle 1071=q_{0}\cdot 462+r_{0}}$.

Este es el cociente ya que . Esto determina y por lo tanto la secuencia ahora es . El siguiente paso es continuar la secuencia para encontrar mediante la búsqueda de números enteros y tales que:${\displaystyle q_{0}=2}$${\displaystyle 1071=2\cdot 462+147}$${\displaystyle r_{0}=147}$${\displaystyle \{1071,\ 462,\ r_{0}=147\}}$$estilo de visualización r_{1}$$estilo de visualización q_{1}}$$estilo de visualización r_{1}<r_{0}}$

${\displaystyle 462=q_{1}\cdot 147+r_{1}}$.

Este es el cociente ya que . Esto determina y por lo tanto la secuencia ahora es . El siguiente paso es continuar la secuencia para encontrar mediante la búsqueda de números enteros y tales que:$estilo de visualización q_{1}=3$${\displaystyle 462=3\cdot 147+21}$${\displaystyle r_{1}=21}$${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}$$estilo de visualización r_{2}$$estilo de visualización q_{2}$$estilo de visualización r_{2}<r_{1}}$

${\displaystyle 147=q_{2}\cdot 21+r_{2}}$.

Este es el cociente ya que . Esto determina y por lo tanto la secuencia se completa ya que no se puede encontrar ningún otro entero no negativo menor que . El penúltimo resto es, por lo tanto, el MCD solicitado:$estilo de visualización q_{2}=7$${\displaystyle 147=7\cdot 21+0}$${\displaystyle r_{2}=0}$${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$${\estilo de visualización 0}$${\estilo de visualización 21}$

${\displaystyle {\text{mcd}}(1071,\ 462)=21.}$

Podemos generalizar ligeramente eliminando cualquier requisito de ordenación en los dos valores iniciales y . Si , el algoritmo puede continuar y encontrar trivialmente que como la secuencia de residuos será . Si , entonces también podemos continuar ya que , lo que sugiere que el siguiente residuo debe ser él mismo, y la secuencia es . Normalmente, esto sería inválido porque rompe el requisito , pero ahora tenemos por construcción, por lo que el requisito se satisface automáticamente y el algoritmo euclidiano puede continuar normalmente. Por lo tanto, eliminar cualquier ordenación entre los primeros dos números enteros no afecta la conclusión de que la secuencia debe terminar eventualmente porque el siguiente residuo siempre satisfará y todo continúa como antes. Las únicas modificaciones que deben hacerse son que solo para , y que la subsecuencia de números enteros no negativos para es estrictamente decreciente, por lo tanto excluyendo de ambas afirmaciones.${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización a=b}$${\displaystyle {\text{mcd}}(a,\ a)=a}$${\displaystyle \{a,\ a,\ 0\}}$${\estilo de visualización a<b}$${\displaystyle a\equiv 0\cdot b+a}$${\estilo de visualización a}$${\displaystyle \{a,\ b,\ a,\ \cpuntos \}}$$estilo de visualización r_{0}<r_{-1}}$${\estilo de visualización a<b}$${\displaystyle r_{0}<b}$${\displaystyle r_{k}<r_{k-1}}$${\displaystyle k\geq 0}$$Estilo de visualización: rk-1$${\displaystyle k\geq 0}$$estilo de visualización a=r_{-2}}$

La validez del algoritmo euclidiano se puede demostrar mediante un argumento de dos pasos. ^[16] En el primer paso, se muestra que el residuo final distinto de cero r _{N −1} divide tanto a a como b . Dado que es un divisor común, debe ser menor o igual que el máximo común divisor g . En el segundo paso, se muestra que cualquier divisor común de a y b , incluido g , debe dividir a r _{N −1} ; por lo tanto, g debe ser menor o igual que r _{N −1} . Estas dos desigualdades opuestas implican r _{N −1}  =  g .

Para demostrar que r _{N −1} divide tanto a a como b (el primer paso), r _{N −1} divide a su predecesor r _{N −2}

rN _{− 2} = qN _rN − _1​

ya que el resto final r _N es cero. r _{N −1} también divide a su siguiente predecesor r _{N −3}

rN _{− 3} = qN _{− 1} rN _{− 2} + rN _{− 1}

porque divide ambos términos del lado derecho de la ecuación. Iterando el mismo argumento, r _{N −1} divide todos los residuos anteriores, incluidos a y b . Ninguno de los residuos anteriores r _{N −2} , r _{N −3} , etc. divide a y b , ya que dejan un residuo. Como r _{N −1} es un divisor común de a y b , r _{N −1}  ≤  g .

En el segundo paso, cualquier número natural c que divida tanto a a como b (en otras palabras, cualquier divisor común de a y b ) divide los residuos r _k . Por definición, a y b pueden escribirse como múltiplos de c  : a  =  mc y b  =  nc , donde m y n son números naturales. Por lo tanto, c divide el residuo inicial r ₀ , ya que r ₀  =  a  −  q ₀ b  =  mc  −  q ₀ nc  = ( m  −  q ₀ n ) c . Un argumento análogo muestra que c también divide los residuos posteriores r ₁ , r ₂ , etc. Por lo tanto, el máximo común divisor g debe dividir a r _{N −1} , lo que implica que g  ≤  r _{N −1} . Como la primera parte del argumento demostró lo contrario ( r _{N −1}  ≤  g ), se deduce que g  =  r _{N −1} . Por lo tanto, g es el máximo común divisor de todos los pares siguientes: ^{[17] [18]}

gramo = mcd( a , b ) = mcd( segundo , r ₀ ) = mcd( r ₀ , r ₁ ) = … = mcd( r _{norte −2} , r _{norte −1} ) = r _{norte −1} .

A modo de ejemplo, se puede utilizar el algoritmo euclidiano para hallar el máximo común divisor de a  = 1071 y b  = 462. Para empezar, se restan los múltiplos de 462 de 1071 hasta que el resto sea menor que 462. Se pueden restar dos de estos múltiplos ( q ₀  = 2), lo que deja un resto de 147:

1071 = 2 × 462 + 147.

Luego se restan múltiplos de 147 de 462 hasta que el resto sea menor que 147. Se pueden restar tres múltiplos ( q ₁  = 3), dejando un resto de 21:

462 = 3 × 147 + 21.

Luego se restan múltiplos de 21 de 147 hasta que el resto sea menor que 21. Se pueden restar siete múltiplos ( q ₂  = 7), sin dejar resto:

147 = 7 × 21 + 0.

Como el último resto es cero, el algoritmo termina con 21 como máximo común divisor de 1071 y 462. Esto concuerda con el mcd(1071, 462) obtenido por factorización prima antes mencionado. En forma de tabla, los pasos son:

El algoritmo euclidiano se puede visualizar en términos de la analogía de mosaico dada anteriormente para el máximo común divisor. ^[19] Supongamos que deseamos cubrir un rectángulo a × b con mosaicos cuadrados exactamente, donde a es el mayor de los dos números. Primero intentamos cubrir el rectángulo usando mosaicos cuadrados b × b ; sin embargo, esto deja un rectángulo residual r ₀ × b sin mosaicos, donde r ₀  <  b . Luego intentamos cubrir el rectángulo residual con mosaicos cuadrados r ₀ × r _{0 . Esto deja un segundo rectángulo residual} r ₁ × r ₀ , que intentamos cubrir usando mosaicos cuadrados r ₁ × r ₁ , y así sucesivamente. La secuencia termina cuando no hay ningún rectángulo residual, es decir, cuando los mosaicos cuadrados cubren exactamente el rectángulo residual anterior. La longitud de los lados del mosaico cuadrado más pequeño es el MCD de las dimensiones del rectángulo original. Por ejemplo, la pieza cuadrada más pequeña en la figura adyacente mide 21×21 (mostrada en rojo), y 21 es el MCD de 1071 y 462, las dimensiones del rectángulo original (mostrado en verde).

En cada paso k , el algoritmo euclidiano calcula un cociente q _k y un resto r _k a partir de dos números r _{k −1} y r _{k −2.}

rk ₋₂ = qk _{rk −1} + rk_​​_​​

donde r _k no es negativo y es estrictamente menor que el valor absoluto de r _{k −1} . El teorema que subyace a la definición de la división euclidiana asegura que dicho cociente y residuo siempre existen y son únicos. ^[20]

En la versión original del algoritmo de Euclides, el cociente y el resto se encuentran por sustracción repetida; es decir, r _{k −1} se resta de r _{k −2} repetidamente hasta que el resto r _k sea menor que r _{k −1} . Después de eso, r _k y r _{k −1} se intercambian y el proceso se itera. La división euclidiana reduce todos los pasos entre dos intercambios en un solo paso, lo que es, por tanto, más eficiente. Además, los cocientes no son necesarios, por lo que se puede reemplazar la división euclidiana por la operación módulo , que da solo el resto. Por lo tanto, la iteración del algoritmo euclidiano se convierte simplemente en

rk = rk ₋₂ módulo rk ₋₁ ._​​​

Las implementaciones del algoritmo pueden expresarse en pseudocódigo . Por ejemplo, la versión basada en división puede programarse como ^[21]

función mcd(a, b) mientras b ≠ 0 t := b b := a módulo b un := t devolver un

Al comienzo de la k iteración, la variable b contiene el último residuo r _{k −1} , mientras que la variable a contiene su predecesor, r _{k −2} . El paso b  := a mod b es equivalente a la fórmula de recursión anterior r _k ≡ r _{k −2} mod r _{k −1} . La variable temporal t contiene el valor de r _{k −1} mientras se calcula el siguiente residuo r _k . Al final de la iteración del bucle, la variable b contiene el residuo r _k , mientras que la variable a contiene su predecesor, r _{k −1} .

(Si se permiten entradas negativas, o si la función mod puede devolver valores negativos, la última línea debe cambiarse a return abs (a).)

En la versión basada en la resta, que fue la versión original de Euclides, el cálculo del resto ( ) se reemplaza por una resta repetida. ^[22] A diferencia de la versión basada en la división, que trabaja con números enteros arbitrarios como entrada, la versión basada en la resta supone que la entrada consiste en números enteros positivos y se detiene cuando a = b :b := a mod b

función mcd(a, b) mientras a ≠ b si a > b a := a − b demás b := b − a devolver un

Las variables a y b se alternan manteniendo los residuos anteriores r _{k −1} y r _{k −2} . Supongamos que a es mayor que b al comienzo de una iteración; entonces a es igual a r _{k −2} , ya que r _{k −2} > r _{k −1} . Durante la iteración del bucle, a se reduce en múltiplos del residuo anterior b hasta que a es menor que b . Entonces a es el siguiente residuo r _k . Luego b se reduce en múltiplos de a hasta que es nuevamente menor que a , dando el siguiente residuo r _{k +1} , y así sucesivamente.

La versión recursiva ^[23] se basa en la igualdad de los MCD de los residuos sucesivos y la condición de detención mcd( r _{N −1} , 0) =  r _{N −1} .

función mcd(a, b) si b = 0 devuelve a de lo contrario  devuelve mcd(b, a mod b)

(Como se indicó anteriormente, si se permiten entradas negativas, o si la función mod puede devolver valores negativos, la instrucción " return a" debe cambiarse a " return max (a, −a)".)

A modo de ejemplo, el mcd(1071, 462) se calcula a partir del mcd equivalente(462, 1071 mod 462) = mcd(462, 147). Este último mcd se calcula a partir del mcd(147, 462 mod 147) = mcd(147, 21), que a su vez se calcula a partir del mcd(21, 147 mod 21) = mcd(21, 0) = 21.

En otra versión del algoritmo de Euclides, el cociente en cada paso se incrementa en uno si el resto negativo resultante es menor en magnitud que el resto positivo típico. ^{[24] [25]} Anteriormente, la ecuación

rk ₋₂ = qk _{rk −1} + rk_​​_​​

Se supone que | r _{k −1} | >  r _k  > 0 . Sin embargo, se puede calcular un resto negativo alternativo e _{k :}

rk ₋₂ = ₍ qk + _{1 )} rk ₋₁ + ek_​

si r _{k −1}  > 0 o

rk ₋₂ = ( qk _{− 1} ) rk _{−1 +} ek_​

si r _{k −1}  < 0 .

Si r _k se reemplaza por e _k , cuando | e _k | < | r _k | , entonces se obtiene una variante del algoritmo euclidiano tal que

| r _k | ≤ | r _{k −1} | / 2

en cada paso.

Leopold Kronecker ha demostrado que esta versión requiere la menor cantidad de pasos de cualquier versión del algoritmo de Euclides. ^{[24] [25]} De manera más general, se ha demostrado que, para cada número de entrada a y b , el número de pasos es mínimo si y solo si se elige q _k para que donde es la proporción áurea . ^[26]${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$${\displaystyle \varphi }$

El algoritmo de Euclides es uno de los algoritmos más antiguos de uso común. ^[27] Aparece en los Elementos de Euclides (c. 300 a. C.), específicamente en el Libro 7 (Proposiciones 1-2) y el Libro 10 (Proposiciones 2-3). En el Libro 7, el algoritmo está formulado para números enteros, mientras que en el Libro 10, está formulado para longitudes de segmentos de línea. (En el uso moderno, uno diría que fue formulado allí para números reales . Pero las longitudes, áreas y volúmenes, representados como números reales en el uso moderno, no se miden en las mismas unidades y no hay una unidad natural de longitud, área o volumen; el concepto de números reales era desconocido en ese momento). El último algoritmo es geométrico. El MCD de dos longitudes a y b corresponde a la mayor longitud g que mide a y b de manera uniforme; en otras palabras, las longitudes a y b son ambas múltiplos enteros de la longitud g .

El algoritmo probablemente no fue descubierto por Euclides , quien recopiló los resultados de matemáticos anteriores en sus Elementos . ^{[28] [29]} El matemático e historiador BL van der Waerden sugiere que el Libro VII deriva de un libro de texto sobre teoría de números escrito por matemáticos de la escuela de Pitágoras . ^[30] El algoritmo probablemente era conocido por Eudoxo de Cnido (alrededor del 375 a. C.). ^{[27] [31]} El algoritmo puede incluso ser anterior a Eudoxo, ^{[32] [33]} a juzgar por el uso del término técnico ἀνθυφαίρεσις ( antifairesis , sustracción recíproca) en obras de Euclides y Aristóteles . ^[34]

Siglos después, el algoritmo de Euclides fue descubierto de forma independiente tanto en la India como en China, ^[35] principalmente para resolver ecuaciones diofánticas que surgieron en astronomía y para hacer calendarios precisos. A finales del siglo V, el matemático y astrónomo indio Aryabhata describió el algoritmo como el "pulverizador", ^[36] quizás por su eficacia para resolver ecuaciones diofánticas. ^[37] Aunque ya se había descrito un caso especial del teorema del resto chino en el libro chino Sunzi Suanjing , ^[38] la solución general fue publicada por Qin Jiushao en su libro de 1247 Shushu Jiuzhang (數書九章Tratado matemático en nueve secciones ). ^[39] El algoritmo de Euclides fue descrito numéricamente por primera vez y popularizado en Europa en la segunda edición de Problèmes plaisants et délectables ( Problemas agradables y placenteros , 1624) de Bachet . ^[36] En Europa, también se utilizó para resolver ecuaciones diofánticas y en el desarrollo de fracciones continuas . El algoritmo euclidiano extendido fue publicado por el matemático inglés Nicholas Saunderson , ^[40] quien lo atribuyó a Roger Cotes como un método para calcular fracciones continuas de manera eficiente. ^[41]

En el siglo XIX, el algoritmo euclidiano condujo al desarrollo de nuevos sistemas numéricos, como los números enteros de Gauss y los números enteros de Eisenstein . En 1815, Carl Gauss utilizó el algoritmo euclidiano para demostrar la factorización única de los números enteros de Gauss , aunque su trabajo se publicó por primera vez en 1832. ^[42] Gauss mencionó el algoritmo en sus Disquisitiones Arithmeticae (publicada en 1801), pero solo como un método para fracciones continuas . ^[35] Peter Gustav Lejeune Dirichlet parece haber sido el primero en describir el algoritmo euclidiano como la base de gran parte de la teoría de números. ^[43] Lejeune Dirichlet señaló que muchos resultados de la teoría de números, como la factorización única, serían válidos para cualquier otro sistema de números al que se pudiera aplicar el algoritmo euclidiano. ^[44] Las conferencias de Lejeune Dirichlet sobre teoría de números fueron editadas y ampliadas por Richard Dedekind , quien utilizó el algoritmo de Euclides para estudiar los números enteros algebraicos , un nuevo tipo general de número. Por ejemplo, Dedekind fue el primero en demostrar el teorema de los dos cuadrados de Fermat utilizando la factorización única de los números enteros gaussianos. ^[45] Dedekind también definió el concepto de dominio euclidiano , un sistema numérico en el que se puede definir una versión generalizada del algoritmo euclidiano (como se describe a continuación). En las últimas décadas del siglo XIX, el algoritmo euclidiano fue eclipsado gradualmente por la teoría más general de los ideales de Dedekind . ^[46]

En el siglo XIX se desarrollaron otras aplicaciones del algoritmo de Euclides. En 1829, Charles Sturm demostró que el algoritmo era útil en el método de la cadena de Sturm para contar las raíces reales de polinomios en cualquier intervalo dado. ^[47]

El algoritmo euclidiano fue el primer algoritmo de relación entera , que es un método para encontrar relaciones enteras entre números reales conmensurables. Se han desarrollado varios algoritmos de relación entera novedosos , como el algoritmo de Helaman Ferguson y RW Forcade (1979) ^[48] y el algoritmo LLL ^{[49] [50]}

En 1969, Cole y Davie desarrollaron un juego para dos jugadores basado en el algoritmo euclidiano, llamado El juego de Euclides , ^[51] que tiene una estrategia óptima. ^[52] Los jugadores comienzan con dos pilas de piedras a y b . Los jugadores se turnan para quitar m múltiplos de la pila más pequeña de la más grande. Por lo tanto, si las dos pilas consisten en x e y piedras, donde x es mayor que y , el siguiente jugador puede reducir la pila más grande de x piedras a x − my piedras, siempre que este último sea un entero no negativo. El ganador es el primer jugador que reduce una pila a cero piedras. ^{[53] [54]}

La identidad de Bézout establece que el máximo común divisor g de dos números enteros a y b puede representarse como una suma lineal de los dos números originales a y b . ^[55] En otras palabras, siempre es posible encontrar los números enteros s y t tales que g  =  sa  +  tb . ^{[56] [57]}

Los números enteros s y t se pueden calcular a partir de los cocientes q ₀ , q ₁ , etc. invirtiendo el orden de las ecuaciones en el algoritmo de Euclides. ^[58] Comenzando con la penúltima ecuación, g se puede expresar en términos del cociente q _{N −1} y los dos residuos anteriores, r _{N −2} y r _{N −3} :

g = rN _{− 1} = rN _{− 3} − qN _{− 1} rN _{− 2}  .

Estos dos residuos pueden expresarse asimismo en términos de sus cocientes y residuos precedentes,

r _{N −2} = r _{N −4} − q _{N −2} r _{N −3} y

rN _{− 3} = rN _{− 5} − qN _{− 3} rN _{− 4}  .

Sustituyendo estas fórmulas para r _{N −2} y r _{N −3} en la primera ecuación se obtiene g como suma lineal de los residuos r _{N −4} y r _{N −5} . El proceso de sustitución de residuos por fórmulas que involucran a sus predecesoras puede continuar hasta que se alcancen los números originales a y b :

r2 = r0 - q2 _r1​​​_​

r1 = b - q1 _r0​​_​

r ₀ = a − q ₀ b .

Después de haber sustituido todos los residuos r ₀ , r _{1 , etc., la ecuación final expresa} g como una suma lineal de a y b , de modo que g  =  sa  +  tb .

El algoritmo euclidiano, y por tanto la identidad de Bézout, pueden generalizarse al contexto de los dominios euclidianos .

La identidad de Bézout proporciona otra definición del máximo común divisor g de dos números a y b . ^[12] Considérese el conjunto de todos los números ua  +  vb , donde u y v son dos enteros cualesquiera. Puesto que a y b son ambos divisibles por g , cada número del conjunto es divisible por g . En otras palabras, cada número del conjunto es un múltiplo entero de g . Esto es cierto para cada divisor común de a y b . Sin embargo, a diferencia de otros divisores comunes, el máximo común divisor es un miembro del conjunto; por la identidad de Bézout, eligiendo u  =  s y v  =  t se obtiene g . Un divisor común más pequeño no puede ser un miembro del conjunto, puesto que cada miembro del conjunto debe ser divisible por g . A la inversa, cualquier múltiplo m de g se puede obtener eligiendo u  =  ms y v  =  mt , donde s y t son los enteros de la identidad de Bézout. Esto se puede ver multiplicando la identidad de Bézout por m ,

Peso corporal = 1,200 kg .

Por lo tanto, el conjunto de todos los números ua  +  vb es equivalente al conjunto de múltiplos m de g . En otras palabras, el conjunto de todas las sumas posibles de múltiplos enteros de dos números ( a y b ) es equivalente al conjunto de múltiplos de mcd ( a , b ). Se dice que el MCD es el generador del ideal de a y b . Esta definición de MCD condujo a los conceptos algebraicos abstractos modernos de un ideal principal (un ideal generado por un solo elemento) y un dominio de ideales principales (un dominio en el que cada ideal es un ideal principal).

Ciertos problemas pueden resolverse utilizando este resultado. ^[59] Por ejemplo, considere dos tazas medidoras de volumen a y b . Sumando/restando u múltiplos de la primera taza y v múltiplos de la segunda taza, se puede medir cualquier volumen ua  +  vb . Estos volúmenes son todos múltiplos de g  = mcd( a ,  b ).

Los números enteros s y t de la identidad de Bézout se pueden calcular de manera eficiente utilizando el algoritmo euclidiano extendido . Esta extensión agrega dos ecuaciones recursivas al algoritmo de Euclides ^[60]

s _k = s _{k −2} − q _k s _{k −1}

tk ₌ tk ₋₂ − qkt tk ₋₁​_​​​

con los valores iniciales

s ₋₂ = 1, t ₋₂ = 0

s ₋₁ = 0, t ₋₁ = 1.

Usando esta recursión, los enteros de Bézout s y t se dan por s  =  s _N y t  =  t _N , donde N+1 es el paso en el que el algoritmo termina con r _N+1  = 0.

La validez de este enfoque se puede demostrar por inducción. Supongamos que la fórmula de recursión es correcta hasta el paso k  − 1 del algoritmo; en otras palabras, supongamos que

rj = sja + tjb_​​​_​​

para todos los j menores que k . El k -ésimo paso del algoritmo da la ecuación

rk = rk ₋₂ − qk _{rk −1} ._​​​_​

Dado que se ha asumido que la fórmula de recursión es correcta para r _{k −2} y r _{k −1} , se pueden expresar en términos de las variables s y t correspondientes.

r _k = ( s _{k −2} a + t _{k −2} b ) − q _k ( s _{k −1} a + t _{k −1} b ).

Reorganizando esta ecuación se obtiene la fórmula de recursión para el paso k , como se requiere

r _k = s _k a + t _k b = ( s _{k −2} − q _k s _{k −1} ) a + ( t _{k −2} − q _k t _{k −1} ) b .

Los números enteros s y t también se pueden encontrar utilizando un método de matriz equivalente . ^[61] La secuencia de ecuaciones del algoritmo de Euclides

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}$

se puede escribir como un producto de matrices cociente 2×2 multiplicando un vector resto bidimensional

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}$

Sea M el producto de todas las matrices cocientes

${\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}$

Esto simplifica el algoritmo euclidiano a la forma

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}$

Para expresar g como una suma lineal de a y b , ambos lados de esta ecuación se pueden multiplicar por la inversa de la matriz M . ^{[61] [62]} El determinante de M es igual a (−1) ^{N +1} , ya que es igual al producto de los determinantes de las matrices cociente, cada una de las cuales es negativa uno. Como el determinante de M nunca es cero, el vector de los residuos finales se puede resolver utilizando la inversa de M

${\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}$

Dado que la ecuación superior da

g = (−1) ^{N + 1} ( m ₂₂ a − m ₁₂ b ),

Los dos números enteros de la identidad de Bézout son s  = (−1) ^{N +1} m ₂₂ y t  = (−1) ^N m ₁₂ . El método matricial es tan eficiente como la recursión equivalente, con dos multiplicaciones y dos sumas por paso del algoritmo euclidiano.

La identidad de Bézout es esencial para muchas aplicaciones del algoritmo de Euclides, como demostrar la factorización única de números en factores primos. ^[63] Para ilustrar esto, supongamos que un número L puede escribirse como un producto de dos factores u y v , es decir, L  =  uv . Si otro número w también divide a L pero es coprimo con u , entonces w debe dividir a v , por el siguiente argumento: Si el máximo común divisor de u y w es 1, entonces los números enteros s y t pueden encontrarse tales que

1 = su + tw

por la identidad de Bézout. Multiplicando ambos lados por v se obtiene la relación:

v = todoterreno + dos vehículos = sL + dos vehículos

Como w divide ambos términos del lado derecho, también debe dividir el lado izquierdo, v . Este resultado se conoce como el lema de Euclides . ^[64] Específicamente, si un número primo divide a L , entonces debe dividir al menos un factor de L . Por el contrario, si un número w es coprimo con cada uno de una serie de números a ₁ , a ₂ , ..., a _n , entonces w también es coprimo con su producto, a ₁  ×  a ₂  × ... ×  a _n . ^[64]

El lema de Euclides es suficiente para demostrar que cada número tiene una factorización única en números primos. ^[65] Para ver esto, supongamos lo contrario, que hay dos factorizaciones independientes de L en m y n factores primos, respectivamente.

L = p ₁ p ₂ … pm = q ₁ q ₂ … q _n  ._​

Como cada primo p divide a L por supuesto, también debe dividir a uno de los factores q ; como cada q también es primo, debe ser que p  =  q . Dividiendo iterativamente por los factores p se muestra que cada p tiene una contraparte igual q ; las dos factorizaciones primas son idénticas excepto por su orden. La factorización única de números en primos tiene muchas aplicaciones en demostraciones matemáticas, como se muestra a continuación.

Las ecuaciones diofánticas son ecuaciones en las que las soluciones están restringidas a números enteros; reciben su nombre del matemático alejandrino del siglo III Diofanto . ^[66] Una ecuación diofántica lineal típica busca números enteros x e y tales que ^[67]

hacha + por = c

donde a , b y c son números enteros dados. Esto se puede escribir como una ecuación para x en aritmética modular :

ax ≡ c mod b .

Sea g el máximo común divisor de a y b . Ambos términos en ax  +  by son divisibles por g ; por lo tanto, c también debe ser divisible por g , o la ecuación no tiene soluciones. Al dividir ambos lados por c / g , la ecuación se puede reducir a la identidad de Bezout.

sa + tb = g

donde s y t se pueden encontrar mediante el algoritmo euclidiano extendido . ^[68] Esto proporciona una solución a la ecuación diofántica, x ₁  =  s ( c / g ) e y 1 ₌  t  ( c / g ) .

En general, una ecuación diofántica lineal no tiene soluciones, o tiene un número infinito de soluciones. ^[69] Para encontrar esta última, considere dos soluciones, ( x ₁ ,  y ₁ ) y ( x ₂ ,  y ₂ ), donde

ax ₁ + por ₁ = c = ax ₂ + por ₂

o equivalentemente

un ( x ₁ - x ₂ ) = segundo ( y ₂ - y ₁ ).

Por lo tanto, la diferencia más pequeña entre dos soluciones x es b / g , mientras que la diferencia más pequeña entre dos soluciones y es a / g . Por lo tanto, las soluciones pueden expresarse como

x = x ₁ − bu / g

y = y1 + au / g ._​

Al permitir que u varíe sobre todos los números enteros posibles, se puede generar una familia infinita de soluciones a partir de una única solución ( x ₁ ,  y ₁ ). Si se requiere que las soluciones sean números enteros positivos ( x  > 0,  y  > 0), solo puede ser posible un número finito de soluciones. Esta restricción en las soluciones aceptables permite que algunos sistemas de ecuaciones diofánticas con más incógnitas que ecuaciones tengan un número finito de soluciones; ^[70] esto es imposible para un sistema de ecuaciones lineales cuando las soluciones pueden ser cualquier número real (ver Sistema subdeterminado ).

Un cuerpo finito es un conjunto de números con cuatro operaciones generalizadas. Las operaciones se llaman adición, sustracción, multiplicación y división y tienen sus propiedades usuales, tales como conmutatividad , asociatividad y distributividad . Un ejemplo de cuerpo finito es el conjunto de 13 números {0, 1, 2, ..., 12} utilizando aritmética modular . En este cuerpo, los resultados de cualquier operación matemática (suma, resta, multiplicación o división) se reducen módulo 13; es decir, se suman o restan múltiplos de 13 hasta que el resultado se lleva dentro del rango de 0 a 12. Por ejemplo, el resultado de 5 × 7 = 35 mod 13 = 9. Tales cuerpos finitos pueden definirse para cualquier primo p ; utilizando definiciones más sofisticadas, también pueden definirse para cualquier potencia m de un primo p ^m . Los cuerpos finitos a menudo se denominan cuerpos de Galois y se abrevian como GF( p ) o GF( p ^m ).  

En un cuerpo con m números, cada elemento distinto de cero a tiene un inverso multiplicativo modular único , a ⁻¹ tal que aa ⁻¹  =  a ⁻¹ a  ≡ 1 mod  m . Este inverso se puede encontrar resolviendo la ecuación de congruencia ax  ≡ 1 mod  m , ^[71] o la ecuación diofántica lineal equivalente ^[72]

hacha + mi = 1.

Esta ecuación se puede resolver mediante el algoritmo euclidiano, como se describió anteriormente. Encontrar inversos multiplicativos es un paso esencial en el algoritmo RSA , que se usa ampliamente en el comercio electrónico ; específicamente, la ecuación determina el entero utilizado para descifrar el mensaje. ^[73] Aunque el algoritmo RSA usa anillos en lugar de campos, el algoritmo euclidiano todavía se puede usar para encontrar un inverso multiplicativo donde exista uno. El algoritmo euclidiano también tiene otras aplicaciones en códigos de corrección de errores ; por ejemplo, se puede usar como una alternativa al algoritmo Berlekamp–Massey para decodificar códigos BCH y Reed–Solomon , que se basan en campos de Galois. ^[74]

El algoritmo de Euclides también se puede utilizar para resolver múltiples ecuaciones diofánticas lineales. ^[75] Tales ecuaciones surgen en el teorema del resto chino , que describe un nuevo método para representar un número entero x . En lugar de representar un número entero por sus dígitos, se puede representar por sus restos x _i módulo un conjunto de N números coprimos m _i : ^[76]

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}$

El objetivo es determinar x a partir de sus N residuos x _i . La solución es combinar las ecuaciones múltiples en una única ecuación diofántica lineal con un módulo M mucho mayor que es el producto de todos los módulos individuales m _i , y definir M _i como

${\displaystyle M_{i}={\frac {M}{m_{i}}}.}$

Por lo tanto, cada M _i es el producto de todos los módulos excepto m _i . La solución depende de encontrar N nuevos números h _i tales que

${\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}$

Con estos números h _i , cualquier entero x puede reconstruirse a partir de sus residuos x _i mediante la ecuación

${\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}$

Dado que estos números h _i son los inversos multiplicativos de M _i , se pueden encontrar utilizando el algoritmo de Euclides como se describe en la subsección anterior.

El algoritmo de Euclides se puede utilizar para organizar el conjunto de todos los números racionales positivos en un árbol binario de búsqueda infinito , llamado árbol de Stern-Brocot . El número 1 (expresado como una fracción 1/1) se coloca en la raíz del árbol, y la ubicación de cualquier otro número a / b se puede encontrar calculando mcd( a , b ) utilizando la forma original del algoritmo de Euclides, en la que cada paso reemplaza el mayor de los dos números dados por su diferencia con el número menor (no su resto), deteniéndose cuando se alcanzan dos números iguales. Un paso del algoritmo de Euclides que reemplaza el primero de los dos números corresponde a un paso en el árbol desde un nodo a su hijo derecho, y un paso que reemplaza el segundo de los dos números corresponde a un paso en el árbol desde un nodo a su hijo izquierdo. La secuencia de pasos construida de esta manera no depende de si a / b se da en términos mínimos, y forma una ruta desde la raíz a un nodo que contiene el número a / b . ^[77] Este hecho se puede utilizar para demostrar que cada número racional positivo aparece exactamente una vez en este árbol.

Por ejemplo, 3/4 se puede encontrar comenzando desde la raíz, yendo hacia la izquierda una vez y luego hacia la derecha dos veces:

${\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}$

El algoritmo euclidiano tiene casi la misma relación con otro árbol binario de números racionales llamado árbol de Calkin-Wilf . La diferencia es que el camino se invierte: en lugar de producir un camino desde la raíz del árbol hasta un objetivo, produce un camino desde el objetivo hasta la raíz.

El algoritmo euclidiano tiene una estrecha relación con las fracciones continuas . ^[78] La secuencia de ecuaciones se puede escribir en la forma

${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}$

El último término del lado derecho siempre es igual al inverso del lado izquierdo de la siguiente ecuación. Por lo tanto, las dos primeras ecuaciones pueden combinarse para formar

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}$

La tercera ecuación se puede utilizar para sustituir el término denominador r ₁ / r ₀ , obteniéndose

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}$

La razón final de los residuos r _k / r _{k −1} siempre se puede sustituir utilizando la siguiente ecuación de la serie, hasta la ecuación final. El resultado es una fracción continua

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}$

En el ejemplo resuelto anteriormente, se calculó el mcd(1071, 462) y los cocientes q _k fueron 2, 3 y 7, respectivamente. Por lo tanto, la fracción 1071/462 puede escribirse

${\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}$

como se puede confirmar mediante cálculo.

Calcular un máximo común divisor es un paso esencial en varios algoritmos de factorización de números enteros , ^[79] como el algoritmo rho de Pollard , ^[80] el algoritmo de Shor , ^[81] el método de factorización de Dixon ^[82] y la factorización de curva elíptica de Lenstra . ^[83] El algoritmo euclidiano puede utilizarse para encontrar este MCD de manera eficiente. La factorización de fracciones continuas utiliza fracciones continuas, que se determinan utilizando el algoritmo de Euclides. ^[84]

La eficiencia computacional del algoritmo de Euclides ha sido estudiada a fondo. ^[85] Esta eficiencia puede describirse por el número de pasos de división que requiere el algoritmo, multiplicado por el gasto computacional de cada paso. El primer análisis conocido del algoritmo de Euclides se debe a AAL Reynaud en 1811, ^[86] quien demostró que el número de pasos de división en la entrada ( u , v ) está acotado por v ; más tarde mejoró esto a v /2 + 2. Más tarde, en 1841, PJE Finck demostró ^[87] que el número de pasos de división es como máximo 2 log ₂  v  + 1, y por lo tanto el algoritmo de Euclides se ejecuta en un polinomio de tiempo en el tamaño de la entrada. ^[88] Émile Léger , en 1837, estudió el peor caso, que es cuando las entradas son números consecutivos de Fibonacci . ^[88] El análisis de Finck fue refinado por Gabriel Lamé en 1844, ^[89] quien demostró que el número de pasos necesarios para completarlo nunca es más de cinco veces el número h de dígitos de base 10 del número más pequeño  b . ^{[90] [91]}

En el modelo de costo uniforme (adecuado para analizar la complejidad del cálculo del MCD en números que caben en una sola palabra de máquina), cada paso del algoritmo toma un tiempo constante , y el análisis de Lamé implica que el tiempo total de ejecución también es O ( h ). Sin embargo, en un modelo de cálculo adecuado para el cálculo con números más grandes, el gasto computacional de un solo cálculo de resto en el algoritmo puede ser tan grande como O ( h ² ). ^[92] En este caso, el tiempo total para todos los pasos del algoritmo se puede analizar utilizando una serie telescópica , mostrando que también es O ( h ² ). Las técnicas algorítmicas modernas basadas en el algoritmo de Schönhage-Strassen para la multiplicación rápida de números enteros se pueden utilizar para acelerar esto, lo que conduce a algoritmos cuasilineales para el MCD. ^{[93] [94]}

El número de pasos para calcular el MCD de dos números naturales, a y b , puede denotarse por T ( a ,  b ). ^[95] Si g es el MCD de a y b , entonces a  =  mg y b  =  ng para dos números coprimos m y n . Entonces

T ( a , b ) = T ( m , n )

como se puede ver al dividir todos los pasos en el algoritmo euclidiano por g . ^[96] Por el mismo argumento, el número de pasos permanece igual si a y b se multiplican por un factor común w : T ( a , b ) = T ( wa , wb ). Por lo tanto, el número de pasos T puede variar drásticamente entre pares de números vecinos, como T( a , b ) y T( a ,  b  + 1), dependiendo del tamaño de los dos MCD.

La naturaleza recursiva del algoritmo euclidiano da otra ecuación

T ( a , b ) = 1 + T ( b , r ₀ ) = 2 + T ( r ₀ , r ₁ ) = … = N + T ( r _{N −2} , r _{N −1} ) = N + 1

donde T ( x , 0) = 0 por suposición. ^[95]

Si el algoritmo euclidiano requiere N pasos para un par de números naturales a  >  b  > 0, los valores más pequeños de a y b para los que esto es cierto son los números de Fibonacci F _{N +2} y F _{N +1} , respectivamente. ^[97] Más precisamente, si el algoritmo euclidiano requiere N pasos para el par a  >  b , entonces uno tiene a  ≥  F _{N +2} y b  ≥  F _{N +1} . Esto se puede demostrar por inducción . ^[98] Si N  = 1, b divide a a sin resto; los números naturales más pequeños para los que esto es cierto son b  = 1 y a  = 2, que son F ₂ y F ₃ , respectivamente. Ahora supongamos que el resultado se cumple para todos los valores de N hasta M  − 1. El primer paso del algoritmo de M pasos es a  =  q ₀ b  +  r ₀ , y el algoritmo euclidiano requiere M  − 1 pasos para el par b  >  r ₀ . Por hipótesis de inducción, se tiene b  ≥  F _{M +1} y r ₀  ≥  F _M . Por lo tanto, a  =  q ₀ b  +  r ₀  ≥  b  +  r ₀  ≥  F _{M +1}  +  F _M  =  F _{M +2} , que es la desigualdad buscada. Esta demostración, publicada por Gabriel Lamé en 1844, representa el comienzo de la teoría de la complejidad computacional [ ^99] y también la primera aplicación práctica de los números de Fibonacci ^{[97] .}

Este resultado es suficiente para demostrar que el número de pasos en el algoritmo de Euclides nunca puede ser mayor que cinco veces el número de sus dígitos (base 10). ^[100] Porque si el algoritmo requiere N pasos, entonces b es mayor o igual que F _{N +1} que a su vez es mayor o igual que φ ^{N −1} , donde φ es la proporción áurea . Como b  ≥  φ ^{N −1} , entonces N  − 1 ≤ log _φ b . Como log ₁₀ φ  > 1/5, ( N  − 1)/5 < log ₁₀ φ  log _φ b  = log ₁₀ b . Por lo tanto, N  ≤ 5 log ₁₀ b . Por lo tanto, el algoritmo euclidiano siempre necesita menos de O ( h ) divisiones, donde h es el número de dígitos en el número más pequeño b .

El número medio de pasos que da el algoritmo euclidiano se ha definido de tres formas diferentes. La primera definición es el tiempo medio T ( a ) necesario para calcular el MCD de un número dado a y un número natural menor b elegido con igual probabilidad entre los números enteros 0 a a  − 1 ^[95]

${\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).}$

Sin embargo, dado que T ( a ,  b ) fluctúa dramáticamente con el MCD de los dos números, la función promedio T ( a ) es igualmente "ruidosa". ^[101]

Para reducir este ruido, se toma un segundo promedio τ ( a ) sobre todos los números coprimos con a

${\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).}$

Hay φ ( a ) números enteros coprimos menores que a , donde φ es la función totiente de Euler . Esta media tau crece suavemente con a ^{[102] [103]}

${\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon })}$

con un error residual de orden a ^{−(1/6) + ε} , donde ε es infinitesimal . La constante C en esta fórmula se denomina constante de Porter ^[104] y es igual a

${\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}$

donde γ es la constante de Euler-Mascheroni y ζ' es la derivada de la función zeta de Riemann . ^{[105] [106]} El coeficiente principal (12/π ² ) ln 2 se determinó mediante dos métodos independientes. ^{[107] [108]}

Dado que el primer promedio se puede calcular a partir del promedio tau sumando los divisores d de  a ^[109]

${\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}$

Se puede aproximar mediante la fórmula ^[110]

${\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}}$

donde Λ( d ) es la función de Mangoldt . ^[111]

Un tercer promedio Y ( n ) se define como el número medio de pasos necesarios cuando tanto a como b se eligen aleatoriamente (con distribución uniforme) de 1 a n ^[110].

${\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).}$

Sustituyendo la fórmula aproximada para T ( a ) en esta ecuación se obtiene una estimación para Y ( n ) ^[112]

${\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.}$

En cada paso k del algoritmo euclidiano, se calculan el cociente q _k y el resto r _k para un par dado de números enteros r _{k −2} y r _{k −1.}

rk ₋₂ = qk _{rk −1} + rk ._​​_​​

El gasto computacional por paso está asociado principalmente con encontrar q _k , ya que el resto r _k se puede calcular rápidamente a partir de r _{k −2} , r _{k −1} y q _k

rk = rk ₋₂ − qk _{rk −1} ._​​​_​

El gasto computacional de dividir números de h bits se escala como O ( h ( ℓ +1)) , donde ℓ es la longitud del cociente. ^[92]

A modo de comparación, el algoritmo original de Euclides basado en la resta puede ser mucho más lento. Una única división entera es equivalente al cociente q número de restas. Si la razón de a y b es muy grande, el cociente es grande y se requerirán muchas restas. Por otro lado, se ha demostrado que es muy probable que los cocientes sean enteros pequeños. La probabilidad de un cociente dado q es aproximadamente ln | u /( u − 1)| donde u = ( q + 1) ² . ^[113] A modo de ilustración, la probabilidad de un cociente de 1, 2, 3 o 4 es aproximadamente 41,5 %, 17,0 %, 9,3 % y 5,9 %, respectivamente. Dado que la operación de resta es más rápida que la división, particularmente para números grandes, ^[114] el algoritmo de Euclides basado en la resta es competitivo con la versión basada en la división. ^[115] Esto se explota en la versión binaria del algoritmo de Euclides. ^[116]

Combinando el número estimado de pasos con el gasto computacional estimado por paso se muestra que el algoritmo de Euclides crece cuadráticamente ( h ² ) con el número promedio de dígitos h en los dos números iniciales a y b . Sea h ₀ , h ₁ , ..., h _{N −1} el número de dígitos en los residuos sucesivos r ₀ , r ₁ , ..., r _{N −1} . Dado que el número de pasos N crece linealmente con h , el tiempo de ejecución está limitado por

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}$

El algoritmo de Euclides se utiliza ampliamente en la práctica, especialmente para números pequeños, debido a su simplicidad. ^[117] A modo de comparación, se puede determinar la eficiencia de las alternativas al algoritmo de Euclides.

Un método ineficiente para hallar el MCD de dos números naturales a y b es calcular todos sus divisores comunes; el MCD es entonces el máximo común divisor. Los divisores comunes se pueden hallar dividiendo ambos números por enteros sucesivos desde 2 hasta el número más pequeño b . El número de pasos de este método crece linealmente con b , o exponencialmente en el número de dígitos. Otro método ineficiente es hallar los factores primos de uno o ambos números. Como se señaló anteriormente, el MCD es igual al producto de los factores primos compartidos por los dos números a y b . ^[8] Los métodos actuales de factorización prima también son ineficientes; muchos sistemas criptográficos modernos incluso se basan en esa ineficiencia. ^[11]

El algoritmo binario MCD es una alternativa eficiente que sustituye la división con operaciones más rápidas explotando la representación binaria utilizada por las computadoras. ^{[118] [119]} Sin embargo, esta alternativa también escala como O ( h ²) . Generalmente es más rápido que el algoritmo euclidiano en computadoras reales, aunque escala de la misma manera. ^[93] Se puede obtener eficiencia adicional examinando solo los dígitos iniciales de los dos números a y b . ^{[120] [121]} El algoritmo binario se puede extender a otras bases ( algoritmos k -arios), ^[122] con aumentos de velocidad de hasta cinco veces. ^[123] El algoritmo MCD de Lehmer usa el mismo principio general que el algoritmo binario para acelerar los cálculos de MCD en bases arbitrarias.

Un enfoque recursivo para números enteros muy grandes (con más de 25.000 dígitos) conduce a algoritmos MCD de números enteros cuasilineales , ^[124] como los de Schönhage, ^{[125] [126]} y Stehlé y Zimmermann. ^[127] Estos algoritmos explotan la forma matricial 2×2 del algoritmo euclidiano dado anteriormente. Estos métodos cuasilineales generalmente escalan como O ( h log h ² log log h ). ^{[93] [94]}

Aunque el algoritmo euclidiano se utiliza para encontrar el máximo común divisor de dos números naturales (enteros positivos), puede generalizarse a los números reales y a otros objetos matemáticos, como polinomios , ^[128] números enteros cuadráticos ^[129] y cuaterniones de Hurwitz . ^[130] En estos últimos casos, el algoritmo euclidiano se utiliza para demostrar la propiedad crucial de la factorización única, es decir, que dichos números pueden factorizarse de forma única en elementos irreducibles , las contrapartes de los números primos. La factorización única es esencial para muchas pruebas de la teoría de números.

El algoritmo de Euclides se puede aplicar a los números reales , como lo describe Euclides en el Libro 10 de sus Elementos . El objetivo del algoritmo es identificar un número real g tal que dos números reales dados, a y b , sean múltiplos enteros de él: a = mg y b = ng , donde m y n son números enteros . ^[28] Esta identificación es equivalente a encontrar una relación entera entre los números reales a y b ; es decir, determina los números enteros s y t tales que sa + tb = 0. Si tal ecuación es posible, a y b se denominan longitudes conmensurables; de lo contrario, son longitudes inconmensurables . ^{[131] [132]}

El algoritmo euclidiano de los números reales difiere de su homólogo de los números enteros en dos aspectos. En primer lugar, los residuos r _k son números reales, aunque los cocientes q _k son números enteros como antes. En segundo lugar, no se garantiza que el algoritmo termine en un número finito N de pasos. Si lo hace, la fracción a / b es un número racional, es decir, el cociente de dos números enteros.

${\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}$

y puede escribirse como una fracción continua finita [ q ₀ ; q ₁ , q ₂ , ..., q _N ] . Si el algoritmo no se detiene, la fracción a / b es un número irracional y puede describirse como una fracción continua infinita [ q ₀ ; q ₁ , q ₂ , …] . ^[133] Ejemplos de fracciones continuas infinitas son la proporción áurea φ = [1; 1, 1, ...] y la raíz cuadrada de dos , √ 2 = [1; 2, 2, ...] . ^[134] Es poco probable que el algoritmo se detenga, ya que casi todas las proporciones a / b de dos números reales son irracionales. ^[135]

Una fracción continua infinita puede truncarse en un paso k [ q ₀ ; q ₁ , q ₂ , ..., q _k ] para obtener una aproximación a a / b que mejora a medida que se incrementa k . La aproximación se describe mediante convergentes m _k / n _k ; el numerador y los denominadores son coprimos y obedecen a la relación de recurrencia

${\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}$

donde m ₋₁ = n ₋₂ = 1 y m ₋₂ = n ₋₁ = 0 son los valores iniciales de la recursión. El convergente m _k / n _k es la mejor aproximación racional a a / b con denominador n _k : ^[136]

${\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.}$

Los polinomios de una sola variable x se pueden sumar, multiplicar y factorizar en polinomios irreducibles , que son los análogos de los números primos para los números enteros. El polinomio máximo común divisor g ( x ) de dos polinomios a ( x ) y b ( x ) se define como el producto de sus polinomios irreducibles compartidos, que se pueden identificar utilizando el algoritmo euclidiano. ^[128] El procedimiento básico es similar al de los números enteros. En cada paso k , se identifican un polinomio cociente q _k ( x ) y un polinomio resto r _k ( x ) para satisfacer la ecuación recursiva

${\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}$

donde r ₋₂ ( x ) = a ( x ) y r ₋₁ ( x ) = b ( x ) . Cada polinomio cociente se elige de modo que cada residuo sea cero o tenga un grado menor que el grado de su predecesor: deg[ r _k ( x )] < deg[ r _{k −1} ( x )] . Dado que el grado es un entero no negativo, y dado que disminuye con cada paso, el algoritmo euclidiano concluye en un número finito de pasos. El último residuo distinto de cero es el máximo común divisor de los dos polinomios originales, a ( x ) y b ( x ) . ^[137]

Por ejemplo, considere los siguientes dos polinomios cuárticos, cada uno de los cuales se factoriza en dos polinomios cuadráticos.

${\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}$

Dividir a ( x ) por b ( x ) da como resultado r ₀ ( x ) = x ³ + (2/3) x ² + (5/3) x − (2/3) . En el siguiente paso, dividir b ( x ) por r ₀ ( x ) da como resultado r ₁ ( x ) = x ² + x + 2 . Finalmente, dividir r ₀ ( x ) por r ₁ ( x ) da como resultado cero, lo que indica que r ₁ ( x ) es el máximo común divisor polinomial de a ( x ) y b ( x ) , lo que es coherente con su factorización.

Muchas de las aplicaciones descritas anteriormente para números enteros se trasladan a los polinomios. ^[138] El algoritmo euclidiano se puede utilizar para resolver ecuaciones diofánticas lineales y problemas de resto chino para polinomios; también se pueden definir fracciones continuas de polinomios.

El algoritmo euclidiano polinomial tiene otras aplicaciones, como las cadenas de Sturm , un método para contar los ceros de un polinomio que se encuentran dentro de un intervalo real dado . ^[139] Esto a su vez tiene aplicaciones en varias áreas, como el criterio de estabilidad de Routh-Hurwitz en la teoría de control . ^[140]

Por último, los coeficientes de los polinomios no tienen por qué extraerse necesariamente de números enteros, números reales o incluso números complejos. Por ejemplo, los coeficientes pueden extraerse de un campo general, como los campos finitos GF( p ) descritos anteriormente. Las conclusiones correspondientes sobre el algoritmo euclidiano y sus aplicaciones son válidas incluso para tales polinomios. ^[128]

Los números enteros gaussianos son números complejos de la forma α = u + vi , donde u y v son números enteros ordinarios ^{[nota 2]} e i es la raíz cuadrada de menos uno . ^[141] Al definir un análogo del algoritmo euclidiano, se puede demostrar que los números enteros gaussianos son factorizables de forma única, mediante el argumento anterior. ^[42] Esta factorización única es útil en muchas aplicaciones, como la derivación de todos los triples pitagóricos o la demostración del teorema de Fermat sobre sumas de dos cuadrados . ^[141] En general, el algoritmo euclidiano es conveniente en tales aplicaciones, pero no esencial; por ejemplo, los teoremas a menudo se pueden demostrar mediante otros argumentos.

El algoritmo euclidiano desarrollado para dos números enteros gaussianos α y β es casi el mismo que el de los números enteros ordinarios, ^[142] pero difiere en dos aspectos. Como antes, fijamos r ₋₂ = α y r ₋₁ = β , y la tarea en cada paso k es identificar un cociente q _k y un resto r _k tales que

${\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}$

donde cada resto es estrictamente menor que su predecesor: | r _k | < | r _{k −1} | . La primera diferencia es que los cocientes y los restos son en sí mismos números enteros gaussianos y, por lo tanto, son números complejos . Los cocientes q _k se encuentran generalmente redondeando las partes reales y complejas de la razón exacta (como el número complejo α / β ) a los números enteros más cercanos. ^[142] La segunda diferencia radica en la necesidad de definir cómo un resto complejo puede ser "más pequeño" que otro. Para hacer esto, se define una función norma f ( u + vi ) = u ² + v ^{2 , que convierte cada entero gaussiano} u + vi en un entero ordinario. Después de cada paso k del algoritmo euclidiano, la norma del resto f ( r _k ) es menor que la norma del resto precedente, f ( r _{k −1} ) . Como la norma es un entero no negativo y disminuye con cada paso, el algoritmo euclidiano para enteros gaussianos termina en un número finito de pasos. ^[143] El resto final distinto de cero es mcd( α , β ) , el entero gaussiano de norma más grande que divide tanto a α como a β ; es único hasta la multiplicación por una unidad, ±1 o ± i . ^[144]

Muchas de las otras aplicaciones del algoritmo euclidiano se trasladan a los números enteros gaussianos. Por ejemplo, se puede utilizar para resolver ecuaciones diofánticas lineales y problemas de resto chino para números enteros gaussianos; ^[145] también se pueden definir fracciones continuas de números enteros gaussianos. ^[142]

Un conjunto de elementos bajo dos operaciones binarias , denotadas como adición y multiplicación, se llama dominio euclidiano si forma un anillo conmutativo R y, en términos generales, si se puede realizar un algoritmo euclidiano generalizado sobre ellos. ^{[146] [147]} Las dos operaciones de dicho anillo no necesitan ser la adición y la multiplicación de la aritmética ordinaria; más bien, pueden ser más generales, como las operaciones de un grupo matemático o monoide . Sin embargo, estas operaciones generales deben respetar muchas de las leyes que gobiernan la aritmética ordinaria, como la conmutatividad , la asociatividad y la distributividad .

El algoritmo euclidiano generalizado requiere una función euclidiana , es decir, una aplicación f de R en el conjunto de números enteros no negativos tales que, para dos elementos distintos de cero a y b en R , existen q y r en R tales que a = qb + r y f ( r ) < f ( b ) . ^[148] Ejemplos de tales aplicaciones son el valor absoluto para números enteros, el grado para polinomios univariados y la norma para números enteros gaussianos anteriores. ^{[149] [150]} El principio básico es que cada paso del algoritmo reduce f inexorablemente; por lo tanto, si f puede reducirse solo un número finito de veces, el algoritmo debe detenerse en un número finito de pasos. Este principio se basa en la propiedad de buen orden de los números enteros no negativos, que afirma que cada conjunto no vacío de números enteros no negativos tiene un miembro más pequeño. ^[151]

El teorema fundamental de la aritmética se aplica a cualquier dominio euclidiano: cualquier número de un dominio euclidiano se puede factorizar de forma única en elementos irreducibles . Cualquier dominio euclidiano es un dominio de factorización única (UFD), aunque lo inverso no es cierto. ^[151] Los dominios euclidianos y los UFD son subclases de los dominios MCD , dominios en los que siempre existe un máximo común divisor de dos números. ^[152] En otras palabras, puede existir un máximo común divisor (para todos los pares de elementos en un dominio), aunque puede que no sea posible encontrarlo usando un algoritmo euclidiano. Un dominio euclidiano es siempre un dominio ideal principal (PID), un dominio integral en el que cada ideal es un ideal principal . ^[153] Una vez más, lo inverso no es cierto: no todo PID es un dominio euclidiano.

La factorización única de los dominios euclidianos es útil en muchas aplicaciones. Por ejemplo, la factorización única de los números enteros gaussianos es conveniente para derivar fórmulas para todos los triples pitagóricos y para demostrar el teorema de Fermat sobre sumas de dos cuadrados . ^[141] La factorización única también fue un elemento clave en un intento de prueba del último teorema de Fermat publicado en 1847 por Gabriel Lamé, el mismo matemático que analizó la eficiencia del algoritmo de Euclides, basado en una sugerencia de Joseph Liouville . ^[154] El enfoque de Lamé requería la factorización única de números de la forma x + ωy , donde x e y son números enteros, y ω = e ^{2 iπ / n} es una raíz n ésima de 1, es decir, ω ⁿ = 1 . Aunque este enfoque tiene éxito para algunos valores de n (como n = 3 , los enteros de Eisenstein ), en general, dichos números no se factorizan de forma única. Este fracaso de la factorización única en algunos campos ciclotómicos llevó a Ernst Kummer al concepto de números ideales y, más tarde, a Richard Dedekind al de ideales . ^[155]

Los anillos de números enteros cuadráticos son útiles para ilustrar los dominios euclidianos. Los números enteros cuadráticos son generalizaciones de los números enteros gaussianos en los que la unidad imaginaria i se reemplaza por un número ω . Por lo tanto, tienen la forma u + vω , donde u y v son números enteros y ω tiene una de dos formas, dependiendo de un parámetro D . Si D no es igual a un múltiplo de cuatro más uno, entonces

${\displaystyle \omega ={\sqrt {D}}.}$

Sin embargo, si D es igual a un múltiplo de cuatro más uno, entonces

${\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}.}$

Si la función f corresponde a una función norma , como la utilizada para ordenar los enteros gaussianos anteriores, entonces el dominio se conoce como norma-euclidiana . Los anillos norma-euclidianos de los enteros cuadráticos son exactamente aquellos donde D es uno de los valores −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 o 73. ^{[156] [157]} Los casos D = −1 y D = −3 producen los enteros gaussianos y los enteros de Eisenstein , respectivamente.

Si se permite que f sea cualquier función euclidiana, entonces la lista de posibles valores de D para los cuales el dominio es euclidiano aún no se conoce. ^[158] El primer ejemplo de un dominio euclidiano que no era norma-euclidiano (con D = 69 ) se publicó en 1994. ^[158] En 1973, Weinberger demostró que un anillo entero cuadrático con D > 0 es euclidiano si, y solo si, es un dominio ideal principal , siempre que se cumpla la hipótesis generalizada de Riemann . ^[129]

El algoritmo euclidiano puede aplicarse a algunos anillos no conmutativos, como el conjunto de cuaterniones de Hurwitz . ^{[130] [159]} Sean α y β dos elementos de dicho anillo. Tienen un divisor derecho común δ si α = ξδ y β = ηδ para alguna elección de ξ y η en el anillo. De manera similar, tienen un divisor izquierdo común si α = dξ y β = dη para alguna elección de ξ y η en el anillo. Dado que la multiplicación no es conmutativa, hay dos versiones del algoritmo euclidiano, una para divisores derechos y otra para divisores izquierdos. ^{[130] [159]} Al elegir los divisores derechos, el primer paso para encontrar el mcd( α , β ) mediante el algoritmo euclidiano se puede escribir

${\displaystyle \rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,}$

donde ψ ₀ representa el cociente y ρ ₀ el resto. Aquí el cociente y el resto se eligen de modo que (si no es cero) el resto tenga N ( ρ ₀ ) < N ( β ) para una "función euclidiana" N definida de manera análoga a las funciones euclidianas de los dominios euclidianos en el caso no conmutativo. ^[159] Esta ecuación muestra que cualquier divisor común por la derecha de α y β es asimismo un divisor común del resto ρ ₀ . La ecuación análoga para los divisores por la izquierda sería

${\displaystyle \rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).}$

Con cualquiera de las dos opciones, el proceso se repite como se indicó anteriormente hasta que se identifique el máximo común divisor derecho o izquierdo. Como en el dominio euclidiano, el "tamaño" del resto ρ ₀ (formalmente, su función euclidiana o "norma") debe ser estrictamente menor que β , y debe haber solo un número finito de tamaños posibles para ρ ₀ , de modo que se garantice que el algoritmo terminará. ^[160]

Muchos resultados del MCD se trasladan a números no conmutativos. Por ejemplo, la identidad de Bézout establece que el mcd recto ( α , β ) se puede expresar como una combinación lineal de α y β . ^[161] En otras palabras, hay números σ y τ tales que

${\displaystyle \Gamma _{\text{right}}=\sigma \alpha +\tau \beta .}$

La identidad análoga para el MCD izquierdo es casi la misma:

${\displaystyle \Gamma _{\text{left}}=\alpha \sigma +\beta \tau .}$

La identidad de Bézout se puede utilizar para resolver ecuaciones diofánticas. Por ejemplo, una de las pruebas estándar del teorema de los cuatro cuadrados de Lagrange , que establece que todo entero positivo se puede representar como una suma de cuatro cuadrados, se basa en MCD de cuaterniones de esta manera. ^[160]

• Ritmo euclidiano , un método para utilizar el algoritmo euclidiano para generar ritmos musicales