Algoritmo euclidiano extendido

Método para calcular la relación de dos números enteros con su máximo común divisor

En aritmética y programación informática , el algoritmo euclidiano extendido es una extensión del algoritmo euclidiano , y calcula, además del máximo común divisor (mcd) de los números enteros a y b , también los coeficientes de identidad de Bézout , que son los números enteros x e y. tal que

${\displaystyle ax+by=\gcd(a,b).}$

Este es un algoritmo de certificación , porque el mcd es el único número que puede satisfacer esta ecuación y dividir las entradas simultáneamente. Permite calcular también, casi sin coste adicional, los cocientes de a y b por su máximo común divisor.

El algoritmo euclidiano extendido también se refiere a un algoritmo muy similar para calcular el máximo común divisor del polinomio y los coeficientes de identidad de Bézout de dos polinomios univariados .

El algoritmo euclidiano extendido es particularmente útil cuando a y b son coprimos . Con esa disposición, x es el inverso multiplicativo modular de a módulo b , e y es el inverso multiplicativo modular de b módulo a . De manera similar, el algoritmo euclidiano extendido polinómico permite calcular el inverso multiplicativo en extensiones de campos algebraicos y, en particular, en campos finitos de orden no primo. De ello se deduce que ambos algoritmos euclidianos extendidos se utilizan ampliamente en criptografía . En particular, el cálculo del inverso multiplicativo modular es un paso esencial en la derivación de pares de claves en el método de cifrado de clave pública RSA .

Descripción

El algoritmo euclidiano estándar procede de una sucesión de divisiones euclidianas cuyos cocientes no se utilizan. Sólo se conservan los restos . Para el algoritmo extendido se utilizan los cocientes sucesivos. Más precisamente, el algoritmo euclidiano estándar con a y b como entrada, consiste en calcular una secuencia de cocientes y una secuencia de restos tales que ${\displaystyle q_{1},\ldots ,q_{k}}$ ${\displaystyle r_{0},\ldots ,r_{k+1}}$

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned}}}$

La propiedad principal de la división euclidiana es que las desigualdades de la derecha se definen de forma única y desde y hacia la derecha. ${\displaystyle q_{i}}$ ${\displaystyle r_{i+1}}$ ${\displaystyle r_{i-1}}$ ${\displaystyle r_{i}.}$

El cálculo se detiene cuando se llega a un resto que es cero; el máximo común divisor es entonces el último resto distinto de cero ${\displaystyle r_{k+1}}$ ${\displaystyle r_{k}.}$

El algoritmo euclidiano extendido procede de manera similar, pero agrega otras dos secuencias, como sigue

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}}$

El cálculo también se detiene cuando y da ${\displaystyle r_{k+1}=0}$

• ${\displaystyle r_{k}}$es el máximo común divisor de la entrada y ${\displaystyle a=r_{0}}$ ${\displaystyle b=r_{1}.}$
• Los coeficientes de Bézout son y es decir ${\displaystyle s_{k}}$ ${\displaystyle t_{k},}$ ${\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
• Los cocientes de a y b por su máximo común divisor están dados por y ${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}$ ${\displaystyle t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}}$

Además, si a y b son ambos positivos y , entonces ${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor }$

porque donde denota la parte integral de x , es decir el mayor entero no mayor que x . ${\displaystyle 0\leq i\leq k,}$ ${\displaystyle \lfloor x\rfloor }$

Esto implica que el par de coeficientes de Bézout proporcionado por el algoritmo euclidiano extendido es el par mínimo de coeficientes de Bézout, por ser el par único que satisface las dos desigualdades anteriores.

También significa que el algoritmo se puede realizar sin desbordamiento de enteros mediante un programa de computadora utilizando números enteros de un tamaño fijo que sea mayor que el de a y b .

Ejemplo

La siguiente tabla muestra cómo procede el algoritmo euclidiano extendido con las entradas 240 y 46 . El máximo común divisor es la última entrada distinta de cero, 2 en la columna "resto". El cálculo se detiene en la fila 6, porque el resto es 0 . Los coeficientes de Bézout aparecen en las dos últimas entradas de la penúltima fila. De hecho, es fácil comprobar que −9 × 240 + 47 × 46 = 2 . Finalmente las dos últimas entradas 23 y −120 de la última fila son, hasta el signo, los cocientes de la entrada 46 y 240 por el máximo común divisor 2 .

Prueba

Como la secuencia de es una secuencia decreciente de números enteros no negativos (desde i = 2 en adelante). Por lo tanto, debe detenerse en algunos. Esto demuestra que el algoritmo finalmente se detiene. ${\displaystyle 0\leq r_{i+1}<|r_{i}|,}$ ${\displaystyle r_{i}}$ ${\displaystyle r_{k+1}=0.}$

Como el máximo común divisor es el mismo para y Esto muestra que el máximo común divisor de la entrada es el mismo que el de Esto demuestra que es el máximo común divisor de a y b . (Hasta este punto, la prueba es la misma que la del algoritmo euclidiano clásico). ${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i},}$ ${\displaystyle (r_{i-1},r_{i})}$ ${\displaystyle (r_{i},r_{i+1}).}$ ${\displaystyle a=r_{0},b=r_{1}}$ ${\displaystyle r_{k},r_{k+1}=0.}$ ${\displaystyle r_{k}}$

Como y tenemos para i = 0 y 1. La relación se sigue por inducción para todos : ${\displaystyle a=r_{0}}$ ${\displaystyle b=r_{1},}$ ${\displaystyle as_{i}+bt_{i}=r_{i}}$ ${\displaystyle i>1}$ $${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}.}$$

Por tanto , y son coeficientes de Bézout. ${\displaystyle s_{k}}$ ${\displaystyle t_{k}}$

Considere la matriz $${\displaystyle A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.}$$

La relación de recurrencia se puede reescribir en forma matricial. $${\displaystyle A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.}$$

La matriz es la matriz identidad y su determinante es uno. El determinante de la matriz más a la derecha en la fórmula anterior es −1. De ello se deduce que el determinante de es En particular, porque tenemos Viendo esto como una identidad de Bézout, esto muestra que y son coprimos . La relación que se ha demostrado anteriormente y el lema de Euclides muestran que divide b , es decir, para algún número entero d . Al dividir por la relación se obtiene So, y son números enteros coprimos que son los cocientes de a y b por un factor común, que por lo tanto es su máximo común divisor o su opuesto . ${\displaystyle A_{1}}$ ${\displaystyle A_{i}}$ ${\displaystyle (-1)^{i-1}.}$ ${\displaystyle i=k+1,}$ ${\displaystyle s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.}$ ${\displaystyle s_{k+1}}$ ${\displaystyle t_{k+1}}$ ${\displaystyle as_{k+1}+bt_{k+1}=0}$ ${\displaystyle s_{k+1}}$ ${\displaystyle b=ds_{k+1}}$ ${\displaystyle s_{k+1}}$ ${\displaystyle as_{k+1}+bt_{k+1}=0}$ ${\displaystyle a=-dt_{k+1}.}$ ${\displaystyle s_{k+1}}$ ${\displaystyle -t_{k+1}}$

Para probar la última afirmación, supongamos que a y b son ambos positivos y . Entonces, y si , se puede ver que las secuencias s y t para ( a , b ) según el EEE son, hasta los 0 y 1 iniciales, las secuencias t y s para ( b , a ). Las definiciones luego muestran que el caso ( a , b ) se reduce al caso ( b , a ). Así que asuma eso sin pérdida de generalidad. ${\displaystyle \gcd(a,b)\neq \min(a,b)}$ ${\displaystyle a\neq b}$ ${\displaystyle a<b}$ ${\displaystyle a>b}$

Se puede ver que es 1 y (que existe por ) es un número entero negativo. A partir de entonces, se alternan en signo y estrictamente aumentan en magnitud, lo que se sigue inductivamente de las definiciones y del hecho de que para , el caso se cumple porque . Lo mismo ocurre después de los primeros términos, por la misma razón. Además, es fácil ver eso (cuando a y b son ambos positivos y ). Así, observando que , obtenemos ${\displaystyle s_{2}}$ ${\displaystyle s_{3}}$ ${\displaystyle \gcd(a,b)\neq \min(a,b)}$ ${\displaystyle s_{i}}$ ${\displaystyle q_{i}\geq 1}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle i=1}$ ${\displaystyle a>b}$ ${\displaystyle t_{i}}$ ${\displaystyle q_{k}\geq 2}$ ${\displaystyle \gcd(a,b)\neq \min(a,b)}$ ${\displaystyle |s_{k+1}|=|s_{k-1}|+q_{k}|s_{k}|}$ $${\displaystyle |s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.}$$

Esto, acompañado del hecho de que sean mayores o iguales en valor absoluto que cualquier prueba anterior o respectivamente completada. ${\displaystyle s_{k},t_{k}}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$

Algoritmo euclidiano extendido polinómico

Para polinomios univariados con coeficientes en un campo , todo funciona de manera similar, división euclidiana, identidad de Bézout y algoritmo euclidiano extendido. La primera diferencia es que, en la división euclidiana y el algoritmo, la desigualdad debe ser reemplazada por una desigualdad de grados. De lo contrario, todo lo que precede en este artículo sigue igual, simplemente reemplazando números enteros por polinomios. ${\displaystyle 0\leq r_{i+1}<|r_{i}|}$ ${\displaystyle \deg r_{i+1}<\deg r_{i}.}$

Una segunda diferencia radica en el límite del tamaño de los coeficientes de Bézout proporcionado por el algoritmo euclidiano extendido, que es más preciso en el caso polinomial, lo que lleva al siguiente teorema.

Si a y b son dos polinomios distintos de cero, entonces el algoritmo euclidiano extendido produce el único par de polinomios ( s , t ) tales que

${\displaystyle as+bt=\gcd(a,b)}$

y

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

Una tercera diferencia es que, en el caso del polinomio, el máximo común divisor se define sólo hasta la multiplicación por una constante distinta de cero. Hay varias formas de definir inequívocamente un máximo común divisor.

En matemáticas, es común exigir que el máximo común divisor sea un polinomio mónico . Para conseguir esto, basta con dividir cada elemento de la producción por el coeficiente principal de. Esto permite que, si a y b son coprimos, se obtiene 1 en el lado derecho de la desigualdad de Bézout. De lo contrario, se puede obtener cualquier constante distinta de cero. En álgebra informática , los polinomios suelen tener coeficientes enteros, y esta forma de normalizar el máximo común divisor introduce demasiadas fracciones para que sea conveniente. ${\displaystyle r_{k}.}$

La segunda forma de normalizar el máximo común divisor en el caso de polinomios con coeficientes enteros es dividir cada resultado por el contenido de para obtener un máximo común divisor primitivo . Si los polinomios de entrada son coprimos, esta normalización también proporciona un máximo común divisor igual a 1. El inconveniente de este enfoque es que se deben calcular y simplificar muchas fracciones durante el cálculo. ${\displaystyle r_{k},}$

Un tercer enfoque consiste en extender el algoritmo de secuencias pseudo-residuales subresultantes de una manera similar a la extensión del algoritmo euclidiano al algoritmo euclidiano extendido. Esto permite que, al partir de polinomios con coeficientes enteros, todos los polinomios que se calculan tengan coeficientes enteros. Además, cada resto calculado es un polinomio subresultante . En particular, si los polinomios de entrada son coprimos, entonces la identidad de Bézout se convierte en ${\displaystyle r_{i}}$

${\displaystyle as+bt=\operatorname {Res} (a,b),}$

donde denota la resultante de a y b . En esta forma de identidad de Bézout, no hay denominador en la fórmula. Si se divide todo por la resultante se obtiene la identidad de Bézout clásica, con un denominador común explícito para los números racionales que aparecen en ella. ${\displaystyle \operatorname {Res} (a,b)}$

Pseudocódigo

Para implementar el algoritmo que se describe anteriormente, primero se debe observar que solo se necesitan los dos últimos valores de las variables indexadas en cada paso. Por lo tanto, para ahorrar memoria, cada variable indexada debe reemplazarse por solo dos variables.

Para simplificar, el siguiente algoritmo (y los demás algoritmos de este artículo) utilizan asignaciones paralelas . En un lenguaje de programación que no tenga esta característica, las asignaciones paralelas deben simularse con una variable auxiliar. Por ejemplo, el primero,

(old_r, r) := (r, old_r - cociente * r)

es equivalente a

prov := r;r := old_r - cociente × prov;viejo_r := prov;

y lo mismo para las otras asignaciones paralelas. Esto lleva al siguiente código:

función extendida_gcd(a, b) (antiguo_r, r) := (a, b) (viejos_s, s) := (1, 0) (antiguo_t, t): = (0, 1)  mientras que r ≠ 0 hace el cociente: = old_r div r (old_r, r) := (r, old_r − cociente × r) (viejos_s, s) := (s, viejos_s − cociente × s) (old_t, t) := (t, old_t − cociente × t)  genera "coeficientes de Bézout:", (old_s, old_t) genera "máximo común divisor:", old_r genera "cocientes por el mcd:", (t, s)

Los cocientes de a y b por su máximo común divisor, que es la salida, pueden tener un signo incorrecto. Esto es fácil de corregir al final del cálculo, pero no se ha hecho aquí para simplificar el código. De manera similar, si aob es cero y el otro es negativo, el máximo común divisor que es la salida es negativo y todos los signos de la salida deben cambiarse.

Finalmente, observe que en la identidad de Bézout, se puede resolver para dado . Por lo tanto, una optimización del algoritmo anterior consiste en calcular solo la secuencia (que produce el coeficiente de Bézout ) y luego calcular al final: ${\displaystyle ax+by=\gcd(a,b)}$ ${\displaystyle y}$ ${\displaystyle a,b,x,\gcd(a,b)}$ ${\displaystyle s_{k}}$ ${\displaystyle x}$ ${\displaystyle y}$

función extendida_gcd(a, b) s := 0; viejos_s := 1 r := b; viejo_r := a  mientras que r ≠ 0 hace el cociente: = old_r div r (old_r, r) := (r, old_r − cociente × r) (viejos_s, s) := (s, viejos_s − cociente × s)  si b ≠ 0 entonces bezout_t := (old_r − old_s × a) div b else bezout_t := 0  salida "coeficientes de Bézout:", (old_s, bezout_t) salida "máximo común divisor:", old_r

Sin embargo, en muchos casos esto no es realmente una optimización: mientras que el algoritmo anterior no es susceptible de desbordarse cuando se usa con enteros de máquina (es decir, enteros con un límite superior fijo de dígitos), la multiplicación de old_s * a en el cálculo de bezout_t puede desbordarse, lo que limita esta optimización a entradas que se pueden representar en menos de la mitad del tamaño máximo. Cuando se utilizan números enteros de tamaño ilimitado, el tiempo necesario para la multiplicación y la división crece cuadráticamente con el tamaño de los números enteros. Esto implica que la "optimización" reemplaza una secuencia de multiplicaciones/divisiones de números enteros pequeños por una única multiplicación/división, que requiere más tiempo de cálculo que las operaciones que reemplaza, tomadas en conjunto.

Simplificación de fracciones

Una fracción ⁠a/b⁠ está en forma canónica simplificada si a y b son coprimos y b es positivo. Esta forma canónica simplificada se puede obtener reemplazando las tres líneas de salida del pseudocódigo anterior por

si  s = 0  entonces genera "División por cero" si  s < 0  entonces  s  := − s ; t  := − t ( para evitar denominadores negativos ) si  s = 1  entonces salida  - t ( para evitar denominadores iguales a 1) salida  ⁠-t​/s⁠

La prueba de este algoritmo se basa en el hecho de que s y t son dos números enteros coprimos tales que + bt = 0 , y por tanto . Para obtener la forma canónica simplificada, basta con mover el signo menos por tener un denominador positivo. ${\displaystyle {\frac {a}{b}}=-{\frac {t}{s}}}$

Si b divide a a en partes iguales, el algoritmo ejecuta solo una iteración y tenemos s = 1 al final del algoritmo. Es el único caso en el que la salida es un número entero.

Calcular inversos multiplicativos en estructuras modulares.

El algoritmo euclidiano extendido es la herramienta esencial para calcular inversos multiplicativos en estructuras modulares, típicamente los enteros modulares y las extensiones de campos algebraicos . Un ejemplo notable del último caso son los campos finitos de orden no primo.

Enteros modulares

Si n es un número entero positivo, el anillo Z / n Z puede identificarse con el conjunto {0, 1, ..., n -1} de los restos de la división euclidiana por n , consistiendo la suma y la multiplicación en tomar el Resto por n del resultado de la suma y la multiplicación de números enteros. Un elemento a de Z / n Z tiene inverso multiplicativo (es decir, es una unidad ) si es coprimo de n . En particular, si n es primo , a tiene un inverso multiplicativo si no es cero (módulo n ). Por tanto, Z / n Z es un campo si y sólo si n es primo.

La identidad de Bézout afirma que a y n son coprimos si y sólo si existen números enteros s y t tales que

${\displaystyle ns+at=1}$

Reducir este módulo de identidad n da

${\displaystyle at\equiv 1\mod n.}$

Así , t , o más exactamente, el resto de la división de t por n , es el inverso multiplicativo de un módulo n .

Para adaptar el algoritmo euclidiano extendido a este problema, se debe señalar que el coeficiente de Bézout de n no es necesario y, por lo tanto, no es necesario calcularlo. Además, para obtener un resultado positivo y menor que n , se puede utilizar el hecho de que el número entero t proporcionado por el algoritmo satisface | t | < n . Es decir, si t < 0 , hay que añadirle n al final. Esto da como resultado el pseudocódigo, en el que la entrada n es un número entero mayor que 1.

función inversa(a,n) t:= 0; tritón := 1 r := norte; más nuevo := a mientras que newr ≠ 0 hacer cociente := r div newr (t, tritón) := (tritón, t − cociente × tritón) (r, nuevor) := (nuevor, r − cociente × nuevor) si r > 1 entonces  devuelve "a no es invertible" si t < 0 entonces t := t + norte regresar t

Extensiones de campos algebraicos simples

El algoritmo euclidiano extendido es también la herramienta principal para calcular inversos multiplicativos en extensiones de campos algebraicos simples . Un caso importante, ampliamente utilizado en criptografía y teoría de la codificación , es el de los campos finitos de orden no primo. De hecho, si p es un número primo y q = p ^d , el campo de orden q es una extensión algebraica simple del campo primo de p elementos, generado por una raíz de un polinomio irreducible de grado d .

Una extensión algebraica simple L de un campo K , generada por la raíz de un polinomio irreducible p de grado d, puede identificarse con el anillo del cociente , y sus elementos están en correspondencia biyectiva con los polinomios de grado menor que d . La suma en L es la suma de polinomios. La multiplicación en L es el resto de la división euclidiana por p del producto de polinomios. Por lo tanto, para completar la aritmética en L , sólo queda definir cómo calcular las inversas multiplicativas. Esto se hace mediante el algoritmo euclidiano extendido. ${\displaystyle K[X]/\langle p\rangle ,}$

El algoritmo es muy similar al proporcionado anteriormente para calcular el inverso multiplicativo modular. Hay dos diferencias principales: en primer lugar, la penúltima línea no es necesaria, porque el coeficiente de Bézout proporcionado siempre tiene un grado menor que d . En segundo lugar, el máximo común divisor que se proporciona, cuando los polinomios de entrada son coprimos, puede ser cualquier elemento distinto de cero de K ; este coeficiente de Bézout (un polinomio generalmente de grado positivo) debe pues multiplicarse por el inverso de este elemento de K . En el pseudocódigo que sigue, p es un polinomio de grado mayor que uno y a es un polinomio.

función inversa (a, p) t:= 0; tritón := 1 r :=p; más nuevo := a mientras que newr ≠ 0 hacer cociente := r div newr (r, nuevor) := (nuevor, r − cociente × nuevor) (t, tritón) := (tritón, t − cociente × tritón) si grado(r) > 0 entonces  devuelve "O p no es irreducible o a es un múltiplo de p" retorno (1/r) × t

Ejemplo

Por ejemplo, si el polinomio utilizado para definir el cuerpo finito GF(2 ⁸ ) es p = x ⁸ + x ⁴ + x ³ + x + 1 , y a = x ⁶ + x ⁴ + x + 1 es el elemento cuyo inverso Si se desea, la ejecución del algoritmo da como resultado el cálculo descrito en la siguiente tabla. Recordemos que en campos de orden 2 ⁿ , se tiene − z = z y z + z = 0 para cada elemento z en el campo). Dado que 1 es el único elemento distinto de cero de GF(2), no es necesario el ajuste en la última línea del pseudocódigo.

Por lo tanto, la inversa es x ⁷ + x ⁶ + x ³ + x , como se puede confirmar multiplicando los dos elementos y tomando el resto por p del resultado.

El caso de más de dos números.

Se puede manejar el caso de más de dos números de forma iterativa. Primero mostramos eso . Para probar esto vamos . Por definición de mcd es un divisor de y . Así para algunos . De manera similar, es un divisor de so para algunos . Dejar . Según nuestra construcción de , pero dado que el máximo divisor es una unidad . Y ya que el resultado está comprobado. ${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$ ${\displaystyle d=\gcd(a,b,c)}$ ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \gcd(a,b)=kd}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle c=jd}$ ${\displaystyle j}$ ${\displaystyle u=\gcd(k,j)}$ ${\displaystyle u}$ ${\displaystyle ud|a,b,c}$ ${\displaystyle d}$ ${\displaystyle u}$ ${\displaystyle ud=\gcd(\gcd(a,b),c)}$

Entonces, si hay y tal que la ecuación final será ${\displaystyle na+mb=\gcd(a,b)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}$

Entonces para aplicar a n números usamos inducción.

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),}$

con las ecuaciones siguientes directamente.

Ver también

• Dominio euclidiano
• Teorema de congruencia lineal
• Kuṭṭaka

Referencias

• Knuth, Donald . El arte de la programación informática . Addison-Wesley.Volumen 2, Capítulo 4.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Páginas 859–861 de la sección 31.2: Máximo común divisor. 

enlaces externos

• Fuente de la forma del algoritmo utilizado para determinar el inverso multiplicativo en GF(2^8)