Algoritmo euclidiano extendido - Extended Euclidean algorithm

En aritmética y la programación informática , el algoritmo de Euclides extendido es una extensión para el algoritmo de Euclides , 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 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 simultáneamente esta ecuación y dividir las entradas. Le permite a uno calcular también, con un costo casi ningún adicional, los cocientes de una 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 la identidad de Bézout de dos polinomios univariados .

El algoritmo de Euclides extendido es particularmente útil cuando un y b son primos entre sí . Con esa disposición, x es el inverso multiplicativo modular de un 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 campo algebraico 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. Solo se conservan los remanentes . 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 tal que ${\ Displaystyle q_ {1}, \ ldots, q_ {k}}$${\ Displaystyle r_ {0}, \ ldots, r_ {k + 1}}$

${\ Displaystyle {\ begin {alineado} r_ {0} & = a \\ r_ {1} & = b \\ & \, \, \, \ vdots \\ r_ {i + 1} & = r_ {i- 1} -q_ {i} r_ {i} \ quad {\ text {y}} \ quad 0 \ leq r_ {i + 1} <| r_ {i} | \ quad {\ text {(esto define}} q_ {i}) \\ & \, \, \, \ vdots \ end {alineado}}}$

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

El cálculo se detiene cuando se alcanza 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 {alineado} 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 {(esto define}} 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 {alineado}}}$

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 eso es${\ Displaystyle s_ {k}}$${\ Displaystyle t_ {k},}$${\ Displaystyle \ gcd (a, b) = r_ {k} = as_ {k} + bt_ {k}}$
• Los cocientes de una y b por su máximo común divisor están dadas 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 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 {y}} \ quad | t_ { i} | \ leq \ left \ lfloor {\ frac {a} {2 \ gcd (a, b)}} \ right \ rfloor}$

porque donde denota la parte integral de x , que es el mayor número 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, ya que es el par único que satisface las dos desigualdades anteriores.

También significa que el algoritmo se puede hacer sin desbordamiento de entero por un programa de ordenador usando números enteros de un tamaño fijo que es mayor que el de una y b .

Ejemplo

La siguiente tabla muestra cómo procede el algoritmo euclidiano extendido con la entrada 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 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 la entrada 46 y 240 por el máximo común divisor 2 .

Prueba

Como la secuencia de es una secuencia decreciente de enteros no negativos (desde i = 2 en adelante). Por lo tanto, debe detenerse con algo. Esto prueba que el algoritmo se detiene eventualmente. ${\ 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 la misma que la de esto prueba que es el máximo común divisor de un 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 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 de matriz.

${\ 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, ya que, al considerar esto como la identidad de un Bézout, esto muestra que y son coprime . La relación que se ha demostrado arriba y Lema de Euclides muestra que divide b y divide a . Ya que son primos entre sí, que son, hasta su signo los cocientes de b y una por su máximo común divisor. ${\ 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 t_ {k + 1}}$

Para probar la última afirmación, suponer que un y b son ambos positivos y . A continuación, y, si , puede verse que las s y t secuencias para ( a , b ) bajo el EEE son, hasta 0s y 1s iniciales, el t y s secuencias para ( b , a ). Las definiciones muestran entonces que el caso ( a , b ) se reduce al caso ( b , a ). Así que asuma eso sin perder la 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, los alternos 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 con los posteriores a los primeros términos, por la misma razón. Además, es fácil ver que (cuando un y b son ambos positivos y ). Por lo tanto, ${\ 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} | = \ left | {\ frac {b} {\ gcd (a, b)}} \ right | \ geq 2 | s_ {k} | \ qquad {\ text {y }} \ qquad | t_ {k + 1} | = \ left | {\ frac {a} {\ gcd (a, b)}} \ right | \ geq 2 | t_ {k} |.}$

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

Algoritmo euclidiano extendido polinomial

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 tiene que ser reemplazada 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 del polinomio, lo que conduce al siguiente teorema.

Si ayb son dos polinomios distintos de cero, entonces el algoritmo euclidiano extendido produce el par único de polinomios ( s , t ) tal 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 solo hasta la multiplicación por una constante distinta de cero. Hay varias formas de definir sin ambigüedades un máximo común divisor.

En matemáticas, es común requerir que el máximo común divisor sea un polinomio monico . Para conseguir esto, basta con dividir cada elemento de la salida por el coeficiente principal de este modo que, si un y b son primos entre sí, 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 de computadora , 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 muchas fracciones deben calcularse y simplificarse durante el cálculo. ${\ Displaystyle r_ {k},}$

Un tercer enfoque consiste en extender el algoritmo de secuencias de pseudo-resto subsultantes 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, todo 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 una 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 señalar 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 otros algoritmos de este artículo) utiliza asignaciones paralelas . En un lenguaje de programación que no tiene esta característica, las asignaciones paralelas deben simularse con una variable auxiliar. Por ejemplo, el primero,

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

es equivalente a

prov := r;
r := old_r - quotient × prov;
old_r := prov;

y de manera similar para las otras asignaciones paralelas. Esto conduce al siguiente código:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

Los cocientes de una y b por su máximo común divisor, que es de salida, pueden tener una señal incorrecta. Esto es fácil de corregir al final del cálculo, pero no se ha hecho aquí para simplificar el código. Del mismo modo, si cualquiera de una o b es cero y el otro es negativo, el máximo común divisor que es salida es negativa, y todas las señales de la salida debe ser cambiado.

Finalmente, observe que en la identidad de Bézout , uno puede resolver por 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}$

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common 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 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, limitando esta optimización a las 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 aumenta de forma cuadrática 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 sola multiplicación / división, lo que requiere más tiempo de cálculo que las operaciones que reemplaza, tomadas en conjunto.

Simplificación de fracciones

Una fracción a/Bestá 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

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output -t        (for avoiding denominators equal to 1)
output -t/s

La prueba de este algoritmo se basa en el hecho de que es y t son dos números primos entre sí de tal manera 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 uniformemente, 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 campo algebraico . Un ejemplo notable de este último caso son los campos finitos de orden no primario.

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 , la suma y la multiplicación consiste en tomar el resto por n del resultado de la suma y la multiplicación de números enteros. Un elemento de una de Z / n Z tiene un inverso multiplicativo (es decir, se trata de una unidad ) si es primos entre sí a 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 solo si n es primo.

La identidad de Bézout afirma que una y n son primos entre sí, si y sólo si existen enteros s y t Obra de tal manera que

${\ Displaystyle ns + en = 1}$

Reducir esta identidad módulo n da

${\ Displaystyle en \ 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 e inferior a 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 número entero mayor que 1.

 function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Extensiones de campos algebraicos simples

El algoritmo euclidiano extendido también es 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 adición de 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 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, no se necesita la última línea, pero una, 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 Bézout (un polinomio generalmente de grado positivo) tiene por lo tanto que se multiplica 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.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Ejemplo

Por ejemplo, si el polinomio utilizado para definir el campo finito GF (2 ⁸ ) es p = x ⁸  +  x ⁴  +  x ³  +  x  + 1, y a = x ⁶  +  x ⁴  +  x  + 1 es el elemento cuyo inverso Si lo desea, la ejecución del algoritmo da como resultado el cálculo que se describe en la siguiente tabla. Recordemos que en los campos de orden 2 ⁿ , se tiene - z = z y z + z = 0 para cada elemento de 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, dejemos . Por definición, mcd es un divisor de y . Así para algunos . De manera similar, es un divisor de eso para algunos . Deja . Por nuestra construcción de , pero ya que es el máximo divisor es una unidad . Y dado que 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 entonces 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}, \ puntos, \ gcd (a_ {n-1} \ ,, a_ {n}))), \ puntos),}$

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)