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  entre  (números enteiros), obtense un cociente  e un resto . É posible demostrar que o máximo común divisor de  e  é o mesmo que o de  e  Este é o fundamento principal do algoritmo. Tamén é importante ter en conta que o máximo común divisor de calquera número  e  é precisamente . Para fins prácticos, a notación  significa máximo común divisor de  e .

Segundo o antes mencionado, para calcular o máximo común divisor de 2366 e 273 pódese proseguir do seguinte xeito:
PasoOperaciónSignificado12366 dividido entre 273 é 8 e sobran 1822273 dividido entre 182 é 1 e sobran 913182 dividido entre 91 é 2 e sobra 0
A secuencia de igualdades  implican que . Dado que , entón conclúese que . 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  e , séguense as seguintes regras:
 Se  entón  e o algoritmo termina
 Noutro caso,  onde  é o resto de dividir  entre . Para calcular  empréganse estas mesmas regras.

Se chamamos  e , aplicando estas regras obtense a seguinte secuencia de operacións:
PasoOperaciónSignificado1 dividido entre  é  e sobran 2 dividido entre  é  e sobran 3 dividido entre  é  e sobran  dividido entre  é  e sobran  dividido entre  é  e sobra 
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  (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  e  o algoritmo de Euclides suxire a seguinte secuencia de operacións:
PasoOperaciónSignificado1 dividido entre  é  e sobra 2 dividido entre  é  e sobra 3 dividido entre  é  e sobra 0
Deste xeito conclúese que o seu máximo común divisor é .

 Algoritmo de Euclides estendido 
O algoritmo de Euclides estendido permite, ademais de atopar o máximo común divisor de dous números enteiros  e , expresalo como a mínima combinación linear deses números, é dicir, atopar números enteiros  e  tales que . 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 " dividido entre  é  e de resto " escríbese a ecuación .
 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  e  obtense a seguinte secuencia de operacións:

PasoOperaciónSignificado189 dividido entre 55 é 1 e sobran 34255 dividido entre 34 é 1 e sobran 21334 dividido entre 21 é 1 e sobran 13421 dividido entre 13 é 1 e sobran 8513 dividido entre 8 é 1 e sobran 568 dividido entre 5 é 1 e sobran 375 dividido entre 3 é 1 e sobran 283 dividido entre 2 é 1 e sobran 192 dividido entre 1 é 2 e sobra 0

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  divisións para calcular o máximo común divisor de  e  onde .

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  bits, entón o número medio de divisións necesarias é .

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 é  onde  é o grao dos polinomios.

 Véxase tamén 

 Bibliografía 














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

Categoría:Aritmética