From Wikipedia, the free encyclopedia
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.
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:
O feito de que os segmentos son conmesurables é clave para asegurar que o proceso remata.
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:
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).
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 é .
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.
Existen varios xeitos de explicar o algoritmo de Euclides estendido; unha das máis comúns consiste no seguinte:
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.
Wikimedia Commons ten máis contidos multimedia na categoría: Algoritmo de Euclides |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.