Algoritmo de Euclides

El algoritmo de Euclides es un algoritmo eficiente para encontrar el máximo común divisor de dos números enteros (o la medida común de dos segmentos ). El algoritmo lleva el nombre del matemático griego Euclides (siglo III a. C.), quien lo describió por primera vez en los libros VII [1] y X [2] de " Comienzos ". Es uno de los algoritmos numéricos más antiguos en uso en la actualidad [3] .

En su forma más simple, el algoritmo de Euclides se aplica a un par de enteros positivos y genera un nuevo par que consiste en el número más pequeño y la diferencia entre los números más grande y más pequeño. El proceso se repite hasta que los números sean iguales. El número encontrado es el máximo común divisor del par original. Euclid propuso un algoritmo solo para números naturales y cantidades geométricas (longitudes, áreas, volúmenes). Sin embargo, en el siglo XIX se generalizó a otros tipos de objetos matemáticos , incluidos los enteros gaussianos y polinomios en una variable . Esto condujo a la aparición del concepto del anillo euclidiano en el álgebra general moderna . Posteriormente, el algoritmo de Euclides se generalizó a otras estructuras matemáticas como nudos y polinomios multidimensionales .

Hay muchas aplicaciones teóricas y prácticas para este algoritmo. En particular, es la base del algoritmo criptográfico de clave pública RSA [4] , que es ampliamente utilizado en el comercio electrónico . El algoritmo también se utiliza para resolver ecuaciones diofánticas lineales [5] , para construir fracciones continuas [6] , en el método de Sturm [7] . El algoritmo de Euclides es la herramienta principal para probar teoremas en la teoría de números moderna , como el teorema de los cuatro cuadrados de Lagrange [8] y el teorema fundamental de la aritmética [9] .

Historia

Los antiguos matemáticos griegos llamaron a este algoritmo ἀνθυφαίρεσις o ἀνταναίρεσις - "resta mutua". Este algoritmo no fue descubierto por Euclides , ya que existe una mención de él en el Topic de Aristóteles (siglo IV aC) [3] . En "Elementos" de Euclides se describe dos veces: en el Libro VII para encontrar el máximo común divisor de dos números naturales [1] y en el Libro X para encontrar la mayor medida común de dos cantidades homogéneas [2] . En ambos casos, se da una descripción geométrica del algoritmo para encontrar la "medida común" de dos segmentos.

Los historiadores de las matemáticas han sugerido que fue con la ayuda del algoritmo de Euclides (el procedimiento de sustracción mutua sucesiva) que la existencia de cantidades inconmensurables (lados y diagonales de un cuadrado, o lados y diagonales de un pentágono regular ) fue descubierta por primera vez en la antigüedad. Matemáticas griegas [10] . Sin embargo, esta suposición no cuenta con suficiente evidencia documental. Un algoritmo para encontrar el máximo común divisor de dos números naturales también se describe en el Libro I del antiguo tratado chino Matemáticas en nueve libros .

Descripción

Algoritmo de Euclides para números enteros

Sean y números enteros no simultáneamente iguales a cero, y una secuencia de números $a$ $b$

{\displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}>\ \dots \ >r_{n))

se define por el hecho de que cada uno es el resto de dividir el número anterior por el anterior, y el penúltimo se divide por el último, es decir: $r_{k}$

a=bq_{0}+r_{1},

b=r_{1}q_{1}+r_{2},

r_{1}=r_{2}q_{2}+r_{3},

\cdots

r_{k-2}=r_{k-1}q_{k-1}+r_{k},

\cdots

r_{n-2}=r_{n-1}q_{n-1}+r_{n},

r_{n-1}=r_{n}q_{n}.

Entonces mcd( a , b ), el máximo común divisor de a y b , es igual a r n , el último miembro distinto de cero de esta secuencia [11] .

La existencia de tal r 1 , r 2 , …, r n , es decir, la posibilidad de división con resto m por n para cualquier entero m y entero n ≠ 0, se prueba por inducción sobre m .

La corrección de este algoritmo se deriva de las siguientes dos afirmaciones [12] :

I. Sea a = b ⋅ q + r , luego mcd (a, b) = mcd (b, r).

Prueba

Sea k cualquier divisor común de los números a y b , no necesariamente el mayor, entonces a = t 1 ⋅ k y b = t 2 ⋅ k , donde t 1 y t 2 son números enteros de la definición.
Entonces k también es un divisor común de b y r , ya que b es divisible por k por definición, a (la expresión entre paréntesis es un número entero, por lo que k divide a r sin resto). $r=ab\cdot q=(t_{1}-t_{2}\cdot q)\cdot k$
Lo contrario también es cierto y se demuestra de manera similar al punto 2: cualquier divisor de b y r también es divisor de a y b .
Por lo tanto, todos los divisores comunes de los pares de números ( a , b ) y ( b , r ) son iguales. En otras palabras, no hay divisor común de números ( a , b ) que no sea también divisor de ( b , r ), y viceversa.
En particular, el máximo común divisor sigue siendo el mismo, ya que suponiendo que mcd ( a , b ) > mcd ( b , r ) o mcd ( a , b ) < mcd ( b , r ) se obtienen contradicciones, por lo tanto, mcd ( a , segundo ) = mcd ( segundo , r ) . QED

II. mcd( r , 0) = r para cualquier r distinto de cero (porque 0 es divisible por cualquier número entero).

Algoritmo geométrico de Euclides

Sean dados dos segmentos de longitud a y b . Resta el segmento más pequeño del segmento más grande y reemplaza el segmento más grande con la diferencia resultante. Repetimos esta operación, restando el segmento más pequeño del segmento más grande, hasta que los segmentos sean iguales. Si esto sucede, entonces los segmentos originales son conmensurables y el último segmento obtenido es su máxima medida común. Si no hay una medida común, entonces el proceso es infinito. De esta forma, el algoritmo es descrito por Euclid [2] y se implementa utilizando un compás y una regla .

Ejemplo

Para ilustrar, se usará el algoritmo de Euclides para encontrar el mcd a = 1071 y b = 462. Para empezar, restamos un múltiplo de 462 de 1071 hasta obtener una diferencia menor que 462. Debemos restar 462 dos veces, ( q 0 = 2), quedando con un resto de 147:

1071 = 2 × 462 + 147.

Luego a 462 le restamos un múltiplo de 147 hasta obtener una diferencia menor a 147. Debemos restar 147 tres veces ( q 1 = 3), quedando con un resto de 21:

462 = 3x147 + 21.

Luego restamos un múltiplo de 21 de 147 hasta obtener una diferencia menor a 21. Debemos restar 21 siete veces ( q 2 = 7), sin dejar residuo:

147 = 7 x 21 + 0.

Así, la secuencia a > b > r 1 > r 2 > r 3 > ... > r n en este caso particular se verá así:

1071 > 462 > 147 > 21.

Como el último residuo es cero, el algoritmo termina en 21 y mcd(1071, 462) = 21.

En forma tabular, los pasos fueron los siguientes:

paso k	Igualdad	cociente y resto
0	1071 = q 0 462 + r 0	q 0 = 2 y r 0 = 147
una	462 = q 1 147 + r 1	q 1 = 3 y r 1 = 21
2	147 = q 2 21 + r 2	q2 = 7 yr2 = 0 ; finaliza el algoritmo

Si se requiere encontrar el mcd para más de dos números, el algoritmo es similar, en cada paso todos los números excepto el más pequeño son reemplazados por residuos módulo el más pequeño. Los residuos cero, si los hay, se tachan. El algoritmo termina cuando queda un número distinto de cero, este es el GCD.

Aplicaciones

Algoritmo de Euclides extendido y relación de Bezout

Las fórmulas para se pueden reescribir de la siguiente manera: $Rhode Island}$

r_{1}=a+b(-q_{0})

r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})

\vpuntos

MCD

(a,b)=r_{n}=as+bt

Aquí s y t son números enteros. Esta representación del máximo común divisor se denomina razón de Bezout , y los números syt son los coeficientes de Bezout [13] . La relación de Bezout es clave en la demostración del lema de Euclides y del teorema fundamental de la aritmética .

Fracciones continuas

El algoritmo de Euclides está bastante relacionado con las fracciones continuas [6] . La relación a / b se puede representar como una fracción continua:

{\frac{a}{b}}=[q_{0};q_{1},q_{2},\cdots,q_{n}]

En este caso, la fracción continua sin el último término es igual a la razón de los coeficientes de Bezout t / s , tomada con signo menos:

[q_{0};q_{1},q_{2},\cdots,q_{n-1}]=-{\frac {t}{s))

La secuencia de igualdades que define el algoritmo de Euclides se puede reescribir en la forma:

{\begin{alineado}{\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{alineado}}

El último término del lado derecho de una ecuación siempre es igual al recíproco del lado izquierdo de la siguiente ecuación. Por lo tanto, las dos primeras ecuaciones se pueden combinar en la forma:

{\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}

La tercera igualdad se puede usar para reemplazar el denominador de la expresión r 1 / r 0 , obtenemos:

{\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{ r_{1}}}}}}}}

La última razón de residuos r k / r k −1 siempre se puede reemplazar usando la siguiente igualdad en la secuencia, y así sucesivamente hasta la última ecuación. El resultado es una fracción continua:

{\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 anterior, se calculó GCD(1071, 462) y se encontró que los cocientes q k eran 2, 3 y 7 respectivamente. Por lo tanto, 1071/462 se puede escribir como:

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

Ecuaciones diofánticas lineales

Una ecuación diofántica es una ecuación con coeficientes enteros y con una o más variables, y la tarea es encontrar solo sus raíces enteras. Tal ecuación puede tener un número infinito de soluciones, un número finito de soluciones o ninguna. La ecuación diofántica más simple es lineal con dos incógnitas:

$a\cdot x+b\cdot y=c,$

donde a , b , c son números enteros. Utilizando el algoritmo de Euclides, se puede encontrar una solución completa a una ecuación de este tipo [5] . Primero, usando este algoritmo, puedes determinar d = mcd( a , b ). Luego, usando el algoritmo de Euclides extendido, k y l se determinan de tal manera que:

$a\cdot k+b\cdot l=d.$

Es decir, x \u003d k y y \u003d l es una solución particular de la ecuación para c \u003d d . Resulta que si c = q⋅d , entonces x = q⋅k , y = q⋅l es una solución particular de la ecuación original, ya que:

$a\cdot x+b\cdot y=a\cdot (q\cdot k)+b\cdot (q\cdot l)=q\cdot (a\cdot k+b\cdot l)=q\cdot d= C.$

Por el contrario, si hay al menos una solución a la ecuación, entonces c es un múltiplo de d . Esto se deriva del hecho de que d divide tanto a a como a b (y, por lo tanto, todo el lado izquierdo), por lo que también debe dividir a c (el lado derecho). Por lo tanto, una ecuación diofántica lineal tiene al menos una solución si y solo si c es un múltiplo de mcd( a , b ).

Variaciones y generalizaciones

Anillo euclidiano

Los anillos en los que se aplica el algoritmo euclidiano se denominan anillos euclidianos [14] . Estos incluyen, en particular, anillos de números enteros y anillos de polinomios .

Algoritmo de Euclides generalizado para polinomios

El algoritmo de Euclides y el algoritmo de Euclides extendido se generalizan naturalmente al anillo de polinomios k [ x ] en una variable sobre un campo arbitrario k , ya que la división con resto está definida para tales polinomios. Al ejecutar el algoritmo de Euclid para polinomios, de manera similar al algoritmo de Euclid para enteros, se obtiene una secuencia residual polinomial (PRS) [15] .

Ejemplo de anillo Z [ x ]

Sea cont(f) por definición el mcd de los coeficientes del polinomio a partir del contenido del polinomio. El cociente de dividir f(x) por cont(f) se denomina parte primitiva del polinomio f(x) y se denota primpart(f(x)). Estas definiciones serán necesarias para encontrar el MCD de dos polinomios p 1 (x) y p 2 (x) en el anillo . Para polinomios sobre enteros, se cumple lo siguiente: $f(x)$ ${\ estilo de visualización Z [x]}$ ${\ estilo de visualización Z [x]}$

$continua($ asentir asentir $\{p_{1}(x),p_{2}(x)\})=$ $\{cont(p_{1}(x)),cont(p_{2}(x))\},$

$primogénito($ asentir asentir $\{p_{1}(x),p_{2}(x)\})=$ $\{primpart(p_{1}(x)),primpart(p_{2}(x))\}.$

Así, el problema de encontrar el mcd de dos polinomios arbitrarios se reduce al problema de encontrar el mcd de polinomios primitivos.

Sean dos polinomios primitivos p 1 (x) y p 2 (x) de Z[x] para los cuales se satisface la relación entre sus potencias: grado(p 1 (x)) = m y grado(p 2 (x) ) = norte, metro > norte. La división de polinomios con resto implica la divisibilidad exacta del mayor coeficiente del dividendo por el mayor coeficiente del divisor, en el caso general no se puede realizar la división con resto. Por lo tanto, se introduce un algoritmo de pseudodivisión que, sin embargo, permite obtener un pseudocociente y un pseudoresto (prem), que a su vez pertenecerán al conjunto de polinomios sobre números enteros.

Por pseudo-división queremos decir que la división misma está precedida por la multiplicación del polinomio por , es decir $p_{1}(x)$ $(lc(p_{2}(x)))^{m-n+1}$

$lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\grado(r (x))<\grado(p_{2}(x)),$

donde y son el pseudoparcial y el pseudoresiduo, respectivamente. $q(x)$ $r(x)$

Así, y además . Entonces el algoritmo de Euclides consta de los siguientes pasos: $p_{1}(x),p_{2}(x)\en Z[x]$ $\grado(p_{1})=n_{1}\geq \grado(p_{2})=n_{2}$

1. Cálculo del contenido de GCD:

$do:=$ GCD . $\{cont(p_{1}),cont(p_{2})\}$

2. Cálculo de partes primitivas:

$p_{1}'(x):=primpart(p_{1}(x));$

$p_{2}'(x):=primpart(p_{2}(x)).$

3. Construcción de una secuencia de residuos polinómicos:

$p_{1}'(x),$

$p_{2}'(x),$

$p_{3}(x):=prem(p_{1}'(x),p_{2}'(x)),$

$p_{4}(x):=prem(p_{2}'(x),p_{3}(x)),$

$p_{5}(x):=prem(p_{3}(x),p_{4}(x)),$

$...$

$p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).$

4. Resultado devuelto:

Si , entonces regresa , de lo contrario regresa . $\grado(p_{h}(x))=0$ $C$ $c\cdot primpart(p_{h}(x))$

Versiones aceleradas del algoritmo

Uno de los métodos para acelerar el algoritmo entero de Euclides es usar el resto simétrico [16] :

r_{i}\equiv r_{i-2}{\pmod {r_{i-1}}},

dónde

-{\frac {r_{i-1}}{2}}\leq r_{i}\leq {\frac {r_{i-1}}{2}}.

Una versión del algoritmo de Euclides acelerado para polinomios se basa en el hecho de que los valores intermedios del algoritmo dependen principalmente de potencias altas. La aplicación de la estrategia de " divide y vencerás " permite reducir la complejidad asintótica del algoritmo [16] .

Complejidad computacional del algoritmo

La complejidad computacional del algoritmo de Euclides ha sido completamente estudiada. [17] Esta complejidad se puede describir como el producto del número de pasos de división requeridos por el algoritmo por la complejidad computacional de un paso. El primer análisis conocido del algoritmo de Euclides fue propuesto por Reinaud en 1811. [18] Demostró que el número de pasos del algoritmo para un par de números ( u , v ) está limitado a v . Más tarde mejoró el límite a v / 2 + 2. Émile Léger, en 1837, estudió el peor de los casos, cuando se introducen números de Fibonacci sucesivos para calcular el gcd . [19] Luego, en 1841, Pierre Joseph Fink demostró [20] que el número de pasos del algoritmo no excede 2 log 2 v + 1. Por lo tanto, el algoritmo se ejecuta en tiempo polinomial en el tamaño del menor del par de números ( u , v ). [19] El análisis de Fink fue refinado por Gabriel Lame en 1844. [21] Demostró que el número de pasos requeridos para completar el algoritmo no es más de cinco veces h , el número de dígitos en la representación decimal del menor del par de números ( u , v ). [22] [23]

Cuando GCD se calcula para números que caben en una palabra de máquina , cada paso del algoritmo lleva un tiempo constante. En este caso, el análisis de Lame sugiere que la complejidad computacional se estima en O ( h ). Sin embargo, en un modelo de cálculo adecuado para cálculos con números mayores que una palabra de máquina, la estimación de la complejidad de calcular un resto puede ser O ( h 2 ). [24] En este caso, el tiempo total para todos los pasos del algoritmo se puede analizar usando la serie telescópica , mostrando que también es O ( h 2 ). Para acelerar el algoritmo de Euclides, se pueden utilizar métodos algorítmicos modernos basados en el método de Schönhage-Strassen para la multiplicación rápida de enteros. Esto conduce a un tiempo cuasi-polinomial . [25]

Número de pasos

El número de pasos para calcular el mcd de dos números naturales a y b se denota como T ( a , b ). Si g es el máximo común divisor de a y b , entonces a = mg y b = ng para dos números coprimos m y n . Entonces T ( a , b ) = T ( m , n ) , lo cual se puede ver si dividimos las ecuaciones obtenidas al calcular el mcd del par ( a , b ) por g . [26] Usando el mismo principio, el número de pasos del algoritmo permanece sin cambios si a y b se multiplican por un factor común w , que es equivalente a T ( a , b ) = T ( wa , wb ). Por lo tanto, el número de pasos T puede variar mucho entre pares de números adyacentes, como ( a , b ) y ( a , b+1 ), ya que este valor depende del gcd.

La naturaleza recursiva del algoritmo de Euclides da la siguiente ecuación T ( a , 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 suposición. [17]

En el 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 a y b para los que esto se cumple son los números de Fibonacci F N +2 y F N +1 , respectivamente. [27] Entonces, si el algoritmo de Euclides requiere N pasos para un par de números ( a , b ), donde a > b , se cumplen las siguientes desigualdades a ≥ F N +2 yb ≥ F N +1 . Esto se puede demostrar por inducción matemática . Si N = 1, entonces a es divisible por b sin resto. Los números naturales más pequeños para los que esto es cierto son b = 1 y a = 2, respectivamente F 2 y F 3 . Supongamos ahora que el resultado se cumple para todos los valores de N hasta M − 1. El primer paso del algoritmo euclidiano con M pasos es a = q 0 b + r 0 , y el algoritmo euclidiano para el par de números ( b , r 0 ), donde b > r 0 , requiere M − 1 pasos. Por la hipótesis de inducción, tenemos 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 requerida. Esta prueba, publicada por Gabriel Lame en 1844, representa el comienzo de la teoría de la complejidad computacional , [28] y también la primera aplicación práctica de los números de Fibonacci . [27]

Teorema de Lame

El número de divisiones con resto en el proceso de aplicación del algoritmo de Euclides no excede de cinco veces el número de dígitos de un número menor escrito en sistema decimal [29] . $b$

Promedio

Hay varias formas de calcular el número promedio de pasos en un algoritmo. El primer método de cálculo 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 , elegidos con igual probabilidad entre números enteros de 0 a a − 1. [17]

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

Sin embargo, dado que T ( a , b ) fluctúa mucho con el mcd de los dos números, la función promediada T ( a ) también es ruidosa. [30] Para reducir este ruido, se toma un segundo promedio τ ( a ) sobre todos los números relativamente primos a a .

\tau (a)={\frac {1}{\varphi (a)))\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\ extremo {matriz pequeña}} T (a, b)

donde φ ( a ) es la función de Euler . Este promedio crece suavemente a medida que aumenta . [31]

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

La constante (constante de Porter [32] ) en esta fórmula es , y ε es infinitesimal . ${\ estilo de visualización C \ aproximadamente 1,467}$

La tercera media Y ( n ) se define como el número promedio de pasos requeridos cuando ayb se eligen aleatoriamente ( distribuidos uniformemente ) de 1 a n .

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

Complejidad computacional de un paso

En cada paso del algoritmo euclidiano, el coeficiente q k y el resto r k se calculan para un par dado de números enteros r k −2 y r k −1 . Estas cantidades están relacionadas por la siguiente relación:

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

La complejidad computacional de cada paso se relaciona principalmente con encontrar q k , ya que el resto r k se puede calcular rápidamente usando r k −2 , r k −1 y q k

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

La complejidad computacional de la operación de dividir números de tamaño h bits se estima como O ( h ( ℓ +1)), donde ℓ es el tamaño del cociente. [24]

En comparación, el algoritmo de Euclides original, que utiliza la resta, puede ser mucho más lento. En la mayoría de los casos, el coeficiente q k es un número pequeño. La probabilidad de un cociente q dado es aproximadamente igual a ln| tu /( tu − 1)|, donde tu = ( q + 1) 2 . [33] Para ilustrar, la probabilidad de un cociente 1, 2, 3 o 4 es aproximadamente 41,5 %, 17,0 %, 9,3 % y 5,9 %, respectivamente. Dado que la resta es más rápida que la división, especialmente para números mayores de una palabra, [34] el algoritmo de Euclides que usa la resta puede ser más competitivo que el algoritmo que usa la división. [35] Esto se usa en el algoritmo binario para calcular gcd . [36]

La estimación de complejidad del algoritmo se calcula como el producto del número de pasos y el tiempo que lleva completar un paso. Muestra que el algoritmo de Euclides crece cuadráticamente O ( h 2 ), donde h es el número promedio de dígitos en los dos números iniciales a y b en notación decimal. Sea h 0 , h 1 , …, h N −1 el número de dígitos en residuos consecutivos r 0 , r 1 , …, r N −1 . Dado que el número de pasos N crece linealmente con h , el tiempo de ejecución está limitado por la siguiente expresión:

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

Notas

↑ 1 2 Mordukhai-Boltovskoy, 1949 , p. 11-13.
↑ 1 2 3 Mordukhai-Boltovskoy, 1949 , p. 103-105.
↑ 1 2 Knuth, 2001 , pág. 378.
↑ Menezes, 1996 , pág. 286.
↑ 12 Courant , 2001 , p. 74-76.
↑ 1 2 Vinogradov, 1952 , p. 14-18.
↑ Engeler, 1987 , pág. 24-31.
↑ Tikhomirov, 2003 , pág. 11-14.
↑ Kaluzhin, 1969 , pág. 6-14.
↑ Zeiten, 1932 , pág. 112-114.
↑ Vinogradov, 1952 , pág. 9-10.
↑ Courant, 2001 , pág. 67-70.
↑ Hasse, 1953 , pág. 29-30.
↑ Kurosh, 1973 , pág. 91-92.
↑ Pankratiev, 2007 , pág. 54-58.
↑ 12 Gathen , 2013 , pág. 313-326.
↑ 1 2 3 Knuth, 1997 , pág. 344.
↑ Shalit, 1994 , pág. 414.
↑ 1 2 Shalit, 1994 , pág. 401-419.
↑ Shalit, 1994 , pág. 413.
↑ Cojo, 1844 , pág. 867-870.
↑ Grossman, 1924 , pág. 443.
↑ Abramov S. A. Construcciones matemáticas y programación. - M., Nauka , 1978. - Circulación 100.000 ejemplares. - C. 170
↑ 1 2 Knuth, 1997 , pág. 257-261.
↑ Möller, 2005 , pág. una.
↑ Mineral, 1948 , pág. 45.
↑ 1 2 Knuth, 1997 , pág. 343.
↑ LeVeque, 1996 , pág. 3.
↑ Abramov S. A. Construcciones matemáticas y programación. - M., Nauka, 1978. - Circulación 100.000 ejemplares. - C. 170
↑ Knuth, 1997 , pág. 353.
↑ Tonkov, 1974 , pág. 47-57.
↑ Weisstein, Eric W. Porter's Constant en el sitio web de Wolfram MathWorld .
↑ Knuth, 1997 , pág. 352.
↑ Vagón, 1999 , p. 335-336.
↑ Cohen, 1993 , pág. catorce.
↑ Cohen, 1993 , pág. 14-15, 17-18.

Literatura

Abramov S. A. El algoritmo más famoso // Kvant / ed. A. L. Semenov , A. A. Gaifullin - MIAN , 1985. - vol. 11. - S. 44-46. — ISSN 0130-2221
Vinogradov I.M. Fundamentos de la teoría de números . - M. - L. : GITTL, 1952. - 180 p. - ISBN 978-5-811-40535-0 .
Kaluzhin L. A. El teorema fundamental de la aritmética. — Conferencias Populares de Matemáticas . - M. : Nauka, 1969. - 33 p.
Knut D. E. El arte de la programación. - Williams, 2001. - T. 2. - 829 p. — ISBN 5-8459-0081-6 .
Courant R., Robbins G. Suplemento del Capítulo I, § 4. // ¿Qué son las matemáticas? - 3ra ed., rev. y adicional - M. , 2001. - 568 p. - ISBN 5-900916-45-6 .
Kurosh A. G. Conferencias sobre álgebra general / ed. ON Golovin - 2ª ed. — M .: Nauka , 1973. — 400 p. — ISBN 978-5-8114-0617-3
Comienzos de Euclides / traducido del griego. y com. D. D. Mordukhai-Boltovsky, ed. Vygodsky M. Ya. y Veselovsky I. N. - GITTL, 1949. - T. 2. - 511 p.
Pankratiev EV Elementos de álgebra informática. - INTUIT, 2007. - 217 p. - ISBN 978-5-955-60099-4 .
Tikhomirov VM Grandes matemáticos del pasado y sus grandes teoremas. — 2ª ed., corregida. - MTsNMO , 2003. - 16 p. — ISBN 5-94057-110-7 .
Hasse G. Conferencias sobre teoría de números. - Ed. literatura extranjera, 1953. - 527 p.
Zeiten GG Historia de las matemáticas en la Antigüedad y en la Edad Media. - GTTI, 1932. - 232 p.
Engeler E. Metamatemáticas de las matemáticas elementales. — M .: Mir, 1987. — 128 p.
Cohen H. Un curso de teoría de números algebraicos computacionales . - Springer-Verlag, 1993. - ISBN 0-387-55640-0 .
von zur Gathen J., Gerhard J. Álgebra informática moderna . - Cambridge University Press, 2013. - 808 p. — ISBN 978-1-107-03903-2 .
Grossman H. Sobre el número de divisiones para encontrar un GCD // The American Mathematical Monthly. - 1924. - Vol. 31 , edición. 9 _ - Pág. 443 . -doi : 10.2307/ 2298146 . — .
Knuth D. E. El arte de la programación informática . - 3. - Addison-Wesley, 1997. - V. 2: Algoritmos Semiméricos. — ISBN 0-201-89684-2 .
Lamé G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers (francés) . Comptes Rendus Acad. Sci., 1844. - No. 19 .
LeVeque WJ Fundamentos de la teoría de números (inglés) . - Dover, 1996. - ISBN 0-486-68906-9 .
Menezes A., van Oorschot P., Vanstone S. Manual de criptografía aplicada. - CRC-Prensa, 1996. - 816 p. - (Matemáticas Discretas y sus Aplicaciones). - ISBN 0-8493-8523-7 .
Möller Niels. Matemáticas de la Computación (Inglés) . — 2005.
Ore O. Teoría de números y su historia (inglés) . — McGraw–Hill, 1948.
Shallit J. Orígenes del análisis del algoritmo euclidiano (inglés) // Historia Math.. - 1994. - vol. 21 . -doi : 10.1006/ hmat.1994.1031 .
Tonkov T. Sobre la longitud promedio de fracciones continuas finitas (inglés) // Acta Arithmetica. - 1974. - vol. 26 .
Wagon S. Mathematica en Acción . - Springer-Verlag, 1999. - ISBN 0-387-98252-3 .

Enlaces

Implementación del algoritmo de Euclides en Pascal

diccionarios y enciclopedias	Gran danés gran noruego gran ruso croata Britannica (en línea) Brockhaus
En catálogos bibliográficos	TIERRA : 4659898-4