algoritmo euclidiano

Algoritmo para calcular los máximos divisores comunes

Método de Euclides para encontrar el máximo común divisor (MCD) de dos longitudes iniciales BA y DC, ambas definidas como múltiplos de una longitud "unitaria" común. Al ser la longitud DC más corta, se utiliza para "medir" BA, pero sólo una vez porque el resto EA es menor que DC. EA ahora mide (el doble) la longitud más corta de DC, y el resto FC es más corto que EA. Entonces FC mide (tres veces) la longitud EA. Como no hay resto, el proceso termina siendo FC el MCD. A la derecha, el ejemplo de Nicómaco con los números 49 y 21, lo que da como resultado su MCD de 7 (derivado de Heath 1908:300).

En matemáticas , el algoritmo euclidiano , ^{[nota 1]} o algoritmo de Euclides , es un método eficiente para calcular el máximo común divisor (MCD) de dos enteros (números), el mayor número que los divide a ambos sin resto . Lleva el 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 según 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 forma parte de muchos otros cálculos criptográficos y de teoría de números.

El algoritmo euclidiano 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 . Dado que este reemplazo reduce el mayor de los dos números, al repetir este proceso se obtienen pares de números sucesivamente más pequeños hasta que los dos números se vuelven iguales. Cuando eso ocurre, son el MCD de los dos números originales. Invirtiendo los pasos o usando el algoritmo euclidiano extendido , el MCD se puede expresar 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 número entero (por ejemplo, 21 = 5 × 105 + (-2) × 252 ). El hecho de que el GCD siempre pueda expresarse de esta manera se conoce como identidad de Bézout .

La versión del algoritmo euclidiano descrito anteriormente (y por Euclides) puede requerir 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 ataja estos pasos, reemplazando 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 cuando alcanza 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 inicio 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 euclidiano 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 métodos para romper estos criptosistemas factorizando grandes números compuestos . El algoritmo euclidiano se puede utilizar para resolver ecuaciones diofánticas , como encontrar números que satisfagan múltiples congruencias según el teorema del resto chino , construir fracciones continuas y encontrar aproximaciones racionales precisas a números reales. Finalmente, puede usarse como 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 se describió sólo para números naturales y longitudes geométricas (números reales), pero el algoritmo se generalizó en el siglo XIX a otros tipos de números, como los enteros gaussianos y los polinomios de una variable. Esto llevó a nociones algebraicas abstractas modernas como los dominios euclidianos .

Antecedentes: máximo común divisor

El algoritmo euclidiano 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 mayor número natural que divide a y b sin dejar resto. Los sinónimos de MCD incluyen máximo común divisor (MCD), máximo común divisor (HCF), máximo común divisor (HCD) y máxima medida común (MCG). El máximo común divisor suele escribirse como mcd( a ,  b ) o, más simplemente, como ( a ,  b ) , ^[3] aunque esta última notación es ambigua y también se utiliza para conceptos como un ideal en el anillo de números enteros , que está estrechamente relacionado con GCD.

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. .

Un rectángulo de 24×60 está cubierto con diez mosaicos cuadrados de 12×12, donde 12 es el MCD de 24 y 60. De manera más general, un rectángulo a × b se puede cubrir con mosaicos cuadrados de longitud de lado c sólo si c es un divisor de a y b .

Sea g = mcd( a ,  b ) . Dado que a y b son múltiplos de g , se pueden escribir a  =  mg y b  =  ng , y no existe un número mayor G  >  g para el que esto sea cierto. Los números naturales myn deben ser coprimos, ya que cualquier factor común podría factorizarse a partir de myn para hacer g mayor . Por lo tanto, cualquier otro número c que divida a y 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 exactamente a y b . Los lados del rectángulo se pueden dividir en segmentos de longitud c , lo que divide 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 12×12 cuadrados, 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 se puede repetir tantas veces como divida a a y b . ^[8] Por ejemplo, dado que 1386 se puede factorizar en 2 × 3 × 3 × 7 × 11 , y 3213 se puede factorizar 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 computacional muy difícil, y la seguridad de muchos protocolos criptográficos ampliamente utilizados se basa en su inviabilidad. ^[11]

Otra definición de MCD es útil en matemáticas avanzadas, particularmente en 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). De hecho, algunas propiedades del MCD son 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 GCD 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 muchos números enteros arbitrarios.

Descripción

Procedimiento

Se puede considerar que el algoritmo euclidiano construye una secuencia de números enteros no negativos que comienza con los dos números enteros dados y eventualmente 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 restos intermedios mediante división con resto en el par anterior encontrando un cociente entero de modo que: ${\displaystyle r_{-2}=a}$ ${\displaystyle 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}}$ ${\displaystyle r_{n-1}}$ ${\displaystyle {\text{gcd}}(a,b)=r_{n-1}}$ ${\displaystyle r_{k}}$ ${\displaystyle (r_{k-2},\ r_{k-1})}$ ${\displaystyle q_{k}}$

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

Debido a que la secuencia de números enteros no negativos es estrictamente decreciente, eventualmente debe terminar . En otras palabras, dado que para cada y cada uno es un número entero 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 n-ésimo paso igual a cero. ^[15] ${\displaystyle \{r_{k}\}}$ ${\displaystyle r_{k}\geq 0}$ ${\displaystyle k}$ ${\displaystyle r_{k}}$ ${\displaystyle r_{k-1}}$ ${\displaystyle r_{n}}$

Para ilustrar, 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\}}$ ${\displaystyle r_{0}}$ ${\displaystyle q_{0}}$ ${\displaystyle r_{0}<r_{-1}}$

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

Este es el cociente desde . Esto determina y así es la secuencia ahora . El siguiente paso es continuar la secuencia para encontrar 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\}}$ ${\displaystyle r_{1}}$ ${\displaystyle q_{1}}$ ${\displaystyle r_{1}<r_{0}}$

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

Este es el cociente desde . Esto determina y así es la secuencia ahora . El siguiente paso es continuar la secuencia para encontrar números enteros y tales que: ${\displaystyle q_{1}=3}$ ${\displaystyle 462=3\cdot 147+21}$ ${\displaystyle r_{1}=21}$ ${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}$ ${\displaystyle r_{2}}$ ${\displaystyle q_{2}}$ ${\displaystyle r_{2}<r_{1}}$

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

Este es el cociente desde . Esto determina y, por lo tanto, la secuencia se completa de manera que no se pueda encontrar ningún otro número entero no negativo más pequeño que el . El penúltimo resto es, por tanto, el MCD solicitado: ${\displaystyle q_{2}=7}$ ${\displaystyle 147=7\cdot 21+0}$ ${\displaystyle r_{2}=0}$ ${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$ ${\displaystyle 0}$ ${\displaystyle 21}$

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

Podemos generalizar ligeramente eliminando cualquier requisito de pedido en los dos valores iniciales y . Si , el algoritmo puede continuar y encontrar trivialmente que la secuencia de restos será . Si , entonces también podemos continuar desde , sugiriendo que el siguiente resto debería ser él mismo y la secuencia es . Normalmente, esto no sería válido porque infringe el requisito , pero ahora lo tenemos por construcción, por lo que el requisito se satisface automáticamente y el algoritmo euclidiano puede continuar con normalidad. Por lo tanto, eliminar cualquier orden entre los dos primeros números enteros no afecta la conclusión de que la secuencia debe terminar eventualmente porque el siguiente resto siempre será satisfactorio y todo continúa como se indicó anteriormente. Las únicas modificaciones que deben hacerse son que solo para y que la subsecuencia de enteros no negativos para es estrictamente decreciente, por lo que se excluye de ambas declaraciones. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a=b}$ ${\displaystyle {\text{gcd}}(a,\ a)=a}$ ${\displaystyle \{a,\ a,\ 0\}}$ ${\displaystyle a<b}$ ${\displaystyle a\equiv 0\cdot b+a}$ ${\displaystyle a}$ ${\displaystyle \{a,\ b,\ a,\ \cdots \}}$ ${\displaystyle r_{0}<r_{-1}}$ ${\displaystyle a<b}$ ${\displaystyle r_{0}<b}$ ${\displaystyle r_{k}<r_{k-1}}$ ${\displaystyle k\geq 0}$ ${\displaystyle \{r_{k-1}\}}$ ${\displaystyle k\geq 0}$ ${\displaystyle a=r_{-2}}$

Prueba de validez

La validez del algoritmo euclidiano se puede demostrar mediante un argumento de dos pasos. ^[16] En el primer paso, se muestra que el resto final distinto de cero r _{N −1} divide tanto a como b . Como 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 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 como b (el primer paso), r _{N −1} divide a su predecesor r _{N −2}

r _{norte −2} = q _norte r _{norte −1}

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

r _{norte −3} = q _{norte −1} r _{norte −2} + r _{norte −1}

porque divide ambos términos en el lado derecho de la ecuación. Iterando el mismo argumento, r _{N −1} divide todos los restos anteriores, incluidos a y b . Ninguno de los restos anteriores r _{N −2} , r _{N −3} , etc. dividen a y b , ya que dejan un resto. Dado que 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 como b (en otras palabras, cualquier divisor común de a y b ) divide los _restos rk . Por definición, a y b se pueden escribir como múltiplos de c  : a  =  mc y b  =  nc , donde myn son números naturales . Por lo tanto, c divide el resto 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 restos posteriores r ₁ , r ₂ , etc. Por lo tanto, el máximo común divisor g debe dividir r _{N −1} , lo que implica que g  ≤  r _{N −1} . Dado que la primera parte del argumento mostró lo contrario ( r _{N −1}  ≤  g ), se deduce que g  =  r _{N −1} . Por tanto, g es el máximo común divisor de todos los pares sucesivos: ^{[17] [18]}

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

Ejemplo resuelto

Animación basada en restas del algoritmo euclidiano. El rectángulo inicial tiene dimensiones a  = 1071 y b  = 462. Dentro de él se colocan cuadrados de tamaño 462 × 462, dejando un rectángulo de 462 × 147. Este rectángulo está revestido con cuadrados de 147 × 147 hasta que queda un rectángulo de 21 × 147, que a su vez está revestido con cuadrados de 21 × 21, sin dejar ningún área descubierta. El tamaño del cuadrado más pequeño, 21, es el MCD de 1071 y 462.

A modo de ilustración, se puede utilizar el algoritmo euclidiano para encontrar el máximo común divisor de a  = 1071 y b  = 462. Para empezar, se restan múltiplos de 462 de 1071 hasta que el resto sea menor que 462. Se pueden restar dos de esos múltiplos ( q ₀  = 2), dejando 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), quedando 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.

Dado que 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) encontrado mediante la factorización prima anterior. En forma tabular, los pasos son:

Visualización

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

división euclidiana

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

r _{k −2} = q _k r _{k −1} + r _k

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 garantiza que dicho cociente y resto siempre existen y son únicos. ^[20]

En la versión original del algoritmo de Euclides, el cociente y el resto se encuentran mediante resta 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, se intercambian r _k y r _{k −1} y se itera el proceso. La división euclidiana reduce todos los pasos entre dos intercambios a un solo paso, lo que por tanto es más eficiente. Además, los cocientes no son necesarios, por lo que se puede sustituir la división euclidiana por la operación módulo , que da sólo el resto. Así, la iteración del algoritmo euclidiano se vuelve simplemente

r _k = r _{k −2} mod r _{k −1} .

Implementaciones

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

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

Al comienzo de la k -ésima iteración, la variable b contiene el último resto rk ₋₁ , mientras que la variable _a contiene su predecesor _, rk ₋₂ . El paso b  := a mod b es equivalente a la fórmula recursiva anterior r _k ≡ r _{k −2} mod r _{k −1} . La variable temporal t contiene el valor de _rk −1 _{mientras se} calcula el siguiente resto rk . Al final de la iteración del bucle, la variable _b contiene el resto rk , 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 era 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 división, que funciona con números enteros arbitrarios como entrada, la versión basada en resta supone que la entrada consta de 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 un := un - segundo demás segundo := segundo - un devolver un

Las variables a y b se alternan manteniendo los restos 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 resto b anterior hasta que a sea menor que b . Entonces a es el siguiente resto r _k . Luego b se reduce en múltiplos de a hasta que vuelve a ser menor que a , dando _el siguiente resto rk ₊₁ , y así sucesivamente.

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

función mcd(a, b) si b = 0 devolver a else  devolver gcd(b, a mod b)

(Como arriba, 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 ilustración, el mcd(1071, 462) se calcula a partir del equivalente mcd(462, 1071 mod 462) = mcd(462, 147). Este último MCD se calcula a partir de mcd(147, 462 mod 147) = mcd(147, 21), que a su vez se calcula a partir de mcd(21, 147 mod 21) = mcd(21, 0) = 21.

Método de residuos mínimos absolutos

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

r _{k −2} = q _k r _{k −1} + r _k

asumió que | rk ₋₁ | _{_} >  rk  > 0 _. Sin embargo, se puede calcular un resto negativo alternativo e _{k :}

r _{k −2} = ( q _k + 1) r _{k −1} + mi _k

si r _{k −1}  > 0 o

r _{k −2} = ( q _k − 1) r _{k −1} + mi _k

si r _{k −1}  < 0 .

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

| rk | _{_} ≤ | rk ₋₁ | _{_} / 2

en cada paso.

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

Desarrollo historico

El algoritmo euclidiano probablemente se inventó antes que Euclides , representado aquí sosteniendo una brújula en una pintura de alrededor de 1474.

El algoritmo euclidiano 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, se 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 existe una unidad natural de longitud, área, o volumen; el concepto de números reales era desconocido en ese momento.) Este último algoritmo es geométrico. El MCD de dos longitudes a y b corresponde a la mayor longitud g que mide a y b uniformemente; en otras palabras, las longitudes a y b son múltiplos enteros de la longitud g .

El algoritmo probablemente no fue descubierto por Euclides , quien recopiló 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 ἀνθυφαίρεσις ( anthyphairesis , resta recíproca) en obras de Euclides y Aristóteles . ^[34]

Siglos más tarde, el algoritmo de Euclides se descubrió de forma independiente tanto en la India como en China, ^[35] principalmente para resolver ecuaciones diofánticas que surgieron en la 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 debido a su eficacia para resolver ecuaciones diofánticas. ^[37] Aunque un caso especial del teorema del resto chino ya se había descrito 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 euclidiano fue descrito numéricamente por primera vez y popularizado en Europa en la segunda edición de Problèmes plaisants et délectables de Bachet ( Problemas agradables y agradables , 1624). ^[36] En Europa, también se utilizó para resolver ecuaciones diofánticas y para desarrollar 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 enteros gaussianos y los enteros de Eisenstein . En 1815, Carl Gauss utilizó el algoritmo euclidiano para demostrar la factorización única de enteros gaussianos , aunque su trabajo se publicó por primera vez en 1832. ^[42] Gauss mencionó el algoritmo en sus Disquisitiones Arithmeticae (publicado en 1801), pero sólo como un método para fracciones continuas. . ^[35] Peter Gustav Lejeune Dirichlet parece haber sido el primero en describir el algoritmo euclidiano como 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 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 gradualmente eclipsado por la teoría más general de los ideales de Dedekind . ^[46]

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

El algoritmo euclidiano fue el primer algoritmo de relaciones enteras , que es un método para encontrar relaciones enteras entre números reales proporcionales. Se han desarrollado varios algoritmos novedosos de relación de enteros , 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 montones de piedras a y b . Los jugadores se turnan para sacar m múltiplos de la pila más pequeña de la más grande. Por lo tanto, si las dos pilas constan de piedras x e y , donde x es mayor que y , el siguiente jugador puede reducir la pila más grande de x piedras a x - mis piedras, siempre que este último sea un número entero no negativo. El ganador es el primer jugador que reduce una pila a cero piedras. ^{[53] [54]}

Aplicaciones matemáticas

La identidad de Bézout

La identidad de Bézout establece que el máximo común divisor g de dos números enteros a y b se puede representar como una suma lineal de los dos números originales a y b . ^[55] En otras palabras, siempre es posible encontrar 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 restos anteriores, r _{N −2} y r _{N −3} :

gramo = r _{norte −1} = r _{norte −3} − q _{norte −1} r _{norte −2}  .

Esos dos restos también se pueden expresar en términos de sus cocientes y restos anteriores,

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

r _{norte −3} = r _{norte −5} − q _{norte −3} r _{norte −4}  .

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

r ₂ = r ₀ − q ₂ r ₁

r ₁ = segundo - q ₁ r ₀

r ₀ = una - q ₀ segundo .

Después de sustituir todos los restos 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 Bezout, pueden generalizarse al contexto de los dominios euclidianos .

Ideales principales y problemas relacionados.

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

mg = msa + mtb .

Por tanto, el conjunto de todos los números ua  +  vb es equivalente al conjunto de los 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 ideal principal (un ideal generado por un solo elemento) y dominio de ideal principal (un dominio en el que cada ideal es un ideal principal).

Ciertos problemas se pueden resolver 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 . Todos estos volúmenes son múltiplos de g  = mcd( a ,  b ).

Algoritmo euclidiano extendido

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}

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

con los valores iniciales

s ₋₂ = 1, t ₋₂ = 0

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

Usando esta recursividad, los enteros s y t de Bézout están dados 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 puede demostrarse por inducción. Supongamos que la fórmula de recursividad es correcta hasta el paso k  − 1 del algoritmo; en otras palabras, suponga que

r _j = s _j a + t _j b

para todo j menor que k . El k ésimo paso del algoritmo da la ecuación

r _k = r _{k −2} − q _k r _{k −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} una + t _{k −2} segundo ) − q _k ( s _{k −1} una + t _{k −1} segundo ).

Reorganizar esta ecuación produce la fórmula de recursividad para el paso k , según sea necesario

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

método matricial

Los números enteros s y t también se pueden encontrar usando un método matricial 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 de cocientes de 2 × 2 que multiplican un vector de 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 de cocientes, cada una de las cuales es negativa. Como el determinante de M nunca es cero, el vector de los restos finales se puede resolver usando 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

gramo = (−1) ^{norte +1} ( metro ₂₂ una − metro ₁₂ segundo ),

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 recursividad equivalente, con dos multiplicaciones y dos sumas por paso del algoritmo euclidiano.

El lema de Euclides y la factorización única.

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 se puede escribir como 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 v por el siguiente argumento: Si el máximo común divisor de u y w es 1, entonces se pueden encontrar enteros s y t tales que

1 = su + tw

por la identidad de Bézout. Multiplicar ambos lados por v da la relación:

v = todoterreno + twv = sL + twv

Dado que w divide ambos términos del lado derecho, también debe dividir el lado izquierdo, v . Este resultado se conoce como 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 de cada uno de una serie de números a ₁ , a ₂ , ..., _an , entonces w también es coprimo de 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 ₂ … p _m = q ₁ q ₂ … q _norte  .

Dado que cada primo p divide a L por supuesto, también debe dividir uno de los q factores; dado que cada q también es primo, debe ser que p  =  q . Dividir iterativamente por los p factores 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 primos tiene muchas aplicaciones en demostraciones matemáticas, como se muestra a continuación.

Ecuaciones lineales diofánticas

Gráfico de una ecuación diofántica lineal , 9 x  + 12 y  = 483. Las soluciones se muestran como círculos azules.

Las ecuaciones diofánticas son ecuaciones en las que las soluciones están restringidas a números enteros; Llevan el 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. Esto se puede escribir como una ecuación para x en aritmética modular :

hacha ≡ 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 tendrá 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 ₁  =  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 este último, considere dos soluciones, ( x ₁ ,  y ₁ ) y ( x ₂ ,  y ₂ ), donde

hacha ₁ + por ₁ = c = hacha ₂ + por ₂

o equivalente

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

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

x = x ₁ − bu / g

y = y ₁ + au / g .

Al permitir que u varíe en 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), sólo será posible un número finito de soluciones. Esta restricción de 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 indeterminado ).

Inversos multiplicativos y el algoritmo RSA

Un campo finito es un conjunto de números con cuatro operaciones generalizadas. Las operaciones se llaman suma, resta, multiplicación y división y tienen sus propiedades habituales, como conmutatividad , asociatividad y distributividad . Un ejemplo de cuerpo finito es el conjunto de 13 números {0, 1, 2,..., 12} usando aritmética modular . En este campo, 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 esté dentro del rango 0-12. Por ejemplo, el resultado de 5 × 7 = 35 mod 13 = 9. Estos campos finitos se pueden definir para cualquier primo p ; utilizando definiciones más sofisticadas, también se pueden definir para cualquier potencia m de un primo p ^m . Los campos finitos a menudo se denominan campos de Galois y se abrevian como GF( ^p ) o GF( pm ).  

En un campo con m números, cada elemento a distinto de cero tiene un inverso multiplicativo modular único , a ⁻¹ tal que aa ⁻¹  =  a ⁻¹ a  ≡ 1 mod  m . Esta inversa 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 describe 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 número entero utilizado para descifrar el mensaje. ^[73] Aunque el algoritmo RSA utiliza anillos en lugar de campos, el algoritmo euclidiano aún se puede utilizar para encontrar un inverso multiplicativo donde exista. El algoritmo euclidiano también tiene otras aplicaciones en códigos de corrección de errores ; por ejemplo, se puede utilizar como alternativa al algoritmo Berlekamp-Massey para decodificar códigos BCH y Reed-Solomon , que se basan en campos de Galois. ^[74]

Teorema del resto chino

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 método novedoso 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 restos x _i . La solución es combinar las múltiples ecuaciones en una sola ecuación diofántica lineal con un módulo M mucho mayor que sea el producto de todos los módulos individuales m _i , y definir Mi _como

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

Por 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 número entero x puede reconstruirse a partir de sus restos 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 usando el algoritmo de Euclides como se describe en la subsección anterior.

Árbol de popa-brocot

El algoritmo euclidiano se puede utilizar para ordenar el conjunto de todos los números racionales positivos en un árbol de búsqueda binario 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 ) usando la forma original del algoritmo euclidiano. , en el 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 euclidiano que reemplaza el primero de los dos números corresponde a un paso en el árbol desde un nodo hasta 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ás bajos y forma una ruta desde la raíz hasta 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 en la raíz, yendo hacia la izquierda una vez y luego hacia la derecha dos veces:

El árbol de Stern-Brocot y las secuencias de Stern-Brocot de orden i para i = 1, 2, 3, 4

${\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 la ruta se invierte: en lugar de producir una ruta desde la raíz del árbol hasta un objetivo, produce una ruta desde el objetivo hasta la raíz.

fracciones continuas

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 a la inversa del lado izquierdo de la siguiente ecuación. Por lo tanto, las dos primeras ecuaciones se pueden combinar 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 ₀ , dando como resultado

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

La relación final de restos r _k / r _{k −1} siempre se puede reemplazar usando 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 anterior, se calculó el mcd(1071, 462) y los cocientes q _k fueron 2, 3 y 7, respectivamente. Por tanto, la fracción 1071/462 podrá escribirse

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

como se puede confirmar mediante cálculo.

Algoritmos de factorización

Calcular el máximo común divisor es un paso esencial en varios algoritmos de factorización de 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 se puede utilizar para encontrar este MCD de manera eficiente. La factorización de fracciones continuas utiliza fracciones continuas, que se determinan mediante el algoritmo de Euclides. ^[84]

Eficiencia algorítmica

Número de pasos en el algoritmo euclidiano para mcd( x , y ). Los puntos más claros (rojo y amarillo) indican relativamente pocos pasos, mientras que los puntos más oscuros (violeta y azul) indican más pasos. El área oscura más grande sigue la línea y = Φx , donde Φ es la proporción áurea .

La eficiencia computacional del algoritmo de Euclides se ha estudiado en profundidad. ^[85] Esta eficiencia se puede describir 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á limitado 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 tanto, el algoritmo de Euclides se ejecuta en un polinomio de tiempo del tamaño de la entrada. ^[88] Émile Léger , en 1837, estudió el peor caso, que es cuando las entradas son números de Fibonacci consecutivos . ^[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 requiere 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 único cálculo del 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 ² ). Se pueden utilizar técnicas algorítmicas modernas basadas en el algoritmo de Schönhage-Strassen para la multiplicación rápida de números enteros para acelerar esto, lo que lleva a algoritmos cuasilineales para el MCD. ^{[93] [94]}

Numero de pasos

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 my n . Entonces

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

como puede verse dividiendo todos los pasos del algoritmo euclidiano por g . ^[96] Por el mismo argumento, el número de pasos sigue siendo el mismo 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 dramáticamente 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 supuesto. ^[95]

Peor de los casos

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 cuales esto es cierto son los _números de Fibonacci _FN +2 _y FN +1 _, respectivamente. ^[97] Más precisamente, si el algoritmo euclidiano requiere N pasos para el par a  >  b , entonces se tiene a  ≥  F _{N +2} y b  ≥  F _{N +1} . Esto se puede demostrar por inducción . ^[98] Si N  = 1, b divide a sin resto; los números naturales más pequeños para los cuales esto es cierto son b  = 1 y a  = 2, que son F ₂ y F ₃ , respectivamente. Ahora supongamos que el resultado es válido 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} yr 0 _≥ F _M . Por lo tanto, a  =  q ₀ b  +  r ₀  ≥  b  +  r ₀  ≥  F _{M +1}  +  F _M  =  F _{M +2} , que es la desigualdad deseada. Esta prueba, 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 mostrar que el número de pasos en el algoritmo de Euclides nunca puede ser más de 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 a F _{N +1} que a su vez es mayor o igual a φ ^{N −1} , donde φ es la proporción áurea . Dado que b  ≥  φ ^{N −1} , entonces N  − 1 ≤ log _φ b . Dado que log ₁₀ φ  > 1/5, ( N  − 1)/5 < log ₁₀ φ  log _φ b  = log ₁₀ b . Por 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 del número menor b .

Promedio

El número medio de pasos dados por el algoritmo euclidiano se ha definido de tres formas diferentes. La primera definición es el tiempo promedio T ( a ) requerido para calcular el MCD de un número dado a y un número natural más pequeño 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 promediada T ( a ) también es "ruidosa". ^[101]

Para reducir este ruido, se toma un segundo promedio τ ( a ) de 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 ) enteros coprimos menores que a , donde φ es la función totiente de Euler . Este promedio tau crece suavemente con un ^{[102] [103]}

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

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

${\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\left(\ln a-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}\right)}$

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

Un tercer promedio Y ( n ) se define como el número medio de pasos requeridos cuando a y 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).}$

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

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

Gasto computacional por paso

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

r _{k −2} = q _k r _{k −1} + r _k .

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.

r _k = r _{k −2} − q _k r _{k −1} .

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

A modo de comparación, el algoritmo original basado en restas de Euclides puede ser mucho más lento. Una sola división de un número entero equivale al cociente q número de restas. Si la razón entre a y b es muy grande, el cociente es grande y serán necesarias muchas restas. Por otro lado, se ha demostrado que es muy probable que los cocientes sean números enteros pequeños. La probabilidad de un cociente q dado es aproximadamente ln | tu /( tu − 1)| donde tu = ( 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]

La combinación del número estimado de pasos con el gasto computacional estimado por paso 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 restos 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}).}$

Metodos alternativos

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 alternativas al algoritmo de Euclides.

Un método ineficiente para encontrar 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 encontrar dividiendo ambos números por enteros sucesivos desde 2 hasta el número menor b . El número de pasos de este enfoque crece linealmente con b , o exponencialmente en el número de dígitos. Otro método ineficiente es encontrar 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 para la factorización prima también son ineficientes; Muchos sistemas de criptografía modernos incluso se basan en esa ineficiencia. ^[11]

El algoritmo binario GCD es una alternativa eficiente que sustituye la división por operaciones más rápidas aprovechando 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 una 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 GCD de Lehmer utiliza el mismo principio general que el algoritmo binario para acelerar los cálculos GCD 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 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 indicado anteriormente. Estos métodos cuasilineales generalmente escalan como O ( h log h ² log log h ). ^{[93] [94]}

Generalizaciones

Aunque el algoritmo euclidiano se utiliza para encontrar el máximo común divisor de dos números naturales (enteros positivos), se puede generalizar a los números reales y a otros objetos matemáticos, como polinomios , ^[128] enteros cuadráticos ^[129] y Hurwitz . cuaterniones . ^[130] En los últimos casos, el algoritmo euclidiano se utiliza para demostrar la propiedad crucial de la factorización única, es decir, que tales números pueden factorizarse de manera ú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.

Números racionales y reales

El algoritmo de Euclides se puede aplicar a números reales , tal 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 equivale a encontrar una relación entera entre los números reales a y b ; es decir, determina números enteros s y t tales que sa + tb = 0 . Si tal ecuación es posible, a y b se llaman longitudes conmensurables; de lo contrario, son longitudes inconmensurables . ^{[131] [132]}

El algoritmo euclidiano de números reales difiere de su homólogo entero en dos aspectos. Primero, los restos 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 es así, la fracción a / b es un número racional, es decir, la razón 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 _norte ] . Si el algoritmo no se detiene, la fracción a / b es un número irracional y puede describirse mediante una fracción continua infinita [ q ₀ ; q1 _, q2 _, … ] . ^[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 razones a / b de dos números reales son irracionales. ^[135]

Una fracción continua infinita se puede truncar en un paso k [ q ₀ ; q ₁ , q ₂ , ..., q _k ] para producir una aproximación a a / b que mejora a medida que k aumenta. 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 recursividad. El convergente m _k / n _k es la mejor aproximación numérica 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}}}.}$

Polinomios

Los polinomios en una sola variable x se pueden sumar, multiplicar y factorizar en polinomios irreducibles , que son análogos de los números primos de 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 mediante 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 manera que cada resto sea cero o tenga un grado menor que el grado de su predecesor: grados[ r _k ( x )] < grados [ r _{k −1} ( x )] . Dado que el grado es un número entero no negativo y disminuye con cada paso, el algoritmo euclidiano concluye en un número finito de pasos. El último resto 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 ) produce un resto r ₀ ( x ) = x ³ + (2/3) x ² + (5/3) x − (2/3) . En el siguiente paso, b ( x ) se divide por r ₀ ( x ) dando un resto r ₁ ( x ) = x ² + x + 2 . Finalmente, dividir r ₀ ( x ) por r ₁ ( x ) produce un resto cero, lo que indica que r ₁ ( x ) es el polinomio máximo común divisor de a ( x ) y b ( x ) , consistente con su factorización.

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

El algoritmo polinomial euclidiano 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 determinado . ^[139] Esto a su vez tiene aplicaciones en varias áreas, como el criterio de estabilidad de Routh-Hurwitz en la teoría del control . ^[140]

Finalmente, los coeficientes de los polinomios no necesitan extraerse de números enteros, reales o incluso de 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]

Enteros gaussianos

Distribución de los primos gaussianos u + vi en el plano complejo, con normas u ² + v ² menores que 500

Los enteros gaussianos son números complejos de la forma α = u + vi , donde u y v son 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 enteros gaussianos son factorizables de forma única, mediante el argumento anterior. ^[42] Esta factorización única es útil en muchas aplicaciones, como derivar todos los triples pitagóricos o demostrar el teorema de Fermat en sumas de dos cuadrados . ^[141] En general, el algoritmo euclidiano es conveniente en este tipo de aplicaciones, pero no esencial; por ejemplo, los teoremas a menudo pueden demostrarse mediante otros argumentos.

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

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

donde cada resto es estrictamente menor que su predecesor: | rk | _{_} < | rk ₋₁ | _{_} . La primera diferencia es que los cocientes y los restos son en sí mismos números enteros gaussianos y, por tanto, son números complejos . Los cocientes q _k generalmente se encuentran redondeando las partes reales y complejas de la razón exacta (como el número complejo α / β ) a los 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 anterior, f ( r _{k −1} ) . Dado que la norma es un número 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 que se multiplica por una unidad, ±1 o ± i . ^[144]

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

Dominios euclidianos

Un conjunto de elementos bajo dos operaciones binarias , denotadas como suma y multiplicación, se denomina 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 tal anillo no necesitan ser la suma 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 rigen la aritmética ordinaria, como la conmutatividad , la asociatividad y la distributividad .

El algoritmo euclidiano generalizado requiere una función euclidiana , es decir, una asignación de f de R al conjunto de enteros no negativos tal que, para dos elementos cualesquiera distintos de cero a y b en R , existen q y r en R tales que a = qb + r y f ( r ) < f ( segundo ) . ^[148] Ejemplos de tales asignaciones 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 tanto, si f sólo puede reducirse 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 todo 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 único (UFD), aunque lo contrario 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 utilizando un algoritmo euclidiano. Un dominio euclidiano es siempre un dominio ideal principal (PID), un dominio integral en el que todo ideal es un ideal principal . ^[153] Una vez más, lo contrario no es cierto: no todos los PID son un dominio euclidiano.

La factorización única de dominios euclidianos es útil en muchas aplicaciones. Por ejemplo, la factorización única de los enteros gaussianos es conveniente para derivar fórmulas para todos los triples pitagóricos y para demostrar el teorema de Fermat en 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, basándose 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 ené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]

Factorización única de números enteros cuadráticos

Distribución de primos de Eisenstein u + vω en el plano complejo, con normas menores que 500. El número ω es raíz cúbica de 1 .

Los anillos de enteros cuadráticos son útiles para ilustrar los dominios euclidianos. Los enteros cuadráticos son generalizaciones de los 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 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 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 aún no se conoce la lista de posibles valores de D cuyo dominio es euclidiano. ^[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 sólo si, es un dominio ideal principal , siempre que se cumpla la hipótesis generalizada de Riemann . ^[129]

Anillos no conmutativos

El algoritmo euclidiano puede aplicarse a algunos anillos no conmutativos como el conjunto de cuaterniones de Hurwitz . ^{[ se necesita aclaración ] [130]} 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, existen dos versiones del algoritmo euclidiano, una para divisores derechos y otra para divisores izquierdos. ^[130] Al elegir los divisores correctos, 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. ^{[ se necesita aclaración ]} Esta ecuación muestra que cualquier divisor derecho común de α y β es también un divisor común del resto ρ ₀ . La ecuación análoga para los divisores de la izquierda sería

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

Con cualquiera de las opciones, el proceso se repite como arriba 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 norma ) debe ser estrictamente menor que β , y debe haber sólo un número finito de tamaños posibles para ρ ₀ , de modo que se garantice que el algoritmo Terminar. ^[159]

La mayoría de los resultados del MCD se trasladan a números no conmutativos. ^{[ se necesita aclaración ]} Por ejemplo, la identidad de Bézout establece que el mcd derecho( α , β ) se puede expresar como una combinación lineal de α y β . ^[160] 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 demostraciones estándar del teorema de los cuatro cuadrados de Lagrange , de que cada entero positivo se puede representar como una suma de cuatro cuadrados, se basa de esta manera en los MCD de cuaterniones. ^[159]

Ver también

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

Notas

1. Algunos libros de texto ampliamente utilizados, como Topics in Algebra de IN Herstein y Álgebra de Serge Lang , utilizan el término "algoritmo euclidiano" para referirse a la división euclidiana.
2. La frase "entero ordinario" se usa comúnmente para distinguir los enteros habituales de los enteros gaussianos y, más generalmente, de los enteros algebraicos .

Referencias

1. Lamé, Gabriel (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus des Séances de l'Académie des Sciences (en francés). 19 : 867–870.
2. Shallit, Jeffrey (1 de noviembre de 1994). "Orígenes del análisis del algoritmo euclidiano". Historia Matemática . 21 (4): 401–419. doi : 10.1006/hmat.1994.1031 . ISSN  0315-0860.
3. Rígido 1978, pag. dieciséis
4. Rígido 1978, pag. 21
5. LeVeque 1996, pág. 32
6. LeVeque 1996, pág. 31
7. Grossman, JW (1990). Matemáticas discretas . Nueva York: Macmillan. pag. 213.ISBN _ 0-02-348331-8.
8. Schroeder 2005, págs. 21-22
9. Schroeder 2005, pág. 19
10. Ogilvy, CS ; Anderson, JT (1966). Excursiones en teoría de números . Nueva York: Oxford University Press . págs. 27-29.
11. Schroeder 2005, págs. 216-219
12. LeVeque 1996, pág. 33
13. Rígido 1978, pag. 25
14. Mineral 1948, págs. 47–48
15. Rígido 1978, pag. 18
16. Rígido 1978, págs. 16-20
17. Knuth 1997, pág. 320
18. Lovász, L .; Pelikán, J.; Vesztergombi, K. (2003). Matemáticas discretas: primaria y posteriores . Nueva York: Springer-Verlag. págs. 100-101. ISBN 0-387-95584-4.
19. Kimberling, C. (1983). "Un algoritmo visual euclidiano". Profesor de matemáticas . 76 : 108-109.
20. Tonto, David S.; Foote, Richard M. (2004). Álgebra abstracta . John Wiley & Sons, Inc. págs. 270–271. ISBN 978-0-471-43334-7.
21. Knuth 1997, págs. 319–320
22. Knuth 1997, págs. 318–319
23. Stillwell 1997, pág. 14
24. Ore 1948, pág. 43
25. Stewart, BM (1964). Teoría de los números (2ª ed.). Nueva York: Macmillan. págs. 43–44. LCCN  64010964.
26. Lazard, D. (1977). "El mejor algoritmo de Euclides para K [ X ] y Z ". Comptes Rendus de l'Académie des Sciences (en francés). 284 : 1–4.
27. Knuth 1997, pág. 318
28. Weil, A. (1983). Teoría de los números . Boston: Birkhäuser. págs. 4–6. ISBN 0-8176-3141-0.
29. Jones, A. (1994). "Matemáticas griegas hasta el año 300 d. C.". Enciclopedia complementaria de la historia y la filosofía de las ciencias matemáticas . Nueva York: Routledge. págs. 46–48. ISBN 0-415-09238-8.
30. van der Waerden, BL (1954). Despertar de la ciencia . traducido por Arnold Dresden. Groninga: P. Noordhoff Ltd. págs.
31. von Fritz, K. (1945). "El descubrimiento de la inconmensurabilidad por Hipasus de Metapontum". Anales de Matemáticas . 46 (2): 242–264. doi :10.2307/1969021. JSTOR  1969021.
32. Salud, TL (1949). Matemáticas en Aristóteles . Prensa de Oxford. págs. 80–83.
33. Fowler, DH (1987). Las matemáticas de la Academia de Platón: una nueva reconstrucción . Oxford: Prensa de la Universidad de Oxford. págs. 31–66. ISBN 0-19-853912-6.
34. Becker, O. (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B. 2 : 311–333.
35. Stillwell 1997, pág. 31
36. Tattersall 2005, pág. 70
37. Rosen 2000, págs. 86–87
38. Mineral 1948, págs. 247-248
39. Tattersall 2005, págs. 72, 184-185
40. Saunderson, Nicolás (1740). Los elementos del álgebra en diez libros. Prensa de la Universidad de Cambridge . Consultado el 1 de noviembre de 2016 .
41. Tattersall 2005, págs. 72–76
42. Gauss, CF (1832). "Theoria residuorum biquadraticorum". Com. Soc. Reg. Ciencia. Gött. Rec . 4 .Reimpreso en Gauss, CF (2011). "Theoria residuorum biquadraticorum commentatio prima". Trabajo . vol. 2. Universidad de Cambridge. Prensa. págs. 65–92. doi :10.1017/CBO9781139058230.004. ISBN 9781139058230.y Gauss, CF (2011). "Theoria residuorum biquadraticorum commentatio secunda". Trabajo . vol. 2. Universidad de Cambridge. Prensa. págs. 93-148. doi :10.1017/CBO9781139058230.005. ISBN 9781139058230.
43. Stillwell 1997, págs. 31-32
44. Lejeune Dirichlet 1894, págs. 29-31
45. Richard Dedekind en Lejeune Dirichlet 1894, Suplemento XI
46. Stillwell 2003, págs. 41–42
47. Sturm, C. (1829). "Mémoire sur la résolution des équations numériques". Toro. Des sciences de Férussac (en francés). 11 : 419–422.
48. Ferguson, HRP ; Forcade, RW (1979). "Generalización del algoritmo euclidiano para números reales a todas las dimensiones superiores a dos". Boletín de la Sociedad Matemática Estadounidense . Series nuevas. 1 (6): 912–914. doi : 10.1090/S0273-0979-1979-14691-3 . SEÑOR  0546316.
49. Peterson, I. (12 de agosto de 2002). "Mejorando el algoritmo de Euclides". Noticias de ciencia .
50. Cipra, Barry Arthur (16 de mayo de 2000). "Lo mejor del siglo XX: los editores nombran los 10 algoritmos principales" (PDF) . Noticias SIAM . Sociedad de Matemática Industrial y Aplicada . 33 (4). Archivado desde el original (PDF) el 22 de septiembre de 2016 . Consultado el 19 de julio de 2016 .
51. Cole, AJ; Davie, AJT (1969). "Un juego basado en el algoritmo euclidiano y una estrategia ganadora". Matemáticas. Gaz . 53 (386): 354–357. doi :10.2307/3612461. JSTOR  3612461. S2CID  125164797.
52. Spitznagel, EL (1973). "Propiedades de un juego basado en el algoritmo de Euclides". Matemáticas. Mag . 46 (2): 87–92. doi :10.2307/2689037. JSTOR  2689037.
53. Rosen 2000, pag. 95
54. Roberts, J. (1977). Teoría de números elemental: un enfoque orientado a problemas. Cambridge, MA: MIT Press . págs. 1–8. ISBN 0-262-68028-9.
55. Jones, Georgia; Jones, JM (1998). "La identidad de Bezout". Teoría elemental de números . Nueva York: Springer-Verlag. págs. 7-11.
56. Rosen 2000, pag. 81
57. Cohn 1962, pag. 104
58. Rosen 2000, pag. 91
59. Schroeder 2005, pág. 23
60. Rosen 2000, págs. 90–93
61. Koshy, T. (2002). Teoría de números elemental con aplicaciones . Burlington, MA: Harcourt/Academic Press. págs. 167-169. ISBN 0-12-421171-2.
62. Bach, E .; Shalit, J. (1996). Teoría algorítmica de números . Cambridge, MA: MIT Press. págs. 70–73. ISBN 0-262-02405-5.
63. Rígido 1978, págs. 26-36
64. Ore 1948, pág. 44
65. Rígido 1978, págs. 281-292
66. Rosen 2000, págs. 119-125
67. Schroeder 2005, págs. 106-107
68. Schroeder 2005, págs. 108-109
69. Rosen 2000, págs. 120-121
70. Rígido 1978, pag. 47
71. Schroeder 2005, págs. 107-109
72. Stillwell 1997, págs. 186-187
73. Schroeder 2005, pág. 134
74. Luna, TK (2005). Codificación de corrección de errores: métodos y algoritmos matemáticos . John Wiley e hijos. pag. 266.ISBN _ 0-471-64800-0.
75. Rosen 2000, págs. 143-170
76. Schroeder 2005, págs. 194-195
77. Graham, R .; Knuth, DE ; Patashnik, O. (1989). Matemáticas concretas . Addison-Wesley. pag. 123.
78. Vinogradov, IM (1954). Elementos de la teoría de números . Nueva York: Dover. págs. 3-13.
79. Crandall y Pomerance 2001, págs. 225–349
80. Knuth 1997, págs. 369–371
81. Corto, PW (1997). "Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación Científica y Estadística . 26 (5): 1484-1509. arXiv : quant-ph/9508027 . Código bibliográfico : 1995quant.ph..8027S. doi :10.1137/s0097539795293172. S2CID  2337707.
82. Dixon, JD (1981). "Factorización asintóticamente rápida de números enteros". Matemáticas. Computación . 36 (153): 255–260. doi : 10.2307/2007743 . JSTOR  2007743.
83. Lenstra, HW Jr. (1987). "Factorizar números enteros con curvas elípticas". Anales de Matemáticas . 126 (3): 649–673. doi :10.2307/1971363. hdl : 1887/2140 . JSTOR  1971363.
84. Knuth 1997, págs. 380–384
85. Knuth 1997, págs. 339–364
86. Reynaud, A.-A.-L. (1811). Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique (6ª ed.). París: Courcier. Nota 60, pág. 34.Como lo cita Shallit (1994).
87. Finck, P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales (en francés). Derivaux.
88. Shallit 1994.
89. Lamé, G. (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus de l'Académie des Sciences (en francés). 19 : 867–870.
90. Grossman, H. (1924). "Sobre el número de divisiones para encontrar un MCD". El Mensual Matemático Estadounidense . 31 (9): 443. doi : 10.2307/2298146. JSTOR  2298146.
91. Honsberger, R. (1976). Gemas Matemáticas II . La Asociación Matemática de América . págs. 54–57. ISBN 0-88385-302-7.
92. Knuth 1997, págs. 257-261
93. Crandall y Pomerance 2001, págs. 77–79, 81–85, 425–431
94. Möller, N. (2008). "Sobre el algoritmo de Schönhage y el cálculo del mcd de enteros subcuadráticos" (PDF) . Matemáticas de la Computación . 77 (261): 589–607. Código Bib : 2008MaCom..77..589M. doi : 10.1090/S0025-5718-07-02017-0 .
95. Knuth 1997, pag. 344
96. Mineral 1948, pag. 45
97. Knuth 1997, pág. 343
98. Mollin 2008, pag. 21
99. LeVeque 1996, pág. 35
100. Mollin 2008, págs. 21-22
101. Knuth 1997, pág. 353
102. Knuth 1997, pág. 357
103. Tonkov, T. (1974). "Sobre la longitud media de fracciones continuas finitas". Acta Aritmética . 26 : 47–57. doi : 10.4064/aa-26-1-47-57 .
104. Knuth, Donald E. (1976). "Evaluación de la constante de Porter". Computadoras y Matemáticas con Aplicaciones . 2 (2): 137–139. doi : 10.1016/0898-1221(76)90025-0 .
105. Portero, JW (1975). "Sobre un teorema de Heilbronn". Matemática . 22 : 20–28. doi :10.1112/S0025579300004459.
106. Knuth, DE (1976). "Evaluación de la constante de Porter". Computadoras y Matemáticas con Aplicaciones . 2 (2): 137–139. doi : 10.1016/0898-1221(76)90025-0 .
107. Dixon, JD (1970). "El número de pasos del algoritmo euclidiano". J. Teoría de números . 2 (4): 414–422. Código Bib : 1970JNT....2..414D. doi : 10.1016/0022-314X(70)90044-2 .
108. Heilbronn, HA (1969). "Sobre la longitud media de una clase de fracciones continuas finitas". En Pablo Turán (ed.). Teoría y análisis de números . Nueva York: Pleno. págs. 87–96. LCCN  76016027.
109. Knuth 1997, pág. 354
110. Norton, GH (1990). "Sobre el análisis asintótico del algoritmo euclidiano". Revista de Computación Simbólica . 10 : 53–58. doi : 10.1016/S0747-7171(08)80036-3 .
111. Knuth 1997, pág. 355
112. Knuth 1997, pág. 356
113. Knuth 1997, pág. 352
114. Vagón, S. (1999). Matemáticas en acción . Nueva York: Springer-Verlag. págs. 335–336. ISBN 0-387-98252-3.
115. Cohen 1993, pag. 14
116. Cohen 1993, págs. 14-15, 17-18
117. Sorenson, Jonathan P. (2004). "Un análisis del algoritmo GCD binario generalizado". Altos primos y delitos menores: conferencias en honor al 60 cumpleaños de Hugh Cowie Williams. Comunicaciones del Instituto Fields. vol. 41. Providence, RI: Sociedad Matemática Estadounidense. págs. 327–340. ISBN 9780821887592. MR  2076257. Los algoritmos que más se utilizan en la práctica hoy en día [para calcular los máximos divisores comunes] son ​​probablemente el algoritmo binario y el algoritmo de Euclides para números más pequeños, y el algoritmo de Lehmer o la versión de Lebealean del algoritmo MCD k -ario para números más grandes.
118. Knuth 1997, págs. 321–323
119. Stein, J. (1967). "Problemas computacionales asociados al álgebra de Racah". Revista de Física Computacional . 1 (3): 397–405. Código bibliográfico : 1967JCoPh...1..397S. doi :10.1016/0021-9991(67)90047-2.
120. Knuth 1997, pág. 328
121. Lehmer, DH (1938). "Algoritmo de Euclides para números grandes". El Mensual Matemático Estadounidense . 45 (4): 227–233. doi :10.2307/2302607. JSTOR  2302607.
122. Sorenson, J. (1994). "Dos algoritmos GCD rápidos". J. Algoritmos . 16 : 110-144. doi :10.1006/jagm.1994.1006.
123. Weber, K. (1995). "El algoritmo GCD acelerado". Transmisión ACM. Matemáticas. Software . 21 : 111-122. doi : 10.1145/200979.201042 . S2CID  14934919.
124. Ah, A .; Hopcroft, J .; Ullman, J. (1974). El diseño y análisis de algoritmos informáticos. Nueva York: Addison-Wesley. págs. 300–310. ISBN 0-201-00029-6.
125. Schönhage, A. (1971). "Schnelle Berechnung von Kettenbruchentwicklungen". Acta Informática (en alemán). 1 (2): 139–144. doi :10.1007/BF00289520. S2CID  34561609.
126. Cesari, G. (1998). "Implementación paralela del algoritmo GCD entero de Schönhage". En G. Buhler (ed.). Teoría algorítmica de números: proc. HORMIGAS-III, Portland, Oregón . Apuntes de conferencias sobre informática. vol. 1423. Nueva York: Springer-Verlag. págs. 64–76.
127. Stehlé, D.; Zimmermann, P. (2005). " Revisión del método de tablas precisas de Gal ". Actas del 17º Simposio IEEE sobre aritmética informática (ARITH-17) . Los Alamitos, CA: IEEE Computer Society Press .
128. Lang, S. (1984). Álgebra (2ª ed.). Menlo Park, California: Addison – Wesley. págs. 190-194. ISBN 0-201-05487-6.
129. Weinberger, P. (1973). "Sobre anillos euclidianos de números enteros algebraicos". Proc. Simposios. Matemáticas puras . Actas de simposios de matemática pura. 24 : 321–332. doi :10.1090/pspum/024/0337902. ISBN 9780821814246.
130. Stillwell 2003, págs. 151-152
131. Boyer, CB; Merzbach, UC (1991). Una historia de las matemáticas (2ª ed.). Nueva York: Wiley. págs. 116-117. ISBN 0-471-54397-7.
132. Cajori, F (1894). Una historia de las matemáticas. Nueva York: Macmillan. pag. 70.ISBN _ 0-486-43874-0.
133. Joux, Antoine (2009). Criptoanálisis algorítmico. Prensa CRC. pag. 33.ISBN _ 9781420070033.
134. Fuks, DB; Tabachnikov, Serge (2007). Ómnibus matemático: treinta conferencias sobre matemáticas clásicas. Sociedad Matemática Estadounidense. pag. 13.ISBN _ 9780821843161.
135. Cariño, David (2004). "La constante de Khintchin". El libro universal de las matemáticas: de Abracadabra a las paradojas de Zenón. John Wiley e hijos. pag. 175.ISBN _ 9780471667001.
136. Williams, Colin P. (2010). Exploraciones en Computación Cuántica. Saltador. págs. 277–278. ISBN 9781846288876.
137. Cox, Little y O'Shea 1997, págs. 37–46
138. Schroeder 2005, págs. 254-259
139. Grattan-Guinness, Ivor (1990). Convoluciones en las matemáticas francesas, 1800-1840: del cálculo y la mecánica al análisis matemático y la física matemática. Volumen II: Las Vueltas. Redes científicas: estudios históricos. vol. 3. Basilea, Boston, Berlín: Birkhäuser. pag. 1148.ISBN _ 9783764322380. Nuestro tema aquí es la 'secuencia de Sturm' de funciones definidas a partir de una función y su derivada mediante el algoritmo de Euclides, para calcular el número de raíces reales de un polinomio dentro de un intervalo dado.
140. Peluquero, Ernst; Nørsett, Syvert P.; Wanner, Gerhard (1993). "El criterio de Routh-Hurwitz". Resolución de ecuaciones diferenciales ordinarias I: problemas no rígidos. Serie Springer en Matemática Computacional. vol. 8 (2ª ed.). Saltador. págs. 81 y siguientes. ISBN 9783540566700.
141. Stillwell 2003, págs. 101-116
142. Hensley, Doug (2006). Fracciones continuas. Científico mundial. pag. 26.ISBN _ 9789812564771.
143. Dedekind, Richard (1996). Teoría de los Enteros Algebraicos. Biblioteca de Matemáticas de Cambridge. Prensa de la Universidad de Cambridge. págs. 22-24. ISBN 9780521565189.
144. Johnston, Bernard L.; Richman, Fred (1997). Números y simetría: una introducción al álgebra. Prensa CRC. pag. 44.ISBN _ 9780849303012.
145. Adams, William W.; Goldstein, Larry Joel (1976). Introducción a la teoría de números . Prentice Hall. Ejercicio 24, pág. 205.ISBN _ 9780134912820. Enuncie y demuestre un análogo del teorema del resto chino para los enteros gaussianos.
146. Rígido 1978, pag. 290
147. Cohn 1962, págs. 104-105
148. Lauritzen, Niels (2003). Álgebra abstracta concreta: de los números a las bases de Gröbner. Prensa de la Universidad de Cambridge. pag. 130.ISBN _ 9780521534109.
149. Lauritzen (2003), pág. 132
150. Lauritzen (2003), pág. 161
151. Sharpe, David (1987). Anillos y Factorización . Prensa de la Universidad de Cambridge. pag. 55.ISBN _ 9780521337182.
152. Sharpe (1987), pág. 52
153. Lauritzen (2003), pág. 131
154. Lamé, G. (1847). "Mémoire sur la résolution, en nombres complexes, de l'équation A ⁿ + B ⁿ + C ⁿ = 0". J. Matemáticas. Pures Appl. (en francés). 12 : 172–184.
155. Edwards, H. (2000). El último teorema de Fermat: una introducción genética a la teoría algebraica de números . Saltador. pag. 76.
156. Cohn 1962, págs. 104-110
157. LeVeque, WJ (2002) [1956]. Temas de teoría de números, volúmenes I y II. Nueva York: Publicaciones de Dover. págs.II:57, 81. ISBN 978-0-486-42539-9. Zbl  1009.11001.
158. Clark, DA (1994). "Un campo cuadrático que es euclidiano pero no euclidiano normativo". Manuscripta Matemática . 83 : 327–330. doi : 10.1007/BF02567617 . S2CID  895185. Zbl  0817.11047.
159. Davidoff, Giuliana ; Sarnak, Pedro; Valette, Alain (2003). "2.6 La aritmética de los cuaterniones enteros". Teoría elemental de números, teoría de grupos y gráficos de Ramanujan . Textos estudiantiles de la Sociedad Matemática de Londres. vol. 55. Prensa de la Universidad de Cambridge. págs. 59–70. ISBN 9780521531436.
160. Ribenboim, Paulo (2001). Teoría clásica de los números algebraicos. Texto universitario. Springer-Verlag. pag. 104.ISBN _ 9780387950709.

Bibliografía

• Cohen, H. (1993). Un curso de teoría de números algebraica computacional. Nueva York: Springer-Verlag. ISBN 0-387-55640-0.
• Cohn, H. (1962). Teoría de números avanzada. Nueva York: Dover. ISBN 0-486-64023-X.
• Cox, D .; Pequeño, J.; O'Shea, D. (1997). Ideales, variedades y algoritmos: una introducción a la geometría algebraica computacional y al álgebra conmutativa (2ª ed.). Springer-Verlag. ISBN 0-387-94680-2.
• Crandall, R .; Pomerancia, C. (2001). Números primos: una perspectiva computacional (1ª ed.). Nueva York: Springer-Verlag. ISBN 0-387-94777-9.
• Lejeune Dirichlet, PG (1894). Dedekind, Richard (ed.). Vorlesungen über Zahlentheorie (Conferencias sobre teoría de números) (en alemán). Braunschweig: Vieweg. LCCN  03005859. OCLC  490186017.. Véase también Vorlesungen über Zahlentheorie
• Knuth, DE (1997). El arte de la programación informática , volumen 2: algoritmos seminuméricos (3ª ed.). Addison-Wesley. ISBN 0-201-89684-2.
• LeVeque, WJ (1996) [1977]. Fundamentos de la teoría de números . Nueva York: Dover. ISBN 0-486-68906-9.
• Mollin, RA (2008). Teoría fundamental de números con aplicaciones (2ª ed.). Boca Ratón: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3.
• Mineral, O. (1948). Teoría de números y su historia . Nueva York: McGraw-Hill.
• Rosen, KH (2000). Teoría de números elemental y sus aplicaciones (4ª ed.). Lectura, MA: Addison-Wesley. ISBN 0-201-87073-8.
• Schroeder, M. (2005). Teoría de números en la ciencia y la comunicación (4ª ed.). Springer-Verlag. ISBN 0-387-15800-6.
• Stark, H. (1978). Una introducción a la teoría de números. Prensa del MIT. ISBN 0-262-69060-8.
• Stillwell, J. (1997). Números y Geometría . Nueva York: Springer-Verlag. ISBN 0-387-98289-2.
• Stillwell, J. (2003). Elementos de la teoría de números . Nueva York: Springer-Verlag. ISBN 0-387-95587-9.
• Tattersall, JJ (2005). Teoría elemental de números en nueve capítulos . Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-85014-8.

enlaces externos

• Demostraciones del algoritmo de Euclides
• Weisstein, Eric W. "Algoritmo euclidiano". MundoMatemático .
• Algoritmo de Euclides para cortar el nudo
• Algoritmo de Euclides en PlanetMath .
• El algoritmo euclidiano en MathPages
• El juego de Euclides al cortar el nudo
• La música y el algoritmo de Euclides.