Algoritmo de Euclides

Definición

El algoritmo de Euclides es un método eficaz para calcular el máximo común divisor (mcd) de dos números enteros.

El algoritmo consiste en varias divisiones euclídeas sucesivas. En la primera división, se toma como dividendo el mayor de los números y como divisor el otro (se ahorra así un paso). Luego, el divisor y el resto sirven respectivamente de dividendo y divisor de la siguiente división. El proceso se para cuando se obtiene un resto nulo. El mcd es entonces el penúltimo resto del algoritmo.
Formalmente, si llamemos a, b los enteros iniciales, r₁, r_n ... r_n-1 y r_n = 0 los restos sucesivos, entonces:

mcd (a, b) = mcd (b, r₁), con r₁ = a - b·q (q es el cociente de a por b)

En efecto los divisores comunes de a y b son los de a - b·q y b:

$\left. \begin{matrix} \mbox{q / a} \\ \mbox{q / b} \end{matrix} \right \} \Leftrightarrow \left \{ \begin{matrix} \mbox{q / a} \\ \mbox{q / (a - bq)}\end{matrix} \right.$

porque si q divide a y b, obviamente divide a - b·q que es una combinación lineal de ambos, y recíprocamente a = (a - b·q) + b·q es una combinación lineal de b y a - b·q. Luego el menor de los divisores comunes es el mismo, y repitiendo la operación:

mcd (b, r₁) = mcd (r₁, r₂) = mcd (r₂, r₃) = ... = mcd (r_n-1, r_n) = mcd (r_n-1, 0) = r_n-1.

Esto permite detallar el algoritmo efectivo:

datos de entrada a y b   -  si hace falta, cambiarlos a positivos el algoritmo: mientras b ≠ 0 repetir las tres instrucciones siguientes: r ← resto de a / b     (dar a r el valor del resto de a dividido por b)       a ← b     (el nuevo valor de a es el antiguo valor de b) b ← r     (el nuevo valor de b es el valor de r) el resultado es a (su último valor).

Este algoritmo da como resultado 0 si a y b son nulos, mientras que en matemáticas, el mayor divisor de cero no existe.

Ejemplos

Se busca el máximo común divisor de a = 945 y b = 651, números escogidos al azar:

945 = 1×651 + 294
651 = 2×294 + 63
294 = 4×63 + 42
 63 = 1×42 + 21
 42 = 2×21 + 0        entonces mcd(951; 294) = 21 (el último resto no nulo).

Como segundo ejemplo, tomemos números de tamaños parecidos a los anteriores: a = 987 y b = 610:

987 = 1×610 + 377
610 = 1×377 + 233
233 = 1×144 + 89
144 = 1×89 + 55
 89 = 1×55 + 34
 34 = 1×21 + 13
 21 = 1×13 + 8
 13 = 1×8 + 5
  8 = 1×5 + 3
  5 = 1×3 + 2
  3 = 1×2 + 1        entonces mcd(987; 610) = 1

El segundo ejemplo es sustencialmente más largo que el primero, y esto se debe a que todos los cocientes valen 1. Aquí a y b no fueron escogidos al azar: son dos términos consecutivos de la sucesión de Fibonacci; es el peor de los casos para este algoritmo. Sin embargo, el número de pasos elementales es en O(n²) - inferior a An² con A una constante - donde n es el menor número de cifras de a y b.

fracciones continuas

Las divisiones euclidianas del algoritmo son idénticas a las que permiten hallar la expresión en fracción continua de

$\frac a b$

.

En efecto,

$a = bq_1 + r_1$

se puede escribir

$\frac a b = q_1 + \frac {r_1} b$

. Del mismo modo,

$b = r_1 q_2 + r_2 \,$

se escribe

$\frac b {r_1} = q_2 + \frac {r_2} {r_1}$

y si lo inyectamos en la igualdad anterior obtenemos

$\frac a b = q_1 + \frac 1 {q_2 + \frac {r_2} {r_1}}$

y el proceso se repite hasta utilizar todas las divisiones euclidianas, y da lugar a fracciones con muchos "pisos". Los dos ejemplos numéricos del párrafo anterior dan:

$\frac {945} {651} = 1 + \frac 1 {2 + \frac 1 {4 + \frac 1 {1 + \frac 1 2 }} } \quad \quad y \quad \quad \frac {987} {610} = 1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 {1 + \frac 1 2 }}}}}}}} }}$

Este proceso funciona también con valores irracionales de $\frac a b$ (con a y b reales). en tal caso, el algoritmo no se para, lo que da una fracción continua infinita. Son de especial interés estas fracciones, como en los casos de π y e.

Volviendo al caso a y b enteros, el algoritmo de Euclides permite encontrar los coeficientes enteros u y v de la identidad de Bézout au + bv = mcd(a,b) de fundamental importancia en la aritmética.

Generalización a los polinomios

Este algoritmo sólo precisa de la divisióon euclidiana, y por consiguiente se extiende a todos los dominios donde existe tal división: es el caso de las álgebras de polinomios, como Q[X] o R[X], (polinomios con coeficientes racionales o reales). Obviamente, los cálculos se vuelven mucho más largos.
Un ejemplo no demasiado complicado, pero tampoco trivial:

Sea

$P=X^3-6X^2-63X+392 \quad$

un polinomio que se cree que tiene una raíz doble.

como resolver una ecuación de tercer grado no es evidente, para hallar la raíz múltiple empleamos la propiedad que dice las raices múltiples son las en común entre el polinomio y su polinomio derivado.

Para simplificar las divisiones, nos permitimos multiplicarlos por factores constantes no nulos, en fin de cuentas el mcm de dos polinomios está definido módulo un factor multiplicativo, así que esta manipulación no altera el resultado.

El polinomio derivado de P es

$P' = 3X^2 - 12X - 63 \quad$

que se puede simplificar por 3, según lo dicho anteriormente. Tomemos entonces

$Q = \frac {P'} 3 = X^2 - 4X - 21$

y efectuemos el algoritmo con P y Q.

$P = (X-2)Q -50X + 350 \quad$

. El resto se factoriza en

$\quad -50(X - 7)$

: tomemos entonces

$\quad R = X - 7$

$Q = (X+3)R + 0 \quad$

 lo que implica que el mcd buscado es

$X-7 \quad$

. Entonces 7 es la raíz doble de P.
En efecto:

$P = (X - 7)^2(X + 8) \quad$

y de paso

$P' = 3(X - 7)(X + 3) \quad$

.

Autor: M.Romero Schmidtke