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

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.

Modelo:Cita

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

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{m}\mathrm{c}\mathrm{d}(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:

Paso	Operación	Significado
1	2366 dividido entre 273 é 8 e sobran 182	$\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(273,182)$
2	273 dividido entre 182 é 1 e sobran 91	$\mathrm{m}\mathrm{c}\mathrm{d}(273,182)=\mathrm{m}\mathrm{c}\mathrm{d}(182,91)$
3	182 dividido entre 91 é 2 e sobra 0	$\mathrm{m}\mathrm{c}\mathrm{d}(182,91)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$

A secuencia de igualdades $\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(273,182)=\mathrm{m}\mathrm{c}\mathrm{d}(182,91)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$ implican que $\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$. Dado que $\mathrm{m}\mathrm{c}\mathrm{d}(91,0)=91$, entón conclúese que $\mathrm{m}\mathrm{c}\mathrm{d}(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:

1. Se $b=0$ entón $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=a$ e o algoritmo termina
2. Noutro caso, $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=\mathrm{m}\mathrm{c}\mathrm{d}(b,r)$ onde $r$ é o resto de dividir $a$ entre $b$. Para calcular $\mathrm{m}\mathrm{c}\mathrm{d}(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:

Paso	Operación	Significado
1	$r_0$ dividido entre $r_1$ é $q_1$ e sobran $r_2$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_0,r_1)=\mathrm{m}\mathrm{c}\mathrm{d}(r_1,r_2)$
2	$r_1$ dividido entre $r_2$ é $q_2$ e sobran $r_3$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_1,r_2)=\mathrm{m}\mathrm{c}\mathrm{d}(r_2,r_3)$
3	$r_2$ dividido entre $r_3$ é $q_3$ e sobran $r_4$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_2,r_3)=\mathrm{m}\mathrm{c}\mathrm{d}(r_3,r_4)$
$⋮$	$⋮$	$⋮$
$n$	$r_{n-1}$ dividido entre $r_n$ é $q_n$ e sobran $r_{n+1}$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_{n-1},r_n)=\mathrm{m}\mathrm{c}\mathrm{d}(r_n,r_{n+1})$
$n+1$	$r_n$ dividido entre $r_{n+1}$ é $q_{n+1}$ e sobra $0$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_n,r_{n+1})=\mathrm{m}\mathrm{c}\mathrm{d}(r_{n+1},0)$

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:

Paso	Operación	Significado
1	$x^5+2x^3+x$ dividido entre $x^4-1$ é $x$ e sobra $2x^3+2x$	$\mathrm{m}\mathrm{c}\mathrm{d}(x^5+2x^3+x,x^4-1)=\mathrm{m}\mathrm{c}\mathrm{d}(x^4-1,2x^3+2x)$
2	$x^4-1$ dividido entre $2x^3+2x$ é $\frac{1}{2}x$ e sobra $-x^2-1$	$\mathrm{m}\mathrm{c}\mathrm{d}(x^4-1,2x^3+2x)=\mathrm{m}\mathrm{c}\mathrm{d}(2x^3+2x,-x^2-1)$
3	$2x^3+2x$ dividido entre $-x^2-1$ é $-2x$ e sobra 0	$\mathrm{m}\mathrm{c}\mathrm{d}(2x^3+2x,-x^2-1)=\mathrm{m}\mathrm{c}\mathrm{d}(-x^2-1,0)$

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{m}\mathrm{c}\mathrm{d}(a,b)=as+bt$. 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:

1. 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=bq+r$.
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

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:

Paso	Operación	Significado
1	89 dividido entre 55 é 1 e sobran 34	$\mathrm{m}\mathrm{c}\mathrm{d}(89,55)=\mathrm{m}\mathrm{c}\mathrm{d}(55,34)$
2	55 dividido entre 34 é 1 e sobran 21	$\mathrm{m}\mathrm{c}\mathrm{d}(55,34)=\mathrm{m}\mathrm{c}\mathrm{d}(34,21)$
3	34 dividido entre 21 é 1 e sobran 13	$\mathrm{m}\mathrm{c}\mathrm{d}(34,21)=\mathrm{m}\mathrm{c}\mathrm{d}(21,13)$
4	21 dividido entre 13 é 1 e sobran 8	$\mathrm{m}\mathrm{c}\mathrm{d}(21,13)=\mathrm{m}\mathrm{c}\mathrm{d}(13,8)$
5	13 dividido entre 8 é 1 e sobran 5	$\mathrm{m}\mathrm{c}\mathrm{d}(13,8)=\mathrm{m}\mathrm{c}\mathrm{d}(8,5)$
6	8 dividido entre 5 é 1 e sobran 3	$\mathrm{m}\mathrm{c}\mathrm{d}(8,5)=\mathrm{m}\mathrm{c}\mathrm{d}(5,3)$
7	5 dividido entre 3 é 1 e sobran 2	$\mathrm{m}\mathrm{c}\mathrm{d}(5,3)=\mathrm{m}\mathrm{c}\mathrm{d}(3,2)$
8	3 dividido entre 2 é 1 e sobran 1	$\mathrm{m}\mathrm{c}\mathrm{d}(3,2)=\mathrm{m}\mathrm{c}\mathrm{d}(2,1)$
9	2 dividido entre 1 é 2 e sobra 0	$\mathrm{m}\mathrm{c}\mathrm{d}(2,1)=\mathrm{m}\mathrm{c}\mathrm{d}(1,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 $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 é $\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

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita publicación
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Ligazóns externas

• O algoritmo de Euclides.
• Algoritmo de Euclides.