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