algoritmo euclidiano

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

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

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

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

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

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

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

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

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

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

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

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

La existencia de un paso${\displaystyle N}$de tal manera que${\displaystyle r_{N}=0}$Se deduce de la condición${\displaystyle |r_{i}|<|r_{i-1}|}$, para${\displaystyle i\geq 1}$Esto garantiza que el algoritmo finalice.

El último resto distinto de cero${\displaystyle r_{N-1}}$ser igual a${\displaystyle \gcd(a,b)}$Se deduce de las siguientes propiedades de${\displaystyle \gcd }$

1.${\displaystyle \gcd(x,0)=x}$, para todos${\displaystyle x\neq 0}$.

De hecho, los divisores comunes de${\displaystyle x}$y${\displaystyle 0}$son exactamente todos los divisores de${\displaystyle x}$, de los cuales${\displaystyle x}$es el más grande.

2.${\displaystyle \gcd(x,y)=\gcd(y,x-zy)}$

De hecho, los conjuntos de divisores comunes de los pares${\displaystyle (x,y)}$y${\displaystyle (y,x-zy)}$son iguales. En particular, el mayor de sus divisores comunes es el mismo.

Para ver esto, supongamos que${\displaystyle d}$es un divisor común de${\displaystyle x}$y${\displaystyle y}$Esto significa que hay números enteros.${\displaystyle X,Y}$de tal manera que${\displaystyle x=dX}$y${\displaystyle y=dY}$De ello se deduce que${\displaystyle x-zy=dX-zdY=d(X-zY)}$, dónde${\displaystyle X-zY}$es un número entero. Por lo tanto,${\displaystyle d}$también es un divisor de${\displaystyle x-zy}$.

Por el contrario, si${\displaystyle d}$es un divisor común de${\displaystyle x-zy}$y${\displaystyle y}$, entonces hay números enteros${\displaystyle Z}$y${\displaystyle Y}$de tal manera que${\displaystyle x-zy=dZ}$y${\displaystyle y=dY}$. Desde este${\displaystyle x=(x-zy)+zy=dZ+zdY=d(Z+zY)}$, dónde${\displaystyle Z+zY}$es un número entero. Por lo tanto,${\displaystyle d}$es también un divisor común de${\displaystyle x}$y${\displaystyle y}$.

Ahora, el algoritmo euclidiano comienza con el par${\displaystyle (r_{-2},r_{-1})=(a,b)}$y en cada paso, el par de restos${\displaystyle (r_{k-2},r_{k-1})}$es reemplazado por${\displaystyle (r_{k-1},r_{k-2}-q_{k}r_{k-1})=(r_{k-1},r_{k})}$La propiedad 2 muestra que el${\displaystyle \gcd }$de los pares permanece invariable. En particular, el${\displaystyle \gcd }$del primer par${\displaystyle (a,b)}$y el último par${\displaystyle (r_{N-1},0)}$son lo mismo. Aplicando la propiedad 1,${\displaystyle \gcd(a,b)=\gcd(r_{N-1},0)=r_{N-1}}$.

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

1071 = 2 × 462 + 147 .

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

462 = 3 × 147 + 21 .

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

147 = 7 × 21 + 0 .

Dado que el último resto es cero, el algoritmo termina con 21 como máximo común divisor de 1071 y 462. Esto coincide con el mcd(1071, 462) hallado mediante la factorización prima anterior . En forma tabular, los pasos son:

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

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

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

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

En la versión original del algoritmo de Euclides, el cociente y el resto se obtienen mediante restas repetidas; es decir, se resta r _{k −1 de} r _{k −2} repetidamente hasta que el resto r _k sea menor que r _{k −1} . Después, se intercambian r _k y r _{k −1} y se repite el proceso. La división euclidiana reduce todos los pasos entre dos intercambios a un solo paso, lo que resulta más eficiente. Además, no se necesitan los cocientes, por lo que se puede reemplazar la división euclidiana por la operación módulo , que solo proporciona el resto. De este modo, la iteración del algoritmo euclidiano se simplifica.

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

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

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

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 predecesor, r _{k −2} . El paso b  := a mod b es equivalente a la fórmula de recursión anterior r _k ≡ r _{k −2} mod r _{k −1} . La variable temporal t contiene el valor de r _{k −1} mientras se calcula el siguiente resto r _k . Al final de la iteración del bucle, la variable b contiene el resto r _k , mientras que la variable a contiene su predecesor, r _{k −1} .

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

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

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

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

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

función mcd(a, b) si b = 0 devuelve a sino devuelve mcd(b, a mod b)

(Como se indicó anteriormente, si se permiten entradas negativas o si la modfunción puede devolver valores negativos, la instrucción return adebe reemplazarse por return max(a, −a).)

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

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

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

Se supuso 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 el menor número de pasos de cualquier versión del algoritmo de Euclides. ^{[ 21 ] [ 22 ]} De manera más general, se ha demostrado que, para cada número de entrada a y b , el número de pasos es mínimo si y solo si q _k se elige de manera que${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$dónde${\displaystyle \varphi }$es la proporción áurea . ^{[ 23 ]}

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

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

g = r _{N −1} = r _{N −3} − q _{N −1} r _{N −2} .

Esos dos restos pueden expresarse igualmente en términos de sus cocientes y restos 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 restos r _{N −4} y r _{N −5} . El proceso de sustitución de restos por fórmulas que involucran a sus predecesores puede continuarse hasta alcanzar los números originales a y b :

r ₂ = r ₀ − q ₂ r ₁

r ₁ = b − q ₁ r ₀

r ₀ = a − q ₀ b .

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

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

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

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 sumas posibles de múltiplos enteros de dos números ( a y b ) es equivalente al conjunto de múltiplos de mcd( a , b ) . Se dice que el MCD es el generador del ideal de a y b . Esta definición de MCD dio origen a los conceptos algebraicos abstractos modernos de ideal principal (un ideal generado por un solo elemento) y dominio de ideales principales (un dominio en el que todo ideal es un ideal principal).

Ciertos problemas pueden resolverse utilizando este resultado. ^{[ 57 ]} Por ejemplo, consideremos dos vasos medidores de volumen a y b . Al sumar/restar u múltiplos del primer vaso y v múltiplos del segundo, se puede medir cualquier volumen ua + vb . Todos estos volúmenes son múltiplos de g = mcd( a , b ) .

Los enteros s y t de la identidad de Bézout se pueden calcular eficientemente utilizando el algoritmo euclidiano extendido . Esta extensión añade dos ecuaciones recursivas al algoritmo de Euclides ^{[ 58 ].}

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

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

con los valores iniciales

s ₋₂ = 1, t ₋₂ = 0

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

Utilizando esta recursión, los enteros de Bézout s y t vienen 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. Supongamos que la fórmula de recursión es correcta hasta el paso k − 1 del algoritmo; en otras palabras, supongamos que

r _j = s _j a + t _j b

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

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

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

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

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

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

Los enteros s y t también se pueden encontrar utilizando un método matricial equivalente . ^{[ 59 ]} La secuencia de ecuaciones del algoritmo de Euclides

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

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

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

Sea M el producto de todas las matrices cociente.

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

Esto simplifica el algoritmo euclidiano a la forma

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

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

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

Dado que la ecuación superior da

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

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

La identidad de Bézout es esencial para muchas aplicaciones del algoritmo de Euclides, como demostrar la factorización única de números en factores primos. ^{[ 61 ]} Para ilustrar esto, supongamos 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 a L pero es coprimo con u , entonces w debe dividir a v , por el siguiente argumento: Si el máximo común divisor de u y w es 1 , entonces se pueden encontrar enteros s y t tales que

1 = su + tw

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

v = suv + twv = sL + twv

Dado que w divide a ambos términos del lado derecho, también debe dividir al lado izquierdo, v . Este resultado se conoce como el lema de Euclides . ^{[ 62 ]} Específicamente, si un número primo divide a L , entonces debe dividir al menos un factor de L. Recíprocamente, si un número w es coprimo con cada uno de una serie de números _a₁ , a₂ _, ... , aₙ _, entonces w también es coprimo con su producto ^, a₁ _× a₂ _× ... ^× aₙ _. [ ⁶² ]

El lema de Euclides basta para demostrar que todo número tiene una única factorización en números primos. ^{[ 63 ]} Para ver esto, supongamos lo contrario, que existen dos factorizaciones independientes de L en m y n factores primos, respectivamente.

L = p ₁ p ₂ ... p _m = q ₁ q ₂ ... q _n  .

Dado que cada número primo p divide a L por hipótesis, también debe dividir a uno de los q factores; y como cada q también es primo, entonces p = q . Dividiendo iterativamente por los p factores se demuestra que cada p tiene un equivalente q ; las dos factorizaciones primas son idénticas, salvo por su orden. La factorización única de números en primos tiene numerosas aplicaciones en demostraciones matemáticas, como se muestra a continuación.

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

ax + by = c

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

ax ≡ c mod b .

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

sa + tb = g ,

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

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

ax ₁ + by ₁ = c = ax ₂ + by ₂

o equivalentemente

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

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

x = x ₁ − bu / g

y = y ₁ + au / g .

Al permitir que u varíe sobre todos los enteros posibles, se puede generar una familia infinita de soluciones a partir de una única solución ( x ₁ , y ₁ ) . Si se requiere que las soluciones sean 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; ^{[ 68 ]} esto es imposible para un sistema de ecuaciones lineales cuando las soluciones pueden ser cualquier número real (véase Sistema subdeterminado ).

Un cuerpo finito es un conjunto de números con cuatro operaciones generalizadas. Estas operaciones se denominan suma, resta, multiplicación y división, y poseen sus propiedades habituales, como la conmutatividad , la asociatividad y la distributividad . Un ejemplo de cuerpo finito es el conjunto de 13 números {0,  1,  2,  ...,  12} mediante aritmética modular . En este cuerpo, los resultados de cualquier operación matemática (suma, resta, multiplicación o división) se reducen módulo 13 ; es decir, se suman o restan múltiplos de 13 hasta que el resultado se encuentra dentro del rango 0 – 12. Por ejemplo, el resultado de 5 × 7 = 35 mod 13 = 9. Dichos cuerpos finitos pueden definirse para cualquier primo p ; utilizando definiciones más sofisticadas, también pueden definirse para cualquier potencia m de un primo p ^m . Los 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 no nulo a tiene un inverso multiplicativo modular único , a ⁻¹ tal que aa ⁻¹ = a ⁻¹ a ≡ 1 mod m . Este inverso se puede encontrar resolviendo la ecuación de congruencia ax ≡ 1 mod m , ^{[ 69 ]} o la ecuación diofántica lineal equivalente ^{[ 70 ].}

ax + mi = 1 .

Esta ecuación se puede resolver mediante el algoritmo euclidiano, como se describió anteriormente . Encontrar inversos multiplicativos es un paso esencial en el algoritmo RSA , ampliamente utilizado en el comercio electrónico ; específicamente, la ecuación determina el entero utilizado para descifrar el mensaje. ^{[ 71 ]} Aunque el algoritmo RSA utiliza anillos en lugar de cuerpos, el algoritmo euclidiano aún se puede usar para encontrar un inverso multiplicativo cuando existe. El algoritmo euclidiano también tiene otras aplicaciones en códigos correctores de errores ; por ejemplo, se puede usar como alternativa al algoritmo Berlekamp-Massey para decodificar códigos BCH y Reed-Solomon , que se basan en cuerpos de Galois. ^{[ 72 ]}

El algoritmo de Euclides también puede utilizarse para resolver múltiples ecuaciones diofánticas lineales. ^{[ 73 ]} Dichas ecuaciones surgen en el teorema chino del resto , que describe un método novedoso para representar un entero x . En lugar de representar un entero por sus dígitos, puede representarse por sus restos x _i módulo un conjunto de N números coprimos m _i : ^{[ 74 ]}

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

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

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

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

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

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

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

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

El algoritmo euclidiano se puede utilizar para organizar el conjunto de todos los números racionales positivos en un árbol de búsqueda binaria infinito , llamado árbol de Stern-Brocot . El número 1 (expresado como 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 la que cada paso reemplaza el mayor de los dos números dados por su diferencia con el menor (no por 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 su mínima expresión, y forma un camino desde la raíz hasta un nodo que contiene el número a / b . ^{[ 75 ]} Este hecho puede usarse para demostrar que cada número racional positivo aparece exactamente una vez en este árbol.

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

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

El algoritmo euclidiano guarda una relación casi idéntica con otro árbol binario sobre los números racionales llamado árbol de Calkin-Wilf . La diferencia radica en que el camino se invierte: en lugar de generar un camino desde la raíz del árbol hasta un destino, genera un camino desde el destino hasta la raíz.

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

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

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

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

La tercera ecuación puede usarse para sustituir el término del denominador r ₁ / r ₀ , obteniendo:

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

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

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

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

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

como puede confirmarse mediante cálculos.

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

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

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

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

La naturaleza recursiva del algoritmo euclidiano da lugar a otra ecuación.

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

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

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

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

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

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

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

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

La combinación del número estimado de pasos con el costo computacional estimado por paso muestra que el algoritmo de Euclides crece cuadráticamente ( ^h² ) _con el número promedio de dígitos h en _los dos números iniciales a y b . Sea h₀ , h₁ _, ..., hN⁻¹ el número de dígitos en los restos sucesivos r₀ _, r₁ _, ... , rN⁻¹ . Dado que el número de pasos _{N crece} linealmente con h , el tiempo _de ejecución está acotado por

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

El algoritmo de Euclides se utiliza ampliamente en la práctica, especialmente para números pequeños, debido a su simplicidad. ^{[ 115 ]} Para comparar, se puede determinar la eficiencia de alternativas al algoritmo de Euclides.

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

El algoritmo binario MCD es una alternativa eficiente que sustituye la división con operaciones más rápidas al explotar la representación binaria utilizada por las computadoras. ^{[ 116 ] [ 117 ]} 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. ^{[ 91 ]} Se puede obtener eficiencia adicional examinando solo los dígitos principales de los dos números a y b . ^{[ 118 ] [ 119 ]} El algoritmo binario se puede extender a otras bases ( algoritmos k -arios), ^{[ 120 ]} con aumentos de velocidad de hasta cinco veces. ^{[ 121 ]} El algoritmo MCD de Lehmer utiliza el mismo principio general que el algoritmo binario para acelerar los cálculos de MCD en bases arbitrarias.

Un enfoque recursivo para enteros muy grandes (con más de 25 000 dígitos) conduce a algoritmos cuasilineales de MCD entero, ^{[ 122 ]} como los de Schönhage, ^{[ 123 ] [ 124 ]} y Stehlé y Zimmermann. ^{[ 125 ]} Estos algoritmos explotan la forma matricial 2×2 del algoritmo euclidiano dado anteriormente . Estos métodos cuasilineales generalmente escalan como O ( h log h ² log log h ). ^{[ 91 ] [ 92 ]}

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

El algoritmo euclidiano para números reales difiere de su contraparte para números enteros en dos aspectos. Primero, los restos r _k son números reales, aunque los cocientes q _k son enteros como antes. Segundo, no se garantiza que el algoritmo termine en un número finito N de pasos. Si lo hace, la fracción a / b es un número racional, es decir, la razón de dos enteros.

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

y puede escribirse como una fracción continua finita [ q ₀ ; q ₁ , q ₂ , ..., q _N ] . Si el algoritmo no se detiene, la fracción a / b es un número irracional y puede describirse mediante una fracción continua infinita [ q ₀ ; q ₁ , q ₂ , …] . ^{[ 131 ]} Ejemplos de fracciones continuas infinitas son la razón áurea φ = [1; 1, 1, ...] y la raíz cuadrada de dos , √ 2 = [1; 2, 2, ...] . ^{[ 132 ]} Cuando se aplica a dos números reales arbitrarios, es improbable que el algoritmo se detenga, ya que casi todas las razones a / b de dos números reales son irracionales. ^{[ 133 ]}

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

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

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

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

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 los enteros. El máximo común divisor g ( x ) de dos polinomios a ( x ) y b ( x ) se define como el producto de sus polinomios irreducibles comunes, que se pueden identificar utilizando el algoritmo euclidiano. ^{[ 126 ]} El procedimiento básico es similar al de los enteros. En cada paso k , se identifica un polinomio cociente qk ( x ) y un _polinomio resto rk ( x ) para satisfacer la ecuación recursiva _.

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

donde r ₋₂ ( x ) = a ( x ) y r ₋₁ ( x ) = b ( x ) . Cada polinomio cociente se elige de tal manera 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 entero no negativo y disminuye con cada paso, el algoritmo euclidiano concluye en un número finito de pasos. El último resto no nulo es el máximo común divisor de los dos polinomios originales, a ( x ) y b ( x ) . ^{[ 135 ]}

Por ejemplo, consideremos los siguientes dos polinomios de cuarto grado, cada uno de los cuales se factoriza en dos polinomios de cuarto grado.

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