Algoritmo de Euclides

Na Galipedia, a Wikipedia en galego.

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[editar | editar a fonte]

AB e CD os segmentos conmensurables.
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.

Para atopar a máxima medida común de dous números que non sexan primos entre eles.

Sexan AB e CD os dous números que non son primos un co outro. Precísase entón atopar a máxima medida común de AB e CD.

Se CD mide AB entón é unha medida común posto que CD mídese a el mesmo. É obvio que tamén é a maior medida pois nada maior que CD pode medir CD. Pero se CD non mide a AB entón algún número quedará de AB e CD, o menor que é continuamente restado do maior e que medirá o número que o precede. Porque unha unidade non quedará pois se non é así, AB e CD serán primos un co outro [Prop. VII.1], o que é o contrario do que se supuxo.

Polo tanto, algún número queda que medirá o número que o precede. Sexa CD que mide BE deixando EA menor que el mesmo e sexa EA que mide DF deixando FC menor que el mesmo e sexa FC medida de AE. Entón, como FC mide AE e AE mide DF, FC será entón medida de DF. E tamén se mide a el mesmo. Polo tanto tamén medirá todo CD. E CD mide a BE. Entón CF mide a BE e tamén mide a EA. Así mide todo BA e tamén mide CD. É dicir, CF mide tanto AB como CD polo que é unha medida común de AB e CD.

Afirmo que tamén é a maior medida común posible porque se non o for, entón un número maior que CF mide os números AB e CD, sexa este G. Dado que G mide CD e CD mide BE, G tamén mide BE. Ademais, mide todo BA polo que mide tamén o residuo AE. E AE mide DF polo que G tamén mide DF. Mide tamén todo DC polo que mide tamén o residuo CF, é dicir o maior mide o menor, o que é imposible.

Polo tanto, ningún número maior que CF pode medir os números AB e CD. Entón CF é a maior medida común de AB e CD, o que se quería demostrar.

En linguaxe moderno, o algoritmo descríbese como segue:

  1. 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.
  2. 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.
  3. 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[editar | editar a fonte]

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:

Paso Operación Significado
1 2366 dividido entre 273 é 8 e sobran 182
2 273 dividido entre 182 é 1 e sobran 91
3 182 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:

  1. Se entón e o algoritmo termina
  2. 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:

Paso Operación Significado
1 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[editar | editar a fonte]

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:

Paso Operación Significado
1 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[editar | editar a fonte]

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[editar | editar a fonte]

Existen varios xeitos de explicar o algoritmo de Euclides estendido; unha das máis comúns consiste no seguinte:

  1. Usar o algoritmo tradicional de Euclides. En cada paso, en lugar de " dividido entre é e de resto " escríbese a ecuación .
  2. Despéxase o resto de cada ecuación.
  3. 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[editar | editar a fonte]

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:

Paso Operación Significado
1 89 dividido entre 55 é 1 e sobran 34
2 55 dividido entre 34 é 1 e sobran 21
3 34 dividido entre 21 é 1 e sobran 13
4 21 dividido entre 13 é 1 e sobran 8
5 13 dividido entre 8 é 1 e sobran 5
6 8 dividido entre 5 é 1 e sobran 3
7 5 dividido entre 3 é 1 e sobran 2
8 3 dividido entre 2 é 1 e sobran 1
9 2 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[editar | editar a fonte]

Bibliografía[editar | editar a fonte]

  • von zur Gathen, Joachim; Gerhard, Jürgen (2003). "The Euclidean Algorithm". Modern Computer Algebra. Cambridge University Press. ISBN 0-521-82646-2. Arquivado dende o orixinal o 15 de setembro de 2016. Consultado o 23 de xullo de 2016. 
  • Shoup, Victor (2008). "Euclid’s algorithm". A Computational Introduction to Number Theory and Algebra. Cambridge University Press. ISBN 978-0-521-85154-1. 
  • Johnsonbaugh, Richard (2005). "Introducción a la teoría de números". Matemáticas Discretas. México: PEARSON EDUCACIÓN. ISBN 970-26-0637-3. 
  • Grimaldi, Ralph P. (1998). "Propiedades de los números enteros: Inducción matemática". Matemáticas Discreta e Combinatoria. México: Addison Wesley Longman de México. ISBN 968-444-324-2. 
  • Lipschutz, Seymour; Lipson, Marc (2009). "Propiedades dos enteiros". Matemáticas Discretas. McGraw-Hill. ISBN 978-970-10-7236-3. 
  • Brassard, Gilles; Bratley, Paul (1997). "Análisis de algoritmos". Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X. 
  • Vallée, Brigitte (2002). "Dynamical Analysis of α-Euclidean Algorithms". Journal of Algorithms 44 (1). Arquivado dende o orixinal o 06 de febreiro de 2012. Consultado o 23 de xullo de 2016. 
  • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). "Number-Theoretic Algorithms". Introduction to Algorithms. The MIT Press. ISBN 978-0-262-53305-8. 
  • Barrera Mora, Fernando (2005). "Definicións e resultados xerales". Introducción a la Teoría de Grupos (PDF). Publicacións Electrónicas da Sociedade Matemática Mexicana. ISBN 968-9161-02-4. 
  • Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004). "Divisibilidad". Álgebra Superior. México: Trillas. ISBN 968-24-3783-0. 
  • Pérez Seguí, María Luisa (2006). "Divisibilidad". Teoría de Números. Instituto de Matemáticas, UNAM. ISBN 970-32-1170-0. 
  • Sánchez Velázquez, Jesús (1998). "Algoritmos para números grandes". Introducción al análisis de algoritmos. México: Trillas. ISBN 968-24-4341-5. 
  • Baldor, Aurelio (2008). "Máximo común divisor". Álgebra. México: Grupo Editorial Patria. ISBN 978-970-817-000-0. 

Ligazóns externas[editar | editar a fonte]