Algoritmo de Euclides

O **algoritmo de Euclides** é un método antigo e eficaz para calcular o máximo común divisor (**MCD**). Foi descrito orixinariamente por Euclides na súa obra *Elementos*. O **algoritmo de Euclides estendido** é unha lixeira modificación que permite ademais expresar o máximo común divisor como unha combinación linear. Este algoritmo ten aplicacións en diversas áreas como álxebra, teoría dos números e ciencias da computación entre outras. Cunhas pequenas modificacións adoita empregarse en computadoras electrónicas debido á súa grande eficiencia.

## Algoritmo orixinal de Euclides 
lang=es|miniatura|*AB* e *CD* os segmentos conmensurables.
miniatura|Exemplo do algoritmo orixinal de Euclides.
Na concepción grega da matemática, os números entendíanse como magnitudes xeométricas. Un tema recorrente na xeometría grega é o da conmensurabilidade de dous segmentos: dous segmentos (números) *AB* e *CD* son conmensurables cando existe un terceiro segmento *PQ* que colle exactamente un número enteiro de veces nos primeiros dos, é dicir, *PQ* «mide» os segmentos *AB* e *CD*.

Non todo par de segmentos é conmensurable, como atoparon os pitagóricos cando establecen que o lado e a diagonal dun cadrado non son conmensurables, pero no caso de dous segmentos conmensurables deséxase atopar a maior medida común posible.

Euclides describe na proposición VII.2 dos seus Elementos un método que permite atopar a maior medida común posible de dous números (segmentos) que non sexan primos entre eles, aínda que pola época tal método se explica en termos xeométricos.

En linguaxe moderno, o algoritmo descríbese como segue:
# Dados dous segmentos *AB* e *CD* (con *AB>CD*), restamos *CD* de *AB* tantas veces como sexa posible. Se non houber residuo, entón *CD* é a máxima medida común.
# Se se obtiver un residuo *EA*, este é menor que *CD* e pódese repetir o proceso: restamos *EA* tantas veces como sexa posible de *CD*. Se ao final non queda un residuo, *EA* é a medida común. En caso contrario obtense un novo residuo *FC* menor que EA.
# Repítese o proceso ata que nalgún momento non se obteña residuo. Entón o último residuo obtido é a maior medida común.

O feito de que os segmentos son conmesurables é clave para asegurar que o proceso remata.

## Algoritmo de Euclides tradicional 
Ao dividir a entre b (números enteiros), obtense un cociente q e un resto r. É posible demostrar que o máximo común divisor de a e b é o mesmo que o de b e r Este é o fundamento principal do algoritmo. Tamén é importante ter en conta que o máximo común divisor de calquera número a e 0 é precisamente a. Para fins prácticos, a notación \mathrm{mcd}(a,b) significa *máximo común divisor de a e b*.

Segundo o antes mencionado, para calcular o máximo común divisor de 2366 e 273 pódese proseguir do seguinte xeito:

A secuencia de igualdades \mathrm{mcd}(2366,273)=\mathrm{mcd}(273,182)=\mathrm{mcd}(182,91)=\mathrm{mcd}(91,0) implican que \mathrm{mcd}(2366,273)=\mathrm{mcd}(91,0). Dado que \mathrm{mcd}(91,0)=91, entón conclúese que \mathrm{mcd}(2366,273)=91. Este mesmo procedemento pode aplicarse a calquera par de números naturais. En xeral, se se desexa atopar o máximo común divisor de dous números naturais a e b, séguense as seguintes regras:
# Se b=0 entón \mathrm{mcd}(a,b)=a e o algoritmo termina
# Noutro caso, \mathrm{mcd}(a,b)=\mathrm{mcd}(b,r) onde r é o resto de dividir a entre b. Para calcular \mathrm{mcd}(b,r) empréganse estas mesmas regras.

Se chamamos a=r_0 e b=r_1, aplicando estas regras obtense a seguinte secuencia de operacións:

Como a sucesión de residuos vai diminuíndo, ao final un residuo ten que ser cero e é nese momento cando o algoritmo termina. O máximo común divisor é precisamente r_{n+1} (o último residuo que non é cero).

### Xeneralización 
En realidade o algoritmo de Euclides funciona non só para os números naturais, senón para calquera elemento no que exista unha "división con residuo". Este tipo de divisións chámanse divisións euclidianas e aos conxuntos onde se pode definir esa división chámanse dominios euclidianos. Por exemplo, o conxunto dos números enteiros e o dos polinomios con coeficientes racionais son dominios euclidianos porque podemos definir unha división con residuo. Deste xeito, pode calcularse o máximo común divisor de dous números enteiros ou de dous polinomios.

Por exemplo, para calcular o máximo común divisor dos polinomios P(x)=x^5+2x^3+x e Q(x)=x^4-1 o algoritmo de Euclides suxire a seguinte secuencia de operacións:

Deste xeito conclúese que o seu máximo común divisor é -x^2-1.

## Algoritmo de Euclides estendido 
O algoritmo de Euclides estendido permite, ademais de atopar o máximo común divisor de dous números enteiros a e b, expresalo como a mínima combinación linear deses números, é dicir, atopar números enteiros s e t tales que \mathrm{mcd}(a,b)=a s+b t. Isto tamén se xeneraliza para calquera dominio euclidiano.

### Fundamentos 
Existen varios xeitos de explicar o algoritmo de Euclides estendido; unha das máis comúns consiste no seguinte:
# Usar o algoritmo tradicional de Euclides. En cada paso, en lugar de "a dividido entre b é q e de resto r" escríbese a ecuación a=b q+r.
# Despéxase o resto de cada ecuación.
# Substitúese o resto da última ecuación na penúltima, e a penúltima na antepenúltima e así sucesivamente ata chegar á primeira ecuación, e en todos os pasos exprésase cada resto como combinación linear.

## Complexidade do algoritmo 
miniatura|230px|Gráfica do número de divisións efectuadas no algoritmo de Euclides. O vermello indica poucas operacións, mentres que as cores eventualmente máis azuis representan maior número de operacións.
O teorema de Lamé afirma que o caso peor para este algoritmo é cando se quere calcular o máximo común divisor de dous números consecutivos da sucesión de Fibonacci. Por exemplo, se se desexa calcular o máximo común divisor de f_{10}=55 e f_{11}=89 obtense a seguinte secuencia de operacións:

Neste exemplo obsérvase que con estes dous números de dous díxitos decimais, precísanse facer 9 divisións. En xeral, o número de divisións efectuadas polo algoritmo nunca supera 5 veces o número de díxitos que teñen estes números. En termos de complexidade computacional, isto significa que se requiren  O(\log n) divisións para calcular o máximo común divisor de n e m onde n>m.

O número medio de divisións efectuadas polo algoritmo estívose investigando dende 1968, pero só en 2002, Brigitte Vallée demostrou que se os dous números se poden representar con n bits, entón o número medio de divisións necesarias é \textstyle{\frac{\pi^2}{6}n}.

Non obstante, non abonda con saber o número de divisións. Hai que lembrar que o algoritmo de Euclides funciona tanto para polinomios como para números enteiros, e en xeral, calquera dominio euclidiano. En cada caso, a complexidade do algoritmo depende do número de divisións efectuadas e do custo de cada división. No caso dos polinomios, o número de divisións é O(\log n) onde n é o grao dos polinomios.

## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

### Ligazóns externas 
* O algoritmo de Euclides.
* Algoritmo de Euclides.