El algoritmo de Euclides

El máximo común divisor entre dos números enteros es el mayor número que divide a ambos.

Ejemplo

Si se tiene el $20$ y el $16$ , el máximo común divisor entre los dos es $4$ , ya que:

Los divisores de $20$ son: $1$ , $2$ , $4$ , $5$ , $10$ y $20$

Los divisores de $16$ son: $1$ , $2$ , $4$ y $16$

Los números que dividen tanto a $20$ como a $16$ son: $1, 2$ y $4$ , y claramente el mayor es $4$ . Así pues, el máximo común divisor entre $20$ y $16$ es $4$ , y se escribe $m c d (20, 16) = 4$ .

No obstante, calcular el máximo común divisor entre dos números puede resultar muy complicado para números muy grandes.

Para hacerlo, existe un método conocido por el nombre de algoritmo de Euclides, que, aunque al principio puede parecer un poco extraño, cuando se coge práctica resulta mucho más cómodo y sencillo que otros métodos.

Además, por si fuera poco, también sirve para resolver ecuaciones diofánticas.

El algoritmo de Euclides se basa en la definición de tres secuencias de números: la primera se llamará $r_{j}$ , la segunda se llamará $s_{j}$ y la tercera $t_{j}$ .

El algoritmo de Euclides consiste en realizar los siguientes pasos:

Se cogen dos números: $a \geq 0$ , $b > 0$ . Se quiere calcular $m c d (a, b)$ (el máximo común divisor entre $a$ y $b$ ). Se podría tomar $a = 10$ y $b = 5$ .
Se define: $\begin{array}{rclrcl} r_{0} & = & a, & r_{1} & = & b \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$ Por ejemplo con $a = 10$ y $b = 5$ , se tendría: : $\begin{array}{rclrcl} r_{0} & = & 10, & r_{1} & = & 5 \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$
Para $j \geq 2$ , hacemos la división entera de $r_{j - a}$ entre $r_{j - 1}$ . Al resultado le llamamos $q_{j - 1}$ y al residuo $r_{j}$ .

En el ejemplo anterior, si queremos calcular $r_{2}$ y $q_{1}$ (es decir, $j = 2$ ) se tiene que hacer la división entera entre $r_{0} = 10$ y $r_{1} = 5$ . Está claro que el resultado de la divisón es $2$ con residuo $0$ , y por lo tanto escribimos $q_{1} = 2$ y $r_{2} = 0$ .

Ahora, se define: $\begin{array}{rcl} s_{j} & = & s_{j - 2} - s_{j - 1} \cdot q_{j - 1} \\ t_{j} & = & t_{j - 2} - t_{j - 1} \cdot q_{j - 1} \end{array}$ En el ejemplo anterior se tendría: $\begin{array}{rcl} s_{2} & = & s_{0} - s_{1} \cdot q_{1} = 1 - 0 \cdot 1 = 1 \\ t_{2} & = & t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 2 = - 2 \end{array}$
Cuando haya un $r_{n + 1} = 0$ , entonces se tiene que $m c d (a, b) = r_{n}$ (es decir, el del paso anterior!). Además, también se cumple que: $m c d (a, b) = s_{n} \cdot a + t_{n} \cdot b$ ( $s_{n}$ y $t_{n}$ son también los del paso anterior).

Volviendo al ejemplo que se ha tratado en los pasos previos, se ha visto que para $j = 2$ ya se cumple que $r_{2} = 0$ . Por lo tanto, el máximo común divisor entre $10$ y $5$ es $r_{1}$ (el del paso anterior), es decir $5$ .

Además la última igualdad nos dice que: $m c d (10, 5) = s_{1} \cdot 10 + t_{1} \cdot 5 = 0 \cdot 10 + 1 \cdot 5 = 0$