Algoritmo de Euclides estendido

En aritmética e programación informática, o **algoritmo de Euclides estendido** é unha extensión do algoritmo de Euclides que calcula, alén do máximo común divisor (mcd) dos números enteiros *a* e *b*, tamén os coeficientes da identidade de Bézout, que son números enteiros *x* e *y* tal que

: ax + by = \gcd(a, b). 
E sendo   e  positivos, un de  ou  é negativo.

O algoritmo de Euclides estendido é particularmente útil cando *a* e *b* son coprimos. Con esa condición temos que *x* é o inverso multiplicativo modular de *a* módulo *b*, e *y* é o inverso multiplicativo modular de *b* módulo *a*. 

Do mesmo xeito, o algoritmo de Euclides polinómico estendido permite calcular o inverso multiplicativo en extensións de corpos alxébricos e, en particular, en corpos finitos de orde non prima. 

Cun algoritmo moi similar podemos calcular o máximo común divisor polinómico e os coeficientes da identidade de Bézout de dous polinomios dunha variable.

## Descrición 
O algoritmo de Euclides estándar son unha sucesión de divisións  cuxos cocientes non se utilizan. Só se usan os *restos*. Para o algoritmo estendido tamén fan falta os sucesivos cocientes. 

: 
\begin{align}
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}-c_i r_i & \text {e } 0 & \le r_{i+1} 

O algoritmo de Euclides estendido procede de xeito similar, mais engade outras dúas secuencias s_i, t_i, sendo c_i os cocientes e r_i os restos como segue:

O cálculo tamén se detén cando r_{k+1}=0 e dá

* r_k é o máximo común divisor da entrada a=r_0 e b=r_1.
* Os coeficientes de Bézout son s_k e t_k, é dicir \gcd(a,b)=r_k=as_k+bt_k
* Os cocientes de *a* e *b* polo seu máximo común divisor veñen dados por s_{k+1}=\pm\frac{b}{\gcd(a,b)} e t_{k+1}=\pm\frac{a}{\gcd(a,b)}

A maiores, se *a* e *b* son ambos os dous positivos e \gcd(a,b)\neq\min(a,b), daquela

: |s_i| \leq \left\lfloor\frac{b}{2\gcd(a,b)}\right\rfloor\quad \text{e} \quad |t_i| \leq \left\lfloor\frac{a}{2\gcd(a,b)}\right\rfloor

para 0\leq i \leq k, onde \lfloor x\rfloor denota a parte enteira de , é dicir, o maior enteiro non maior que .

Isto implica que o par de coeficientes de Bézout proporcionado polo algoritmo de Euclides estendido é o *par mínimo* de coeficientes de Bézout, xa que é o único par que satisfai ambas as desigualdades anteriores.

A continuación un exemplo pode clarificar.

### Exemplo 
A seguinte táboa mostra como funciona o algoritmo de Euclides estendido coas entradas  e . O máximo común divisor é a última entrada distinta de cero,    na columna "resto". O cálculo detense na fila 6, porque o resto é . Os coeficientes de Bézout aparecen nas dúas últimas entradas da penúltima fila. De feito, é doado verificar que  \cdot  +  \cdot  = 2. Finalmente, as dúas últimas entradas  e  da última fila son, ata o signo, os cocientes da entrada  e  polo máximo común divisor  .

A maiores, os cocientes, en azul, son os coeficientes da fracción continua de  = [5, 4, 1, 1, 2].

## Algoritmo polinómico de Euclides estendido 
Para polinomios dunha variable con coeficientes nun corpo, todo funciona de xeito similar, división euclidiana, identidade de Bézout e algoritmo de Euclides estendido. A primeira diferenza é que, na división de Euclides e no algoritmo, a desigualdade 0\le r_{i+1} ten que ser substituída por unha desigualdade nos graos do polinomio \deg r_{i+1} Para o demais, todo o que precede neste artigo segue sendo o mesmo, simplemente substituíndo os enteiros por polinomios.

Unha segunda diferenza reside no límite do tamaño dos coeficientes de Bézout proporcionados polo algoritmo, que é máis preciso no caso polinómico, o que leva ao seguinte teorema.

En matemáticas, é común esixir que o máximo común divisor sexa un polinomio mónico. Para conseguir isto, abonda con dividir cada elemento da saída polo coeficiente principal de r_{k}. Isto permite que, se *a* e *b* son coprimos, se obtén 1 no lado dereito da desigualdade de Bézout. En caso contrario, pódese obter calquera constante distinta de cero.

*Se a e b son dous polinomios distintos de cero, entón o algoritmo de Euclides estendido produce o único par de polinomios* (*s*, *t*) *tal que*

: as+bt=\gcd(a,b)

O algoritmo de Euclides estendido é a ferramenta esencial para calcular inversos multiplicativos en estruturas modulares, normalmente os enteiros modulares e as extensións de corpos alxébricos. Un exemplo notable deste último caso son os corpos finitos de orde non prima.

: \deg s 

Unha terceira diferenza é que, no caso polinómico, o máximo común divisor defínese só ata a multiplicación por unha constante distinta de cero. Hai varias formas de definir sen ambigüidades un máximo común divisor.

: \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),

## Cálculo de inversos multiplicativos en aritmética modular 
### Números enteiros modulares 
Un elemento  do anel   ten un inverso multiplicativo (é dicir, é unha unidade) se é coprimo con . En particular, se  é primo,  ten un inverso multiplicativo se non é cero (módulo ). Así,  é un corpo se e só se  é primo.

A identidade de Bézout afirma que  e  son primos primos se e só se existen números enteiros  e  tal que

: ns+at=1

Reducindo esta identidade módulo  dáse

: at \equiv 1 \mod n.

Así , ou, máis exactamente, o resto da división de  por , é o inverso multiplicativo de  módulo .

### Extensións simples de corpos alxébricos 
#### Exemplo 
Por exemplo, se o polinomio usado para definir o corpo finito GF(28) é , e  é o elemento cuxo inverso se desexa, entón a realización do algoritmo dá como resultado o cálculo descrito na seguinte táboa embaixo. Lembremos que en corpos de orde 2*n*, un ten &#x2212; *z* = *z* e *z* + *z* = 0 para cada elemento *z* do corpo). Temos que 1 é o único elemento distinto de cero en GF(2).

Así, o inverso é , como se pode confirmar multiplicando os dous elementos xuntos e tomando o resto por  do resultado.

## O caso de máis de dous números 
Pódese manexar o caso de máis de dous números de forma iterativa. 

: \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),

## Notas 
## Véxase tamén 
### Bibliografía 
*  Volume 2, Chapter 4.
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. . Pages 859&ndash;861 of section 31.2: Greatest common divisor.

### Outros artigos 
* Dominio euclidiano
* Teorema chinés do resto
* Inverso multiplicativo modular

### Ligazóns externas 
* Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)