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 la identidad de Bézout , que son los números enteros x e y tales que

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

Se trata de un algoritmo de certificación , porque el mcd es el único número que puede satisfacer simultáneamente esta ecuación y dividir las entradas. ^[1] 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 de un polinomio y los coeficientes de la identidad de Bézout de dos polinomios univariados .

El algoritmo euclidiano extendido es particularmente útil cuando a y b son coprimos . Con esa condició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 polinomial 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 mediante una sucesión de divisiones euclidianas cuyos cocientes no se utilizan. Sólo se conservan los residuos . 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 residuos 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 manera única y a partir de y ${\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 ${\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 único par que satisface ambas desigualdades anteriores.

Esto también significa que el algoritmo puede realizarse sin desbordamiento de números enteros mediante un programa informático que utilice 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 en ella es 0. Los coeficientes de Bézout aparecen en las dos últimas columnas de la penúltima fila. De hecho, es fácil verificar 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 las entradas 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 (a partir de i = 2), debe detenerse en algún punto. Esto demuestra que el algoritmo se detiene en algún momento. ${\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 demuestra 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 todo : ${\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 lo 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 puede reescribirse 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 situada más a la derecha en la fórmula anterior es −1. De ello se deduce que el determinante de es En particular, para lo que tenemos Viéndolo como una identidad de Bézout, esto demuestra que y son coprimos . La relación que se ha demostrado anteriormente y el lema de Euclides demuestran que divide a b , es decir, para algún entero d . Dividiendo por la relación se obtiene Por lo tanto, y son enteros coprimos que son los cocientes de a y b por un factor común, que es, por tanto, 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 ) bajo el EEA son, hasta los 0 y 1 iniciales, las secuencias t y s para ( b , a ). Las definiciones muestran entonces que el caso ( a , b ) se reduce al caso ( b , a ). Así que supongamos que 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 entero negativo. A partir de entonces, los 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 es cierto para después de los primeros términos, por la misma razón. Además, es fácil ver que (cuando a y b son ambos positivos y ). Por lo tanto, notando 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 son 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 polinomial

Para polinomios univariados con coeficientes en un cuerpo , 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 reemplazarse por una desigualdad en los grados. De lo contrario, todo lo que precede en este artículo permanece igual, simplemente reemplazando los 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 conduce 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 de los polinomios, el máximo común divisor se define únicamente hasta la multiplicación por una constante distinta de cero. Existen varias formas de definir de forma inequívoca un máximo común divisor.

En matemáticas, es común requerir que el máximo común divisor sea un polinomio mónico . Para obtener esto, basta con dividir cada elemento de la salida por el coeficiente principal de Esto permite que, si a y b son coprimos, se obtenga 1 en el lado derecho de la desigualdad de Bézout. De lo contrario, se puede obtener cualquier constante distinta de cero. En álgebra computacional , los polinomios comúnmente tienen coeficientes enteros, y esta forma de normalizar el máximo común divisor introduce demasiadas fracciones para ser 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 salida 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 las sucesiones de pseudoresiduos subresultantes de una manera similar a la extensión del algoritmo euclidiano al algoritmo euclidiano extendido. Esto permite que, al comenzar con polinomios con coeficientes enteros, todos los polinomios que se calculan tengan coeficientes enteros. Además, cada residuo 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 la 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 descrito anteriormente, primero hay que tener en cuenta que en cada paso solo se necesitan los dos últimos valores de las variables indexadas. 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

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

Y lo mismo para las demás asignaciones paralelas. Esto conduce al siguiente código:

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

Los cocientes de a y b por su máximo común divisor, que se obtiene como 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 a o b es cero y el otro es negativo, el máximo común divisor que se obtiene como salida es negativo y se deben cambiar todos los signos de la salida.

Por último, observe que en la identidad de Bézout, , se puede resolver para dado . Por lo tanto, una optimización del algoritmo anterior es 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 gcd_extendido(a, b) s := 0; antiguo_s := 1 r := b; antiguo_r := a  mientras r ≠ 0 hacer cociente := old_r div r (antiguo_r, r) := (r, antiguo_r − cociente × r) (old_s, s) := (s, old_s − cociente × s)  si b ≠ 0 entonces bezout_t := (antiguo_r − antiguo_s × a) div b de lo contrario sin efecto_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 desbordamiento cuando se utiliza con números enteros de máquina (es decir, números 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óna/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 salida "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 - el/s⁠

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

Si b divide a a de manera uniforme, 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 entero.

Cálculo de inversos multiplicativos en estructuras modulares

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

Números enteros modulares

Si n es un 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 adición y la multiplicación en tomar el resto por n del resultado de la adición 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 con n . En particular, si n es primo , a tiene inverso multiplicativo si no es cero (módulo n ). Por tanto, Z / n Z es un cuerpo si y solo 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}$

Reduciendo esta identidad módulo n se obtiene

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

Por lo tanto , t , o, más exactamente, el resto de la división de t por n , es el inverso multiplicativo de a módulo n .

Para adaptar el algoritmo euclidiano extendido a este problema, se debe tener en cuenta que no se necesita el coeficiente de Bézout de n 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 entero t proporcionado por el algoritmo satisface | t | < n . Es decir, si t < 0 , se le debe sumar n al final. Esto da como resultado el pseudocódigo, en el que la entrada n es un entero mayor que 1.

función inversa(a, n) t := 0; tritón := 1 r := n; nuevo r := 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 + n volver t

Extensiones de campos algebraicos simples

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

Una extensión algebraica simple L de un cuerpo K , generado por la raíz de un polinomio irreducible p de grado d puede identificarse con el anillo de cocientes , y sus elementos están en correspondencia biyectiva con los polinomios de grado menor que d . La adición en L es la adición 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 , solo queda definir cómo calcular los inversos multiplicativos. 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 que se proporciona 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) tiene que ser multiplicado 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; nuevo r := 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 se desea, entonces la ejecución del algoritmo da como resultado el cálculo descrito en la siguiente tabla. Recordemos que en cuerpos de orden 2 ⁿ , se tiene − z = z y z + z = 0 para cada elemento z en el cuerpo). Como 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 entre sí 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 manera iterativa. Primero demostramos que . Para probar esto, sea . Por definición de mcd es un divisor de y . Por lo tanto, para algunos . De manera similar, es un divisor de, por lo que para algunos . Sea . Por nuestra construcción de , pero como es el mayor divisor es una unidad . Y como el resultado está probado. ${\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 tales que entonces 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 siguiendo directamente.

Véase también

• Dominio euclidiano
• Teorema de congruencia lineal
• Kuttaka

Referencias

1. McConnell, Ross; Mehlhorn, Kurt; Näher, Stefan; Schweitzer, Pascal. "Algoritmos de certificación" (PDF) . Consultado el 29 de septiembre de 2024 .

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