Algoritmo euclidiano - Euclidean algorithm

El 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 de "unidad" común. Siendo la longitud DC más corta, se usa para "medir" BA, pero solo una vez porque el resto EA es menor que DC. EA ahora mide (dos veces) la longitud más corta DC, con el resto FC más corto que EA. Entonces FC mide (tres veces) la longitud EA. Como no hay resto, el proceso termina con FC como GCD. A la derecha , el ejemplo de Nicomachus con los números 49 y 21 resultando en su MCD de 7 (derivado de Heath 1908: 300).

En matemáticas , el algoritmo de Euclides , o algoritmo de Euclides , es un método eficiente para calcular el máximo común divisor (MCD) de dos enteros (números), el número más grande que los divide a ambos sin un 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 un algoritmo , un procedimiento paso a paso para realizar un cálculo de acuerdo con reglas bien definidas, y es uno de los algoritmos más antiguos de uso común. Puede usarse para reducir fracciones a su forma más simple y es parte de muchos otros cálculos criptográficos y teóricos de números.

El algoritmo euclidiano se basa en el principio de que el máximo común divisor de dos números no cambia si el número más grande se reemplaza por su diferencia con el número más pequeño. Por ejemplo, 21 es el MCD de 252 y 105 (como 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, repetir este proceso da sucesivamente pares de números 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. Al invertir los pasos o al utilizar 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 la GCD siempre pueda expresarse de esta manera se conoce como identidad de Bézout .

La versión del algoritmo euclidiano descrita anteriormente (y por Euclid) puede tomar muchos pasos de resta para encontrar el MCD cuando uno de los números dados es mucho más grande que el otro. Una versión más eficiente del algoritmo ataja estos pasos, en lugar de reemplazar 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 número entero más pequeño. Esto fue probado por Gabriel Lamé en 1844 y marca el comienzo de la teoría de la complejidad computacional . En el siglo XX se desarrollaron métodos adicionales para mejorar la eficiencia del algoritmo.

El algoritmo 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 asegurar las comunicaciones de Internet y en los métodos para romper estos criptosistemas al factorizar números compuestos grandes . El algoritmo euclidiano se puede utilizar para resolver ecuaciones diofánticas , como encontrar números que satisfagan múltiples congruencias de acuerdo con el teorema chino del resto , construir fracciones continuas y encontrar aproximaciones racionales precisas a números reales. Finalmente, se puede utilizar como una herramienta básica para demostrar teoremas en teoría de números , como el teorema de los cuatro cuadrados de Lagrange y la unicidad de las factorizaciones primas . El algoritmo original se describió solo 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 enteros gaussianos y polinomios de una variable. Esto condujo a nociones algebraicas abstractas modernas como los dominios euclidianos .

Trasfondo: máximo común divisor

El algoritmo de Euclides calcula el máximo común divisor (MCD) de dos números naturales a y b . El máximo común divisor g es el mayor número natural que divide tanto una y b sin dejar un residuo. Sinónimos de la GCD son el mayor factor común divisor (MCD), el factor común más alto (HCF), el divisor común más alta (HCD), y la mayor medida común (GCM). El máximo común divisor a menudo se escribe como mcd ( ab ) o, más simplemente, como ( ab ), aunque la última notación es ambigua, también se usa para conceptos como un ideal en el anillo de números enteros , que es muy cercano relacionados con GCD.

Si gcd ( ab ) = 1, entonces una y b se dice que son primos entre sí (o relativamente primo). Esta propiedad no implica que una o b son ellos mismos números primos . Por ejemplo, ni 6 ni 35 son números primos, ya que ambos tienen dos factores primos: 6 = 2 × 3 y 35 = 5 × 7. Sin embargo, 6 y 35 son coprimos. Ningún número natural que no sea 1 divide tanto a 6 como a 35, ya que no tienen factores primos en común.

"Rectángulo alto y delgado dividido en una cuadrícula de cuadrados. El rectángulo tiene dos cuadrados de ancho y cinco cuadrados de alto".
Un rectángulo de 24 por 60 se cubre con diez de 12 por 12 azulejos cuadrados, donde 12 es el MCD de 24 y 60. Más en general, un una -by- b rectángulo se puede cubrir con baldosas cuadradas de lado de longitud c sólo si c es un divisor común de una y b .

Sea g = mcd ( ab ). Dado que a y b son múltiplos de g , se pueden escribir a  =  mg y b  =  ng , y no hay un número mayor G  >  g para el que esto sea cierto. Los números naturales m y n deben ser primos entre sí, ya que cualquier factor común podría ser un factor de m y n para hacer g mayor. Por lo tanto, cualquier otro número c que divida a y b también debe dividir g . El máximo común divisor g de un y b es el único común divisor (positivo) de un y b que es divisible por cualquier otro divisor común c .

El GCD se puede visualizar de la siguiente manera. Considere un área rectangular de una por b , y cualquier divisor común c que divide tanto una y b exactamente. Los lados del rectángulo se pueden dividir en segmentos de longitud c , que divide el rectángulo en una cuadrícula de cuadrados de longitud lateral c . El máximo común divisor g es el mayor valor de c para el que esto es posible. Por ejemplo, un área rectangular de 24 por 60 se puede dividir en una cuadrícula de: cuadrados de 1 por 1, cuadrados de 2 por 2, cuadrados de 3 por 3, cuadrados de 4 por 4, cuadrados de 6 por -6 cuadrados o cuadrados de 12 por 12. Por lo tanto, 12 es el máximo común divisor de 24 y 60. Un área rectangular de 24 por 60 se puede dividir en una cuadrícula de 12 por 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 MCD de dos números a y b es el producto de los factores primos compartidos por los dos números, donde un mismo factor primo se puede utilizar varias veces, pero sólo el tiempo que el producto de estos factores se divide tanto una y b . 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 máximo común divisor de 1386 y 3213 es igual a 63 = 3 × 3 × 7, el producto de sus factores primos compartidos. Si dos números no tienen factores primos en común, su máximo común divisor 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 GCD de manera eficiente sin tener que calcular los factores primos. Se cree que la factorización de números enteros grandes es un problema computacionalmente muy difícil, y la seguridad de muchos protocolos criptográficos ampliamente utilizados se basa en su inviabilidad.

Otra definición del GCD es útil en matemáticas avanzadas, particularmente en teoría de anillos . El máximo común divisor g   de dos números distintos de cero a y b es también su combinación integral positivo más pequeño lineal, 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 una 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 lenguaje matemático moderno, el ideales generada por una y b es el ideal generado por  g solo (un ideal generado por un único elemento que se llama una de ideal principal , y todos los ideales de los números enteros son ideales principales). Algunas propiedades de la GCD son de hecho más fáciles de ver con esta descripción, por ejemplo el hecho de que cualquier común divisor de un y b también divide el GCD (que 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, pero también se puede calcular tomando repetidamente los MCD de pares de números. Por ejemplo,

mcd ( abc ) = mcd ( a , mcd ( bc )) = mcd (mcd ( ab ),  c ) = mcd (mcd ( ac ),  b ).

Por tanto, el algoritmo de Euclides, que calcula el MCD de dos enteros, es suficiente para calcular el MCD de muchos enteros arbitrariamente.

Descripción

Procedimiento

El algoritmo euclidiano procede en una serie de pasos de modo que la salida de cada paso se utiliza como entrada para el siguiente. Sea k un número entero que cuenta los pasos del algoritmo, comenzando con cero. Así, el paso inicial corresponde a k  = 0, el siguiente paso corresponde a k  = 1, y así sucesivamente.

Cada paso comienza con dos residuos no negativos r k −1 y r k −2 . Dado que el algoritmo asegura que los residuos disminuyan constantemente con cada paso, r k −1 es menor que su predecesor r k −2 . El objetivo del k- ésimo paso es encontrar un cociente q k y el resto r k que satisfaga la ecuación

y que tienen 0 ≤ r k  <  r k −1 . En otras palabras, los múltiplos del número menor r k −1 se restan del número mayor r k −2 hasta que el resto r k sea ​​menor que r k −1 .

En el paso inicial ( k  = 0), los restos r -2 y r -1 igual a y b , los números para los que se solicita la GCD. En el siguiente paso ( k  = 1), los restos son iguales a b y el resto r 0 del paso inicial, y así sucesivamente. Por lo tanto, el algoritmo se puede escribir como una secuencia de ecuaciones.

Si a es menor que b , el primer paso del algoritmo intercambia los números. Por ejemplo, si a  <  b , el cociente inicial q 0 es igual a cero y el resto r 0 es a . Por lo tanto, r k es más pequeño que su predecesor r k −1 para todo k  ≥ 0.

Dado que los restos disminuyen con cada paso pero nunca pueden ser negativos, un resto r N debe ser eventualmente igual a cero, momento en el que el algoritmo se detiene. La final distinto de cero resto r N -1 es el máximo común divisor de un y b . El número N no puede ser infinito porque solo hay un número finito de enteros no negativos entre el resto inicial r 0 y cero.

Prueba de validez

La validez del algoritmo euclidiano se puede probar mediante un argumento de dos pasos. En el primer paso, se muestra que el resto final distinto de cero r N −1 divide tanto a como b . Dado que es un divisor común, debe ser menor o igual que el máximo común divisor g . En el segundo paso, se muestra que cualquier común divisor de un y b , incluyendo g , debe dividir r N -1 ; por lo tanto, g debe ser menor o igual que r N −1 . Estas dos conclusiones son inconsistentes a menos que r N −1  =  g .

Para demostrar que r N −1 divide a y b (el primer paso), r N −1 divide a su predecesor r N −2

r N −2 = q N r N −1

ya que el resto final r N es cero. r N −1 también divide a su próximo predecesor r N −3

r N −3 = q N −1 r N −2 + r N −1

porque divide ambos términos en el lado derecho de la ecuación. Iterar el mismo argumento, r N -1 divide todos los restos anteriores, que incluye un y b . Ninguno de los restos anteriores r N -2 , r N -3 , etc. dividir un 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 la segunda etapa, cualquier número natural c que divide tanto una y b (en otras palabras, cualquier común divisor de un y b ) divide los residuos r k . Por definición, una y b se puede escribir como múltiplos de c  : un  =  mc y b  =  nc , donde m y n son números naturales. Por lo tanto, c divide el resto inicial r 0 , ya que r 0  =  a  -  q 0 b  =  mc  -  q 0 nc  = ( m  -  q 0 n ) c . Un argumento análogo muestra que c también divide los residuos subsiguientes r 1 , r 2 , 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:

g = mcd ( a , b ) = mcd ( b , r 0 ) = mcd ( r 0 , r 1 ) =… = mcd ( r N −2 , r N −1 ) = r N −1 .

Ejemplo resuelto

Animación en la que se agregan mosaicos cuadrados progresivamente más pequeños para cubrir un rectángulo por completo.
Animación basada en restas del algoritmo euclidiano. El rectángulo inicial tiene dimensiones a  = 1071 yb  = 462. Se colocan cuadrados de tamaño 462 × 462 dentro de él dejando un rectángulo de 462 × 147. Este rectángulo se alicata con 147 × 147 cuadrados hasta dejar un rectángulo de 21 × 147, que a su vez se alicata con 21 × 21 cuadrados, sin dejar ningún área descubierta. El tamaño cuadrado más pequeño, 21, es el MCD de 1071 y 462.

Por ejemplo, el algoritmo euclidiano se puede utilizar para encontrar el máximo común divisor de a  = 1071 yb  = 462. Para empezar, se restan múltiplos de 462 de 1071 hasta que el resto sea menor que 462. Se pueden restar dos de estos múltiplos ( q 0  = 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 1  = 3), dejando un resto de 21:

462 = 3 × 147 + 21

Luego se restan múltiplos de 21 de 147 hasta que el resto sea menor que 21. Se pueden restar siete múltiplos ( q 2  = 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) que se encontró mediante la factorización prima anterior . En forma tabular, los pasos son:

Paso k Ecuación Cociente y resto
0 1071 = q 0 462 + r 0 q 0 = 2 y r 0 = 147
1 462 = q 1 147 + r 1 q 1 = 3 y r 1 = 21
2 147 = q 2 21 + r 2 q 2 = 7 y r 2 = 0 ; finaliza el algoritmo

Visualización

El algoritmo euclidiano se puede visualizar en términos de la analogía de mosaico dada anteriormente para el máximo común divisor. Supongamos que deseamos cubrir un un -by- b rectángulo con baldosas cuadradas exactamente, donde una es el mayor de los dos números. Primero intentamos enlosar el rectángulo usando b- por- b mosaicos cuadrados; sin embargo, esto deja un rectángulo residual r 0 -por- b sin enlosar, donde r 0  <  b . Luego intentamos enlosar el rectángulo residual con r 0 -por- r 0 mosaicos cuadrados. Esto deja un segundo rectángulo residual r 1 -por- r 0 , que intentamos enlosar usando r 1 -por- r 1 mosaicos cuadrados, y así sucesivamente. La secuencia finaliza cuando no hay ningún rectángulo residual, es decir, cuando las baldosas cuadradas cubren exactamente el rectángulo residual anterior. La longitud de los lados de la loseta 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 por 21 (mostrado en rojo), y 21 es el MCD de 1071 y 462, las dimensiones del rectángulo original (mostrado en verde).

División euclidiana

En cada paso k , el algoritmo euclidiano calcula un cociente q k y el resto r k a partir 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 asegura que tal cociente y resto siempre existen y son únicos.

En la versión original del algoritmo de Euclides, el cociente y el resto se encuentran por 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, r k y r k −1 se intercambian y el proceso se itera. La división euclidiana reduce todos los pasos entre dos intercambios en un solo paso, por lo que es más eficiente. Además, los cocientes no son necesarios, por lo que se puede reemplazar la división euclidiana por la operación módulo , que da solo el resto. Por lo tanto, la iteración del algoritmo euclidiano se 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 divisiones puede programarse como

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

Al comienzo de la k- ésima iteración, la variable b contiene el último resto r k −1 , mientras que la variable a contiene su predecesora, r k −2 . El paso b  : = a mod b es equivalente a la fórmula de recursión anterior r kr k −2 mod r k −1 . La variable temporal t tiene el valor de r k −1 mientras se calcula el siguiente resto r k . Al final de la iteración del ciclo, la variable b contiene el resto r k , mientras que la variable a tiene su predecesora, 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 max (a, −a).)

En la versión basada en la resta, que era la versión original de Euclid, el cálculo restante ( ) se reemplaza por una resta repetida. A diferencia de la versión basada en divisiones, que funciona con enteros arbitrarios como entrada, la versión basada en restas supone que la entrada consta de enteros positivos y se detiene cuando a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Las variables a y b alternativo que sostiene los restos anteriores r k -1 y r k -2 . Suponga 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 ciclo, a se reduce en múltiplos del resto anterior b hasta que a es menor que b . Entonces a es el siguiente resto r k . Entonces b se reduce en múltiplos de a hasta que vuelve a ser más pequeño que a , dando el siguiente resto r k +1 , y así sucesivamente.

La versión recursiva se basa en la igualdad de los MCD de los residuos sucesivos y la condición de parada mcd ( r N −1 , 0) =  r N −1 .

function gcd(a, b)
    if b = 0
        return a
    else
        return 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)".)

Por ejemplo, el mcd (1071, 462) se calcula a partir del mcd equivalente (462, 1071 mod 462) = mcd (462, 147). El último MCD se calcula a partir del mcd (147, 462 mod 147) = mcd (147, 21), que a su vez se calcula a partir del mcd (21, 147 mod 21) = mcd (21, 0) = 21.

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. Anteriormente, la ecuación

r k −2 = q k r k −1 + r k

asumió que | r k −1 | >  r k  > 0 . Sin embargo, se puede calcular un resto negativo alternativo e k :

r k −2 = ( q k + 1) r k −1 + e k

si r k −1  > 0 o

r k −2 = ( q k - 1) r k −1 + e k

si r k −1  <0 .

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

| r k | ≤ | r k −1 | / 2

en cada paso.

Leopold Kronecker ha demostrado que esta versión requiere la menor cantidad de pasos de cualquier versión del algoritmo de Euclid. Más en general, se ha demostrado que, por cada números de entrada a y b , el número de pasos es mínimo si y sólo si q k se elige a fin de que donde es la proporción de oro .

Desarrollo historico

"Representación de Euclides como un hombre barbudo que sostiene un par de separadores en una tableta".
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. Aparece en los Elementos de Euclides (c. 300 aC), específicamente en el Libro 7 (Proposiciones 1-2) y el Libro 10 (Proposiciones 2-3). En el Libro 7, el algoritmo se formula para números enteros, mientras que en el Libro 10, se formula para longitudes de segmentos de línea. (En el uso moderno, se diría que se formuló allí para números reales . Pero las longitudes, áreas y volúmenes, representados como números reales en el uso moderno, no se miden en las mismas unidades y no hay una unidad natural de longitud, área, o volumen; el concepto de números reales era desconocido en ese momento.) El último algoritmo es geométrico. El MCD de dos longitudes a y b corresponde a la mayor longitud g que las medidas a y b de manera uniforme; en otras palabras, las longitudes de un y b son ambos múltiplos enteros de la longitud g .

El algoritmo probablemente no fue descubierto por Euclid , quien compiló resultados de matemáticos anteriores en sus Elementos . 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 . El algoritmo probablemente fue conocido por Eudoxo de Cnidus (alrededor del 375 aC). El algoritmo puede incluso ser anterior a Eudoxo, a juzgar por el uso del término técnico ἀνθυφαίρεσις ( antifáiresis , resta recíproca) en las obras de Euclides y Aristóteles .

Siglos más tarde, el algoritmo de Euclides se descubrió de forma independiente tanto en India como en China, principalmente para resolver ecuaciones diofánticas que surgieron en astronomía y hacer calendarios precisos. A finales del siglo V, el matemático y astrónomo indio Aryabhata describió el algoritmo como el "pulverizador", quizás debido a su eficacia para resolver ecuaciones diofánticas. Aunque ya se había descrito un caso especial del teorema del resto chino en el libro chino Sunzi Suanjing , la solución general fue publicada por Qin Jiushao en su libro de 1247 Shushu Jiuzhang (數 書 九章Tratado matemático en nueve secciones ). El algoritmo euclidiano se describió por primera vez numéricamente y se popularizó en Europa en la segunda edición de Problèmes plaisants et délectables de Bachet ( Problemas agradables y agradables , 1624). 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 , quien lo atribuyó a Roger Cotes como un método para calcular fracciones continuas de manera eficiente.

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 usó el algoritmo euclidiano para demostrar la factorización única de los enteros gaussianos , aunque su trabajo se publicó por primera vez en 1832. Gauss mencionó el algoritmo en sus Disquisitiones Arithmeticae (publicado en 1801), pero solo como un método para fracciones continuas . Peter Gustav Lejeune Dirichlet parece haber sido el primero en describir el algoritmo euclidiano como la base de gran parte de la teoría de números. 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. Las conferencias de Lejeune Dirichlet sobre teoría de números fueron editadas y extendidas por Richard Dedekind , quien utilizó el algoritmo de Euclides para estudiar los enteros algebraicos , un nuevo tipo general de número. Por ejemplo, Dedekind fue el primero en probar el teorema de los dos cuadrados de Fermat utilizando la factorización única de los enteros gaussianos. 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 .

"[El algoritmo euclidiano] es el abuelo de todos los algoritmos, porque es el algoritmo no trivial más antiguo que ha sobrevivido hasta el día de hoy".

Donald Knuth , El arte de la programación informática, vol. 2: Algoritmos seminuméricos , 2ª edición (1981), pág. 318.

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 la cadena de Sturm para contar las raíces reales de polinomios en cualquier intervalo dado.

El algoritmo euclidiano fue el primer algoritmo de relación de enteros , que es un método para encontrar relaciones de enteros entre números reales conmensurables. Se han desarrollado varios algoritmos novedosos de relación de enteros , como el algoritmo de Helaman Ferguson y RW Forcade (1979) y el algoritmo LLL .

En 1969, Cole y Davie desarrollaron un juego para dos jugadores basado en el algoritmo euclidiano, llamado The Game of Euclid , que tiene una estrategia óptima. Los jugadores comienzan con dos pilas de unos y b piedras. Los jugadores se turnan para quitar m múltiplos de la pila más pequeña de la más grande. Por lo tanto, si las dos pilas consisten en X y Y las piedras, donde x es mayor que y , el siguiente jugador puede reducir la pila más grande de x piedras para x - mis piedras, siempre y cuando este último es un número entero no negativo. El ganador es el primer jugador en reducir una pila a cero piedras.

Aplicaciones matemáticas

La identidad de Bézout

La identidad de Bézout estados que el máximo común divisor g de dos enteros una y b pueden ser representados como una suma lineal de los dos números originales una y b . En otras palabras, siempre es posible encontrar números enteros s y t tal que g  =  sa  +  tb .

Los enteros s y t se puede calcular a partir de los cocientes q 0 , q 1 , etc. invirtiendo el orden de las ecuaciones en el algoritmo de Euclides. 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 :

g = r N −1 = r N −3 - q N −1 r N −2  .

Esos dos residuos pueden expresarse igualmente en términos de sus cocientes y residuos precedentes,

r N −2 = r N −4 - q N −2 r N −3 y
r N −3 = r N −5 - q N −3 r N −4  .

Sustituyendo estas fórmulas para r N −2 y r N −3 en la primera ecuación se obtiene g como una suma lineal de los residuos r N −4 y r N −5 . El proceso de sustitución de restos de fórmulas que implican sus predecesores se puede continuar hasta que los números originales a y b son accesibles:

r 2 = r 0 - q 2 r 1
r 1 = segundo - q 1 r 0
r 0 = a - q 0 b .

Después de todo los residuos r 0 , r 1 , etc. han sido sustituidos, la ecuación final expresa g como una suma lineal de una y b : g  =  sa  +  tb . La identidad de Bézout , y por lo tanto el algoritmo anterior, pueden generalizarse al contexto de los dominios euclidianos .

Principales ideales y problemas relacionados

La identidad de Bézout proporciona otra definición del máximo común divisor g de dos números a y b . Considere el conjunto de todos los números ua  +  vb , donde u y v son dos enteros cualesquiera. Dado que a y b son divisibles por g , cada número del conjunto es divisible por g . En otras palabras, cada número del conjunto es un múltiplo entero de g . Esto es cierto para todos los divisores comunes de una y b . Sin embargo, a diferencia de otros divisores comunes, el máximo común divisor es un miembro del conjunto; por la identidad de Bézout, eligiendo u  =  s y v  =  t 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 . A la inversa, cualquier múltiplo m de g puede obtenerse eligiendo u  =  ms y v  =  mt , donde s y t son los números enteros de la identidad de Bézout. Esto puede verse multiplicando la identidad de Bézout por m ,

mg = msa + mtb .

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

Algunos problemas se pueden resolver con este resultado. Por ejemplo, considere dos tazas de medición de volumen de una y b . Al sumar / restar 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 ( ab ).

Algoritmo euclidiano extendido

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

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 −2 = 1, t −2 = 0
s −1 = 0, t −1 = 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 se puede demostrar por inducción. Suponga que la fórmula de recursividad es correcta hasta el paso k  - 1 del algoritmo; en otras palabras, suponga que

r j = s j una + 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 supuesto que la fórmula de recursión es correcta para r k −2 y r k −1 , pueden expresarse en términos de las correspondientes variables s y t

r k = ( s k −2 a + t k −2 b ) - q k ( s k −1 a + t k −1 b ).

Reordenando esta ecuación se obtiene la fórmula de recursividad para el paso k , según sea necesario

r k = s k a + t k b = ( s k −2 - q k s k −1 ) a + ( t k −2 - q k t k −1 ) b .

Método de matriz

Los enteros s y t también se puede encontrar utilizando un equivalente de matriz método. La secuencia de ecuaciones del algoritmo de Euclides.

se puede escribir como un producto de matrices de cociente de 2 por 2 multiplicando un vector residual bidimensional

Sea M el producto de todas las matrices de cocientes

Esto simplifica el algoritmo euclidiano a la forma

Para expresar g como una suma lineal de una y b , ambos lados de esta ecuación pueden multiplicarse por el inverso de la matriz M . 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. Dado que el determinante de M nunca es cero, el vector de los residuos finales se puede resolver usando la inversa de M

Dado que la ecuación superior da

g = (−1) N +1 ( m 22 a - m 12 b ),

los dos enteros de la identidad de Bézout son s  = (−1) N +1 m 22 y t  = (−1) N m 12 . El método matricial es tan eficiente como la recursividad equivalente, con dos multiplicaciones y dos adiciones por paso del algoritmo euclidiano.

Lema de Euclides y factorización única

La identidad de Bézout es esencial para muchas aplicaciones del algoritmo de Euclid, como demostrar la factorización única de números en factores primos. Para ilustrar esto, suponga que un número L se puede escribir como un producto de dos factores u y v , es decir, L  =  uv . Si otro número w también divide L pero es primos entre sí 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 los números enteros s y t se puede encontrar de tal manera que

1 = su + tw  .

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

v = SUV + TWV = sL + TWV  .

Dado que w divide ambos términos en el lado derecho, también debe dividir el lado izquierdo, v . Este resultado se conoce como lema de Euclides . En concreto, si un número primo divide 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 1 , a 2 , ..., a n , entonces w también es coprimo de su producto, a 1  ×  a 2  × ... ×  a n .

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

L = p 1 p 2p m = q 1 q 2q n  .

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

Ecuaciones lineales diofánticas

"Una línea diagonal que va desde la esquina superior izquierda a la inferior derecha. Quince círculos están espaciados a intervalos regulares a lo largo de la línea. Los ejes de coordenadas xy perpendiculares tienen su origen en la esquina inferior izquierda; la línea cruza el eje y en la esquina superior izquierda y cruce el eje x en la parte inferior derecha ".
Gráfica 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 Diofanto del siglo III . Un típico lineal ecuación Diophantine busca números enteros x e y tales que

ax + por = c

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

axc mod b .

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

sa + tb = g

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

En general, una ecuación diofántica lineal no tiene soluciones o tiene un número infinito de soluciones. Para encontrar este último, considere dos soluciones, ( x 1y 1 ) y ( x 2y 2 ), donde

ax 1 + por 1 = c = ax 2 + por 2

o equivalente

a ( x 1 - x 2 ) = b ( y 2 - y 1 ).

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

x = x 1 - bu / g
y = y 1 + au / g .

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

Inversas multiplicativas y el algoritmo RSA

Un campo finito es un conjunto de números con cuatro operaciones generalizadas. Las operaciones se denominan suma, resta, multiplicación y división y tienen sus propiedades habituales, como conmutatividad , asociatividad y distributividad . Un ejemplo de un campo finito es el conjunto de 13 números {0, 1, 2, ..., 12} usando aritmética modular . En este campo, el resultado de cualquier operación matemática (suma, resta, multiplicación o división) se reduce módulo 13; es decir, se suman o restan múltiplos de 13 hasta que el resultado se coloca 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 ( p m ).   

En un campo de este tipo con m números, cada elemento distinto de cero una tiene un único inverso multiplicativo modular , un -1 tal que AA -1  =  un -1 un  ≡ 1 mod  m . Esta inversa se puede encontrar resolviendo la ecuación de congruencia ax  ≡ 1 mod  m , o la ecuación diofántica lineal equivalente

ax + mi = 1.

Esta ecuación se puede resolver mediante el algoritmo euclidiano, como se describe anteriormente . Encontrar inversas multiplicativas 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. Aunque el algoritmo RSA usa anillos en lugar de campos, el algoritmo euclidiano aún se puede usar para encontrar un inverso multiplicativo donde exista uno. El algoritmo euclidiano también tiene otras aplicaciones en códigos de corrección de errores ; por ejemplo, se puede utilizar como una alternativa al algoritmo de Berlekamp-Massey para decodificar códigos BCH y Reed-Solomon , que se basan en campos de Galois.

Teorema del resto chino

El algoritmo de Euclides también se puede utilizar para resolver múltiples ecuaciones diofánticas lineales. Estas 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, puede ser representado por sus restos x i módulo un conjunto de N números coprimos m i :

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

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

Con estos números h i , cualquier entero x se puede reconstruir a partir de sus restos x i mediante la ecuación

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 organizar 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 ) utilizando 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 a su hijo derecho, y un paso que reemplaza el segundo de los dos números corresponde a un paso en el árbol desde un nodo. a su hijo izquierdo. La secuencia de pasos construida de esta manera no depende de si a / b se da en los términos más bajos y forma un camino desde la raíz hasta un nodo que contiene el número a / b . Este hecho puede usarse para probar 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 a la izquierda una vez, luego a la derecha dos veces:

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

El algoritmo euclidiano tiene casi la misma relación con otro árbol binario en los 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 . La secuencia de ecuaciones se puede escribir en la forma

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

La tercera ecuación se puede utilizar para sustituir el término denominador r 1 / r 0 , dando

La razón final de los residuos 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

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 se puede escribir

como puede confirmarse mediante cálculo.

Algoritmos de factorización

Calcular un máximo común divisor es un paso esencial en varios algoritmos de factorización de enteros , como el algoritmo rho de Pollard , el algoritmo de Shor , el método de factorización de Dixon y la factorización de la curva elíptica de Lenstra . El algoritmo euclidiano se puede utilizar para encontrar este GCD de manera eficiente. La factorización de fracciones continuas utiliza fracciones continuas, que se determinan mediante el algoritmo de Euclid.

Eficiencia algorítmica

"Un conjunto de líneas coloreadas que se irradian hacia afuera desde el origen de un sistema de coordenadas xy. Cada línea corresponde a un conjunto de pares de números que requieren el mismo número de pasos en el algoritmo euclidiano".
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 Euclid se ha estudiado a fondo. 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, quien mostró que el número de pasos de división en la entrada ( u , v ) está acotado por v ; luego mejoró esto a v / 2 + 2. Más tarde, en 1841, PJE Finck mostró que el número de pasos de división es como máximo 2 log 2  v  + 1, y por lo tanto el algoritmo de Euclides se ejecuta en polinomios de tiempo en el tamaño de la entrada. Émile Léger , en 1837, estudió el peor de los casos, que es cuando las entradas son números de Fibonacci consecutivos . El análisis de Finck fue refinado por Gabriel Lamé en 1844, quien mostró que el número de pasos requeridos para completar nunca es más de cinco veces el número h de dígitos en base 10 del número menor  b .

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

Numero de pasos

El número de pasos para calcular el MCD de dos números naturales, un y b , pueden estar indicados por T ( unb ). Si g es el MCD de un y b , a continuación, un  =  mg y b  =  ng por dos números coprimos m y n . Luego

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

como puede verse dividiendo todos los pasos del algoritmo euclidiano por g . Por el mismo argumento, el número de pasos sigue siendo el mismo si una y b se multiplican por un factor común w : T ( un , 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 ( ab  + 1), dependiendo del tamaño de los dos GCD.

La naturaleza recursiva del algoritmo euclidiano da otra ecuación

T ( un , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = ... = N + T ( r N -2 , r N -1 ) = N + 1

donde T ( x , 0) = 0 por supuesto.

Peor de los casos

Si el algoritmo de Euclides requiere N pasos para un par de números naturales a  >  b  > 0, los valores más pequeños de una y b para los que esto es cierto son los números de Fibonacci F N 2 y F N 1 , respectivamente. Más precisamente, si el algoritmo euclidiano requiere N pasos para el par a  >  b , entonces uno tiene a  ≥  F N +2 y b  ≥  F N +1 . Esto se puede demostrar por inducción . Si N  = 1, b divide un sin resto; los números naturales más pequeños para los que esto es cierto son b  = 1 y a  = 2, que son F 2 y F 3 , respectivamente. Ahora suponga 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 0 b  +  r 0 , y el algoritmo euclidiano requiere M  - 1 pasos para el par b  >  r 0 . Por hipótesis de inducción, uno tiene b  ≥  F M 1 y r 0  ≥  F M . Por lo tanto, a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  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 y también la primera aplicación práctica de los números de Fibonacci.

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). Porque si el algoritmo requiere N pasos, entonces b es mayor o igual que F N +1 que a su vez es mayor o igual que φ N −1 , donde φ es la proporción áurea . Dado que b  ≥  φ N −1 , entonces N  - 1 ≤ log φ b . Dado que log 10 φ  > 1/5, ( N  - 1) / 5 <log 10 φ  log φ b  = log 10 b . Por tanto, N  ≤ 5 log 10 b . Por lo tanto, el algoritmo euclidiano siempre necesita menos de O ( h ) divisiones, donde h es el número de dígitos en el número 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 de los enteros 0 a a  - 1

Sin embargo, dado que T ( ab ) fluctúa drásticamente con el MCD de los dos números, la función promedio T ( a ) es igualmente "ruidosa".

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

Hay φ ( a ) enteros coprimos menores que a , donde φ es la función totiente de Euler . Este promedio de tau crece suavemente con un

siendo el error residual de orden a - (1/6) + ε , donde ε es infinitesimal . La constante C ( constante de Porter ) en esta fórmula es igual a

donde γ es la constante de Euler-Mascheroni y ζ 'es la derivada de la función zeta de Riemann . El coeficiente principal (12 / π 2 ) ln 2 se determinó mediante dos métodos independientes.

Dado que el primer promedio se puede calcular a partir del promedio de tau sumando los divisores d de  un

se puede aproximar mediante la fórmula

donde Λ ( d ) es la función de Mangoldt .

Un tercer promedio Y ( n ) se define como el número medio de pasos requeridos cuando tanto a como b se eligen al azar (con distribución uniforme) de 1 a n

Sustituyendo la fórmula aproximada de T ( a ) en esta ecuación se obtiene una estimación de Y ( n )

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 dado de enteros 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 la determinación de 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 se escala como O ( h ( +1)), donde es la longitud del cociente.

A modo de comparación, el algoritmo original basado en restas de Euclid puede ser mucho más lento. Una sola división entera equivale al cociente q número de restas. Si la relación entre un y b es muy grande, el cociente es grande y se requiere muchas sustracciones. 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 | u / ( u  - 1) | donde u  = ( q  + 1) 2 . Por ejemplo, la probabilidad de un cociente de 1, 2, 3 o 4 es aproximadamente del 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, el algoritmo de Euclid basado en la resta es competitivo con la versión basada en la división. Esto se explota en la versión binaria del algoritmo de Euclid.

Combinando el número estimado de pasos con el coste de cálculo estimado por muestra paso a que el algoritmo de Euclides crece cuadráticamente ( h 2 ) con el número promedio de dígitos h en los dos números iniciales una y b . Sea h 0 , h 1 , ..., h N −1 representar el número de dígitos en los restos sucesivos r 0r 1 , ...,  r N −1 . Dado que el número de pasos N crece linealmente con h , el tiempo de ejecución está limitado por

Metodos alternativos

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

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 divisor común más grande. Los divisores comunes se pueden encontrar dividiendo ambos números entre números 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 enfoque 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 que comparten los dos números de una y b . Los métodos actuales de factorización prima también son ineficaces; muchos sistemas criptográficos modernos incluso se basan en esa ineficiencia.

El algoritmo binario GCD es una alternativa eficiente que sustituye la división con operaciones más rápidas al explotar la representación binaria utilizada por las computadoras. 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. Eficiencia adicional puede ser obtenida mediante el examen de sólo los dígitos iniciales de los dos números de una y b . El algoritmo binario se puede extender a otras bases ( algoritmos k -ary), con incrementos de velocidad de hasta cinco veces. 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 enteros muy grandes (con más de 25.000 dígitos) conduce a algoritmos GCD de enteros cuasilineales , como los de Schönhage y Stehlé y Zimmermann. Estos algoritmos explotan la forma matricial 2 × 2 del algoritmo euclidiano dado anteriormente . Estos métodos cuasilineales generalmente escalan como O ( h (log h ) 2 (log log h )).

Generalizaciones

Aunque el algoritmo euclidiano se utiliza para encontrar el máximo común divisor de dos números naturales (enteros positivos), puede generalizarse a los números reales y a otros objetos matemáticos, como polinomios , enteros cuadráticos y cuaterniones de Hurwitz . 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 se pueden factorizar de forma única en elementos irreductibles , 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 , 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 dadas, un y b , son números enteros múltiplos de ella: un = mg y b = ng , donde m y n son números enteros . Esta identificación es equivalente a encontrar una relación número entero entre los números reales a y b ; es decir, que determina los números enteros s y t que tales sa + tb = 0 . Euclid usa este algoritmo para tratar la cuestión de longitudes inconmensurables .

El algoritmo euclidiano de números reales difiere de su contraparte entera en dos aspectos. Primero, los residuos r k son números reales, aunque los cocientes q k son 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 enteros

y puede escribirse como una fracción continua finita [ q 0 ; q 1 , q 2 , ..., q N ] . 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 0 ; q 1 , q 2 ,…] . Ejemplos de fracciones continuas infinitas son la proporción áurea φ = [1; 1, 1, ...] y la raíz cuadrada de dos , 2 = [1; 2, 2, ...] . Es poco probable que el algoritmo se detenga, ya que casi todas las relaciones a / b de dos números reales son irracionales.

Una fracción continua infinita se puede truncar en un paso k [ q 0 ; q 1 , q 2 , ..., q k ] para obtener 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

donde m −1 = n −2 = 1 y m −2 = n −1 = 0 son los valores iniciales de la recursividad. El convergente m k / n k es la mejor aproximación de número racional a a / b con denominador n k :

Polinomios

Los polinomios en una sola variable x se pueden sumar, multiplicar y factorizar en polinomios irreducibles , que son los análogos de los números primos para números enteros. El mayor polinomio 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. 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 restante r k ( x ) para satisfacer la ecuación recursiva

donde r −2 ( x ) = a ( x ) y r −1 ( x ) = b ( x ) . Cada polinomio de cociente se elige de modo que cada resto sea cero o tenga un grado menor que el grado de su predecesor: deg [ r k ( x )] <deg [ r k −1 ( x )] . Dado que el grado es un número entero no negativo y que 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 ) .

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

Al dividir a ( x ) por b ( x ) se obtiene un resto r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x - (2/3) . En el siguiente paso, b ( x ) se divide por r 0 ( x ) dando un resto r 1 ( x ) = x 2 + x + 2 . Finalmente, dividir r 0 ( x ) por r 1 ( x ) produce un residuo cero, lo que indica que r 1 ( x ) es el mayor polinomio común divisor de a ( x ) y b ( x ) , de acuerdo con su factorización.

Muchas de las aplicaciones descritas anteriormente para números enteros se trasladan a polinomios. El algoritmo euclidiano se puede utilizar para resolver ecuaciones diofánticas lineales y problemas de residuo chino 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 dado . Esto a su vez tiene aplicaciones en varias áreas, como el criterio de estabilidad de Routh-Hurwitz en la teoría de control .

Por último, no es necesario extraer los coeficientes de los polinomios a partir de números enteros, números reales o incluso números complejos. Por ejemplo, los coeficientes se pueden extraer 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.

Enteros gaussianos

"Un conjunto de puntos que se encuentran dentro de un círculo. El patrón de puntos tiene una simetría cuádruple, es decir, las rotaciones de 90 grados dejan el patrón sin cambios. El patrón también se puede reflejar en cuatro líneas que pasan por el centro del círculo: la vertical y la horizontal ejes y las dos líneas diagonales a ± 45 grados ".
Distribución de los primos gaussianos u + vi en el plano complejo, con normas u 2 + v 2 menores que 500

Los enteros gaussianos son números complejos de la forma α = u + vi , donde u y v son enteros ordinarios e i es la raíz cuadrada del uno negativo . Al definir un análogo del algoritmo euclidiano, se puede demostrar que los enteros gaussianos son factorizables de forma única, mediante el argumento anterior . Esta factorización única es útil en muchas aplicaciones, como derivar todos los triples de Pitágoras o demostrar el teorema de Fermat en sumas de dos cuadrados . En general, el algoritmo euclidiano es conveniente en tales aplicaciones, pero no esencial; por ejemplo, los teoremas a menudo pueden probarse con otros argumentos.

El algoritmo euclidiano desarrollado para dos enteros gaussianos α y β es casi el mismo que el de los enteros ordinarios, pero difiere en dos aspectos. Como antes, la tarea en cada paso k es identificar un cociente q k y un resto r k tal que

donde r k −2 = α , donde r k −1 = β , y donde cada resto es estrictamente más pequeño que su predecesor: | r k | <| r k −1 | . La primera diferencia es que los cocientes y los residuos son en sí mismos enteros gaussianos y, por tanto, son números complejos . Los cocientes q k generalmente se encuentran redondeando las partes real y compleja de la razón exacta (como el número complejo α / β ) a los números enteros más cercanos. La segunda diferencia radica en la necesidad de definir cómo un resto complejo puede ser "más pequeño" que otro. Para ello, se define una función normal f ( u + vi ) = u 2 + v 2 , que convierte todo 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. El resto final distinto de cero es gcd ( α , β ) , el entero gaussiano de norma más grande que divide tanto α como β ; es único hasta la multiplicación por una unidad, ± 1 o ± i .

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 residuo chino para enteros gaussianos; También se pueden definir fracciones continuas de enteros gaussianos.

Dominios euclidianos

Un conjunto de elementos bajo dos operaciones binarias , denotado como suma y multiplicación, se llama dominio euclidiano si forma un anillo conmutativo R y, en términos generales, si se puede realizar un algoritmo euclidiano generalizado sobre ellos. 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 , asociatividad y distributividad .

El algoritmo de Euclides generalizada requiere una función euclidiana , es decir, un mapeo f de R en el conjunto de enteros no negativos tal que, para cualquier par de elementos no nulos de un y b en R , existen q y r en R tal que un = qb + r y f ( r ) < f ( b ) . Ejemplos de tales asignaciones son el valor absoluto de los números enteros, el grado de los polinomios univariados y la norma anterior de los números enteros gaussianos . 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 ordenación correcta de los enteros no negativos, que afirma que todo conjunto no vacío de enteros no negativos tiene un miembro más pequeño.

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. Los dominios euclidianos y las UFD son subclases de los dominios GCD , dominios en los que siempre existe un máximo común divisor de dos números. En otras palabras, puede existir un máximo común divisor (para todos los pares de elementos en un dominio), aunque puede que no sea posible encontrarlo usando un algoritmo euclidiano. Un dominio euclidiano es siempre un dominio ideal principal (PID), un dominio integral en el que todo ideal es un ideal principal . Una vez más, lo contrario no es cierto: no todos los PID son un dominio euclidiano.

La factorización única de los dominios euclidianos es útil en muchas aplicaciones. Por ejemplo, la factorización única de los enteros gaussianos es conveniente para derivar fórmulas para todas las triples pitagóricas y para demostrar el teorema de Fermat sobre sumas de dos cuadrados . La factorización única también fue un elemento clave en un intento de demostración del último teorema de Fermat publicado en 1847 por Gabriel Lamé, el mismo matemático que analizó la eficiencia del algoritmo de Euclides, basado en una sugerencia de Joseph Liouville . El enfoque de Lamé requiere la factorización única de números de la forma x + ωy , donde x y y son números enteros, y ω = e 2 / n es un n º raíz de 1, es decir, ω n = 1 . Aunque este enfoque tiene éxito para algunos valores de n (como n = 3 , los números 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 a los ideales .

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

"Un conjunto de puntos que se encuentran dentro de un círculo. El patrón de puntos tiene una simetría séxtuple, es decir, las rotaciones de 60 grados dejan el patrón sin cambios. El patrón también se puede reflejar alrededor de seis líneas que pasan por el centro del círculo: la vertical y la horizontal ejes y las cuatro líneas diagonales a ± 30 y ± 60 grados ".
Distribución de primos de Eisenstein u + en el plano complejo, con normas menores que 500. El número ω es una raíz cúbica de 1 .

Los anillos 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 + , donde u y v son números enteros y ω tiene una de dos formas, dependiendo de un parámetro D . Si D no es un múltiplo de cuatro más uno, entonces

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

Si la función f corresponde a una función norma , como la que se usó para ordenar los enteros gaussianos arriba , entonces el dominio se conoce como norma-euclidiana . Los anillos norm-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. Los casos D = −1 y D = −3 producen los enteros de Gauss 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 para los que el dominio es euclidiano. El primer ejemplo de un dominio euclidiano que no era euclidiano normativo (con D = 69 ) se publicó en 1994. En 1973, Weinberger demostró que un anillo entero cuadrático con D > 0 es euclidiano si, y solo si, es un anillo principal dominio ideal , siempre que se mantenga la hipótesis de Riemann generalizada .

Anillos no conmutativos

El algoritmo euclidiano se puede aplicar a algunos anillos no conmutativos como el conjunto de cuaterniones de Hurwitz . Dejemos que α y β representen 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 α = y β = 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 los divisores de la derecha y otra para los divisores de la izquierda. Al elegir los divisores correctos, se puede escribir el primer paso para encontrar el mcd ( α , β ) mediante el algoritmo euclidiano

donde ψ 0 representa el cociente y ρ 0 el resto. Esta ecuación muestra que cualquier divisor común a la derecha de α y β es igualmente un divisor común del resto ρ 0 . La ecuación análoga para los divisores izquierdos sería

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

La mayoría de los resultados del GCD se transfieren a números no conmutativos. Por ejemplo, la identidad de Bézout establece que el mcd derecho ( α , β ) se puede expresar como una combinación lineal de α y β . En otras palabras, hay números σ y τ tales que

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

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 en los GCD de cuaterniones de esta manera.

Ver también

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

Notas

Referencias

Bibliografía

enlaces externos